Discrete Mathematics & Theoretical Computer Science |

- 1 Departament de Matemàtica Aplicada II
- 2 Laboratoire d'informatique Algorithmique : Fondements et Applications
- 3 Instituto de Ciencias Matemàticas [Madrid]

Erdős and Rényi conjectured in 1960 that the limiting probability $p$ that a random graph with $n$ vertices and $M=n/2$ edges is planar exists. It has been shown that indeed p exists and is a constant strictly between 0 and 1. In this paper we answer completely this long standing question by finding an exact expression for this probability, whose approximate value turns out to be $p ≈0.99780$. More generally, we compute the probability of planarity at the critical window of width $n^{2/3}$ around the critical point $M=n/2$. We extend these results to some classes of graphs closed under taking minors. As an example, we show that the probability of being series-parallel converges to 0.98003. Our proofs rely on exploiting the structure of random graphs in the critical window, obtained previously by Janson, Łuczak and Wierman, by means of generating functions and analytic methods. This is a striking example of how analytic combinatorics can be applied to classical problems on random graphs.

Source: HAL:hal-01229657v1

Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Section: Proceedings

Published on: January 1, 2013

Imported on: November 21, 2016

Keywords: random graphs,planar cubic multigraphs,analytic combinatorics,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Funding:

- Source : OpenAIRE Graph
*Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.*; Funder: European Commission; Code: 208471

This page has been seen 373 times.

This article's PDF has been downloaded 732 times.