Two critical periods in the evolution of random planar graphs

Kang, Mihyun; Łuczak, Tomasz

doi:10.1090/S0002-9947-2012-05502-4

Two critical periods in the evolution of random planar graphs
HTML articles powered by AMS MathViewer

by Mihyun Kang and Tomasz Łuczak PDF

Trans. Amer. Math. Soc. 364 (2012), 4239-4265 Request permission

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

Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michèle Soria, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Structures Algorithms 19 (2001), no. 3-4, 194–246. Analysis of algorithms (Krynica Morska, 2000). MR 1871555, DOI 10.1002/rsa.10021
Edward A. Bender and E. Rodney Canfield, The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B 53 (1991), no. 2, 293–299. MR 1129556, DOI 10.1016/0095-8956(91)90079-Y
Edward A. Bender, Zhicheng Gao, and Nicholas C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin. 9 (2002), no. 1, Research Paper 43, 13. MR 1946145
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
J. Bouttier, P. Di Francesco, and E. Guitter, Planar maps as labeled mobiles, Electron. J. Combin. 11 (2004), no. 1, Research Paper 69, 27. MR 2097335
V. E. Britikov, Asymptotics of the number of forests made up of nonrooted trees, Mat. Zametki 43 (1988), no. 5, 672–684, 703 (Russian); English transl., Math. Notes 43 (1988), no. 5-6, 387–394. MR 954351, DOI 10.1007/BF01158847
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.
Philippe Chassaing and Gilles Schaeffer, Random planar lattices and integrated superBrownian excursion, Probab. Theory Related Fields 128 (2004), no. 2, 161–212. MR 2031225, DOI 10.1007/s00440-003-0297-8
Chris Dowden, The evolution of uniform random planar graphs, Electron. J. Combin. 17 (2010), no. 1, Research Paper 7, 20. MR 2578902
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
MichałKaroński and Zbigniew Palka (eds.), Random graphs ’85, North-Holland Mathematics Studies, vol. 144, North-Holland Publishing Co., Amsterdam, 1987. Papers from the second international seminar on random graphs and probabilistic methods in combinatorics held at Adam Mickiewicz University, Poznań, August 5–9, 1985; Annals of Discrete Mathematics, 33. MR 930478
Jean-François Le Gall, The topological structure of scaling limits of large planar maps, Invent. Math. 169 (2007), no. 3, 621–670. MR 2336042, DOI 10.1007/s00222-007-0059-9
Stefanie Gerke, Colin McDiarmid, Angelika Steger, and Andreas Weißl, Random planar graphs with $n$ nodes and a fixed number of edges, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 999–1007. MR 2298359
Stefanie Gerke, Dirk Schlatter, Angelika Steger, and Anusch Taraz, The random planar graph process, Random Structures Algorithms 32 (2008), no. 2, 236–261. MR 2387559, DOI 10.1002/rsa.20186
Omer Giménez and Marc Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), no. 2, 309–329. MR 2476775, DOI 10.1090/S0894-0347-08-00624-3
Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
Svante Janson, Growth of components in random graphs, Proceedings of the Ninth International Conference “Random Structures and Algorithms” (Poznan, 1999), 2000, pp. 343–356. MR 1801138, DOI 10.1002/1098-2418(200010/12)17:3/4<343::AID-RSA8>3.3.CO;2-4
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
Tomasz Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), no. 3, 287–310. MR 1099794, DOI 10.1002/rsa.3240010305
Tomasz Łuczak, Cycles in random graphs, Discrete Math. 98 (1991), no. 3, 231–236. MR 1144405, DOI 10.1016/0012-365X(91)90379-G
T. Łuczak, The phase transition in a random graph, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 399–422. MR 1395867
Tomasz Łuczak and Boris Pittel, Components of random forests, Combin. Probab. Comput. 1 (1992), no. 1, 35–52. MR 1167294, DOI 10.1017/S0963548300000067
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
Malwina Luczak and Tomasz Łuczak, The phase transition in the cluster-scaled model of a random graph, Random Structures Algorithms 28 (2006), no. 2, 215–246. MR 2198498, DOI 10.1002/rsa.20088
Colin McDiarmid, Random graphs on surfaces, J. Combin. Theory Ser. B 98 (2008), no. 4, 778–797. MR 2418771, DOI 10.1016/j.jctb.2007.11.006
Colin McDiarmid and Bruce Reed, On the maximum degree of a random planar graph, Combin. Probab. Comput. 17 (2008), no. 4, 591–601. MR 2433943, DOI 10.1017/S0963548308009097
Colin McDiarmid, Angelika Steger, and Dominic J. A. Welsh, Random planar graphs, J. Combin. Theory Ser. B 93 (2005), no. 2, 187–205. MR 2117936, DOI 10.1016/j.jctb.2004.09.007
Deryk Osthus, Hans Jürgen Prömel, and Anusch Taraz, On random planar graphs, the number of planar graphs and their triangulations, J. Combin. Theory Ser. B 88 (2003), no. 1, 119–134. MR 1973264, DOI 10.1016/S0095-8956(02)00040-0
G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires, Ph.D. Thesis (in French), Université Bordeaux I, 1998.
Oded Schramm, Conformally invariant scaling limits: an overview and a collection of problems, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 513–543. MR 2334202, DOI 10.4171/022-1/20
W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249–271. MR 146823, DOI 10.4153/CJM-1963-029-x
W. T. Tutte, A census of planar triangulations, Canadian J. Math. 14 (1962), 21–38. MR 130841, DOI 10.4153/CJM-1962-002-9