Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

On the probability of planarity of a random graph near the critical point


Authors: Marc Noy, Vlady Ravelomanana and Juanjo Rué
Journal: Proc. Amer. Math. Soc. 143 (2015), 925-936
MSC (2010): Primary 05A16, 01C80; Secondary 05C10
DOI: https://doi.org/10.1090/S0002-9939-2014-12141-1
Published electronically: December 4, 2014
MathSciNet review: 3293711
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G(n,M)$ be the uniform random graph with $ n$ vertices and $ M$ edges. Erdős and Rényi (1960) conjectured that the limiting probability

$\displaystyle \lim _{n \to \infty } \mathrm {Pr}\{G(n,\textstyle {n\over 2}) \hbox { is planar}\} $

exists and is a constant strictly between 0 and $ 1$. Łuczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting probability of a random graph being planar near the critical point $ M=n/2$. For each $ \lambda $, we find an exact analytic expression for

$\displaystyle p(\lambda ) = \lim _{n \to \infty } \mathrm {Pr} \left \{G\left (n,\textstyle {n\over 2}(1+\lambda n^{-1/3})\right ) \hbox { is planar} \right \}.$

In particular, we obtain $ p(0) \approx 0.99780$. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of $ G(n,\textstyle {n\over 2})$ being series-parallel converges to $ 0.98003$. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05A16, 01C80, 05C10

Retrieve articles in all journals with MSC (2010): 05A16, 01C80, 05C10


Additional Information

Marc Noy
Affiliation: Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain
Email: marc.noy@upc.edu

Vlady Ravelomanana
Affiliation: LIAFA UMR CNRS 7089, Université Denis Diderot, 175, Rue du Chevaleret, 75013 Paris, France
Email: vlad@liafa.univ-paris-diderot.fr

Juanjo Rué
Affiliation: Instituto de Ciencias Matemáticas, Calle Nicolás Cabrera 15, 28049 Madrid, Spain
Email: juanjo.rue@icmat.es

DOI: https://doi.org/10.1090/S0002-9939-2014-12141-1
Received by editor(s): April 23, 2012
Received by editor(s) in revised form: November 16, 2012
Published electronically: December 4, 2014
Additional Notes: The first author was partially supported by grants MTM2011-24097 and DGR2009-SGR1040
The second author was partially supported by grant ANR-MAGNUM 2010 BLAN-0204
The third author was partially supported by grants JAE-DOC (CSIC), MTM2011-22851 and SEV-2011-0087
Dedicated: We dedicate this paper to the memory of Philippe Flajolet
Communicated by: David Levin
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society