Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Two critical periods in the evolution of random planar graphs


Authors: Mihyun Kang and Tomasz Łuczak
Journal: Trans. Amer. Math. Soc. 364 (2012), 4239-4265
MSC (2010): Primary 05C10, 05C80; Secondary 05C30, 05A16
DOI: https://doi.org/10.1090/S0002-9947-2012-05502-4
Published electronically: March 13, 2012
MathSciNet review: 2912453
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ P(n,M)$ be a graph chosen uniformly at random from the family of all labeled planar graphs with $ n$ vertices and $ M$ edges. In this paper we study the component structure of $ P(n,M)$. Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of $ P(n,M)$. The first one, of width $ \Theta (n^{2/3})$, is analogous to the phase transition observed in the standard random graph models and takes place for $ M=n/2+O(n^{2/3})$, when the largest complex component is formed. Then, for $ M=n+O(n^{3/5})$, when the complex components cover nearly all vertices, the second critical period of width $ n^{3/5}$ occurs. Starting from that moment increasing of $ M$ mostly affects the density of the complex components, not its size.


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

  • 1. C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Struc. Alg. 19 (2001), 194-246. MR 1871555 (2002k:05012)
  • 2. E. A. Bender and E. R. Canfield, The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B 53 (1991), 293-299. MR 1129556 (92g:05100)
  • 3. A. Bender, Z. Gao, and N. C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin. 9 (2002), Research Paper 43, 13 pp. MR 1946145 (2003i:05071)
  • 4. M. Bodirsky, M. Kang, M. Löffler, and C. McDiarmid, Random cubic planar graphs, Random Struc. Alg. 30 (2007), 78-94. MR 2283223 (2007k:05193)
  • 5. B. Bollobás, The evolution of random graphs, Trans. Am. Math. Soc. 286 (1984), 257-274. MR 756039 (85k:05090)
  • 6. J. Bouttier, P. Di Francesco, and E. Guitter, Planar maps as labeled mobiles, Electron. J. Combin. 11 (2004), Research Paper 69, 27 pp. MR 2097335 (2005i:05087)
  • 7. V. E. Britikov, Asymptotics of the number of forests made up of nonrooted trees, Math. Notes 43 (1988), 387-394. MR 954351 (89j:05063)
  • 8. G. Chapuy, É. Fusy, O. Giménez, B. Mohar, and M. Noy, Asymptotic enumeration and limit laws for graphs of fixed genus, to appear in SIAM Journal of Discrete Mathematics.
  • 9. P. Chassaing and G. Schaeffer, Random planar lattices and integrated superBrownian excursion, Probab. Theory Related Fields 128 (2004), 161-212. MR 2031225 (2004k:60016)
  • 10. C. Dowden, The evolution of uniform random planar graphs, Electron. J. Combin. 17 (2010), Research Paper 7. MR 2578902 (2011c:05306)
  • 11. P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61. MR 0125031 (23:A2338)
  • 12. A. Frieze, Random Graphs `85: Open problems, Annals of Discrete Mathematics 33 (1987), 353-354. MR 930478 (88j:05002)
  • 13. J. F. Le Gall, The topological structure of scaling limits of large planar maps, Invent. Math. 169 (2007), 621-670. MR 2336042 (2008i:60022)
  • 14. S. Gerke, C. McDiarmid, A. Steger, and A. Weißl, Random planar graphs with $ n$ nodes and a fixed number of edges, In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 999-1007, 2005. MR 2298359
  • 15. S. Gerke, D. Schlatter, A. Steger, and A. Taraz, The random planar graphs process, Random Struc. Alg. 32 (2008), 236-261. MR 2387559 (2008m:60015)
  • 16. O. Giménez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), 309-329. MR 2476775 (2010g:05031)
  • 17. F. Harary and E. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214 (50:9682)
  • 18. S. Janson, The growth of components in random graphs, Random Struc. Alg. 17 (2000), 343-356. MR 1801138 (2002j:05133)
  • 19. S. Janson, D. Knuth, T. Łuczak, and B. Pittel, The birth of the giant component, Random Struc. Alg. 4 (1993), 233-358. MR 1220220 (94h:05070)
  • 20. S. Janson, T. Łuczak, and A. Ruciński, Random Graphs, Wiley, New York, 2000. MR 1782847 (2001k:05180)
  • 21. T. Łuczak, Component behavior near the critical point of the random graph, Random Struc. Alg. 1 (1990), 287-310. MR 1099794 (92c:05139)
  • 22. T. Łuczak, Cycles in random graphs, Discrete Math. 98 (1991), 231-236. MR 1144405 (92i:05190)
  • 23. T. Łuczak, The phase transition in a random graph, In Combinatorics, Paul Erdős is eighty, Vol. 2, Bolyai Soc. Math. Stud., 2, J. Bolyai Math. Soc., Budapest, 1996, 399-422. MR 1395867 (97d:05245)
  • 24. T. Łuczak and B. Pittel, Components of random forests, Comb. Probab. Comput. 1 (1992), 35-52. MR 1167294 (93i:05118)
  • 25. T. Łuczak, B. Pittel, and J. Wierman, The structure of a random graph near the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), 721-748. MR 1138950 (94d:05123)
  • 26. M. J. Luczak and T. Łuczak, The phase transition in the cluster-scaled model of a random graph, Random Struc. Alg. 28 (2006), 215-246. MR 2198498 (2006k:05193)
  • 27. C. McDiarmid, Random graphs on surfaces, J. Combin. Theory Ser. B 98 (2008), 778-797. MR 2418771 (2009c:05224)
  • 28. C. McDiarmid and B. Reed, On the maximum degree of a random planar graph, Combin. Probab. Comput. 17 (2008), 591-601. MR 2433943 (2009m:05165)
  • 29. C. McDiarmid, A. Steger, and D. Welsh, Random planar graphs, J. Combin. Theory Ser. B 93 (2005), 187-205. MR 2117936 (2005k:05221)
  • 30. D. Osthus, H. J. Prömel, and A. Taraz, On random planar graphs, the number of planar graphs and their triangulations. J. Combin. Theory Ser. B 88 (2003), 119-134. MR 1973264 (2004a:05068)
  • 31. G. Schaeffer, Conjugaison d'arbres et cartes combinatoires aléatoires, Ph.D. Thesis (in French), Université Bordeaux I, 1998.
  • 32. O. Schramm, Conformally invariant scaling limits: An overview and a collection of problems. In International Congress of Mathematicians. Vol. I, pages 513-543. Eur. Math. Soc., Zürich, 2007. MR 2334202 (2008j:60237)
  • 33. W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249-271. MR 0146823 (26:4343)
  • 34. W. T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38. MR 0130841 (24:A695)

Similar Articles

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

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


Additional Information

Mihyun Kang
Affiliation: Institut für Optimierung und Diskrete Mathematik (Math B), Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria
Email: kang@math.tugraz.at

Tomasz Łuczak
Affiliation: Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland
Email: tomasz@amu.edu.pl

DOI: https://doi.org/10.1090/S0002-9947-2012-05502-4
Received by editor(s): June 2, 2010
Received by editor(s) in revised form: November 5, 2010
Published electronically: March 13, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society