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
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?)

  • [1] Manuel Bodirsky, Mihyun Kang, Mike Löffler, and Colin McDiarmid, Random cubic planar graphs, Random Structures Algorithms 30 (2007), no. 1-2, 78-94. MR 2283223 (2007k:05193),
  • [2] Béla Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257-274. MR 756039 (85k:05090),
  • [3] Béla Bollobás, The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 35-57. MR 777163 (86i:05119)
  • [4] Béla Bollobás, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. MR 809996 (87f:05152)
  • [5] Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, and David B. Wilson, The scaling window of the 2-SAT transition, Random Structures Algorithms 18 (2001), no. 3, 201-256. MR 1824274 (2002a:68052),
  • [6] Guillaume Chapuy, Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy, Asymptotic enumeration and limit laws for graphs of fixed genus, J. Combin. Theory Ser. A 118 (2011), no. 3, 748-777. MR 2745423 (2012g:05105),
  • [7] P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17-61 (English, with Russian summary). MR 0125031 (23 #A2338)
  • [8] Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Graph theory and combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 167-215. MR 1001395 (90d:05184),
  • [9] Philippe Flajolet, Bruno Salvy, and Gilles Schaeffer, Airy phenomena and analytic combinatorics of connected graphs, Electron. J. Combin. 11 (2004), no. 1, Research Paper 34, 30 pp. (electronic). MR 2056086 (2005a:05014)
  • [10] Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235 (2010h:05005)
  • [11] Stefanie Gerke, Omer Giménez, Marc Noy, and Andreas Weißl, The number of graphs not containing $ K_{3,3}$ as a minor, Electron. J. Combin. 15 (2008), no. 1, Research Paper 114, 20. MR 2438586 (2009d:05109)
  • [12] O. Giménez, M. Noy, and J. Rué, Graph classes with given 3-connected components: asymptotic enumeration and random graphs, Random Structures Algorithms 42 (2013), no. 4, 438-479. MR 3068033
  • [13] Svante Janson, Donald E. Knuth, Tomasz Łuczak, and Boris Pittel, The birth of the giant component, with an introduction by the editors, Random Structures Algorithms 4 (1993), no. 3, 231-358. MR 1220220 (94h:05070),
  • [14] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847 (2001k:05180)
  • [15] Mihyun Kang and Tomasz Łuczak, Two critical periods in the evolution of random planar graphs, Trans. Amer. Math. Soc. 364 (2012), no. 8, 4239-4265. MR 2912453,
  • [16] Tomasz Łuczak, Boris Pittel, and John C. Wierman, The structure of a random graph at the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), no. 2, 721-748. MR 1138950 (94d:05123),
  • [17] Richard Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599. MR 0025715 (10,53c)
  • [18] V. E. Stepanov, Some features of the structure of a random graph near a critical point, Teor. Veroyatnost. i Primenen. 32 (1987), no. 4, 633-657 (Russian). MR 927246 (89m:05102)
  • [19] E. M. Wright, The number of connected sparsely edged graphs. III. Asymptotic results, J. Graph Theory 4 (1980), no. 4, 393-407. MR 595607 (82d:05070),

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

Vlady Ravelomanana
Affiliation: LIAFA UMR CNRS 7089, Université Denis Diderot, 175, Rue du Chevaleret, 75013 Paris, France

Juanjo Rué
Affiliation: Instituto de Ciencias Matemáticas, Calle Nicolás Cabrera 15, 28049 Madrid, Spain

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