On the probability of planarity of a random graph near the critical point
HTML articles powered by AMS MathViewer
- by Marc Noy, Vlady Ravelomanana and Juanjo Rué PDF
- Proc. Amer. Math. Soc. 143 (2015), 925-936 Request permission
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 \[ \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 \[ 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
- 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, DOI 10.1002/rsa.20149
- Béla Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257–274. MR 756039, DOI 10.1090/S0002-9947-1984-0756039-5
- Béla Bollobás, The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 35–57. MR 777163
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- 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, DOI 10.1002/rsa.1006
- 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, DOI 10.1016/j.jcta.2010.11.014
- 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 125031
- Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Discrete Math. 75 (1989), no. 1-3, 167–215. Graph theory and combinatorics (Cambridge, 1988). MR 1001395, DOI 10.1016/0012-365X(89)90087-3
- 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. MR 2056086
- Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
- 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
- Omer Giménez, Marc Noy, and Juanjo Rué, Graph classes with given 3-connected components: asymptotic enumeration and random graphs, Random Structures Algorithms 42 (2013), no. 4, 438–479. MR 3068033, DOI 10.1002/rsa.20421
- Svante Janson, Donald E. Knuth, Tomasz Łuczak, and Boris Pittel, The birth of the giant component, Random Structures Algorithms 4 (1993), no. 3, 231–358. With an introduction by the editors. MR 1220220, DOI 10.1002/rsa.3240040303
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- 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, DOI 10.1090/S0002-9947-2012-05502-4
- 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, DOI 10.1090/S0002-9947-1994-1138950-5
- Richard Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583–599. MR 25715, DOI 10.2307/1969046
- 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
- E. M. Wright, The number of connected sparsely edged graphs. III. Asymptotic results, J. Graph Theory 4 (1980), no. 4, 393–407. MR 595607, DOI 10.1002/jgt.3190040409
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
- 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 - Communicated by: David Levin
- © Copyright 2014 American Mathematical Society
- 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
- MathSciNet review: 3293711
Dedicated: We dedicate this paper to the memory of Philippe Flajolet