The Library

Critical random graphs : limiting constructions and distributional properties

Tools

Addario-Berry, L., Broutin, N. and Goldschmidt, C. (Christina). (2010) Critical random graphs : limiting constructions and distributional properties. Electronic Journal of Probability, Vol.15 . pp. 741-775. ISSN 1083-6489

Preview

PDF
WRAP_Goldschmidt_Critical_random_graphs.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (395Kb)

Official URL: http://www.math.washington.edu/~ejpecp/

Abstract

We consider the Erdos-Renyi random graph G(n, p) inside the critical window, where p = 1/n + lambda n(-4/3) for some lambda is an element of R. We proved in Addario-Berry et al. [2009+] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n(-1/3) and letting n -> infinity yields a non-trivial sequence of limit metric spaces C = (C-1, C-2,...). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous' Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on R+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Luczak et al. [1994] by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Random graphs
Journal or Publication Title:	Electronic Journal of Probability
Publisher:	University of Washington. Dept. of Mathematics
ISSN:	1083-6489
Official Date:	2010
Volume:	Vol.15
Number of Pages:	35
Page Range:	pp. 741-775
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
Funder:	Natural Sciences and Engineering Research Council of Canada (NSERC), Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/D065755/1 (EPSRC)
References:	[1] L. Addario-Berry, N. Broutin, and C. Goldschmidt. The continuum limit of critical random graphs. arXiv:0903.4730v1 [math.PR], 2009+. [2] D. Aldous. The continuum random tree. I. Ann. Probab., 19(1):1–28, 1991. ISSN 0091-1798. MR1085326 [3] D. Aldous. The continuum random tree. II. An overview. In Stochastic analysis (Durham, 1990), volume 167 of London Math. Soc. Lecture Note Ser., pages 23–70. Cambridge University Press, Cambridge, 1991. MR1166406 [4] D. Aldous. The continuum random tree. III. Ann. Probab., 21(1):248–289, 1993. ISSN 0091- 1798. MR1207226 [5] D. Aldous. Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab., 22(2):527–545, 1994. ISSN 0091-1798. MR1288122 [6] D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab., 25:812–854, 1997. MR1434128 [7] D. Aldous and J. Pitman. Brownian bridge asymptotics for random mappings. Random Structures Algorithms, 5(4):487–512, 1994. ISSN 1042-9832. MR1293075 [8] D. Aldous, G. Miermont, and J. Pitman. Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees. Probability Theory and Related Fields, 133(1):1–17, 2005. MR2197134 [9] D.J. Aldous. Exchangeability and related topics. In École d’été de probabilités de Saint-Flour, XIII, volume 1117, pages 1–198, Berlin, 1983. Springer. MR0883646 [10] K. B. Athreya and P. E. Ney. Branching processes. Dover Publications Inc., Mineola, NY, 2004. ISBN 0-486-43474-5. Reprint of the 1972 original [Springer, New York; MR0373040]. MR0373040 [11] J. Bertoin and C. Goldschmidt. Dual random fragmentation and coagulation and an application to the genealogy of Yule processes. In Mathematics and computer science. III, Trends Math., pages 295–308. Birkhäuser, Basel, 2004. MR2090520 [12] J. Bertoin and J. Pitman. Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math., 118(2):147–166, 1994. ISSN 0007-4497. MR1268525 [13] D. Blackwell and D. G. Kendall. The Martin boundary for Pólya’s urn scheme, and an application to stochastic population growth. J. Appl. Probab., 1:284–296, 1964. MR0176518 [14] B. Bollobás. Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2001. MR1864966 [15] L. Chaumont and M. Yor. Exercises in probability, volume 13 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2003. ISBN 0- 521-82585-7. A guided tour from measure theory to random processes, via conditioning. MR2016344 [16] B. de Finetti. Funzione caratteristica di un fenomeno aleatorio. Atti della R. Academia Nazionale dei Lincei, Serie 6. Memorie, Classe di Scienze Fisiche, Mathematice e Naturale, 4: 251—299, 1931. [17] J. Ding, J.H. Kim, E. Lubetzky, and Y. Peres. Anatomy of a young giant component in the random graph. arXiv:0906.1839v1 [math.CO], 2009. [18] D. Dufresne. Algebraic properties of beta and gamma distributions, and applications. Adv. Appl. Math., 20:285–299, 1998. MR1618423 [19] F. Eggenberger and G. Pólya. Uber die Statistik verketteter Vorgange. Zeitschrift fur Angewandte Mathematik und Mechanik, 3:279–289, 1923. [20] P. Erd˝os and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17–61, 1960. MR0125031 [21] S.N. Evans, J. Pitman, and A. Winter. Rayleigh processes, real trees, and root growth with regrafting. Probab. Theory Related Fields, 134(1):81–126, 2006. ISSN 0178-8051. MR2221786 [22] W. Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971. MR0270403 [23] D.A. Freedman. Bernard Friedman’s urn. The Annals of Mathematical Statistics, 36:956–970, 1965. MR0177432 [24] L. Gordon. A stochastic approach to the gamma function. Amer. Math. Monthly, 101(9): 858–865, 1994. MR1300491 [25] S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel. The birth of the giant component. Random Structures Algorithms, 4:233–358, 1993. MR1220220 [26] S. Janson, T. Łuczak, and A. Ruciínski. Random Graphs. Wiley, New York, 2000. MR1782847 [27] N.L. Johnson, S. Kotz, and N. Balakrishnan. Continuous Univariate Distributions, volume 1. Wiley, New York, NY, second edition, 1994. MR1299979 [28] J.-F. Le Gall. Random trees and applications. Probab. Surv., 2:245–311 (electronic), 2005. ISSN 1549-5787. MR2203728 [29] T. Łuczak, B. Pittel, and J. C. Wierman. The structure of a random graph at the point of transition. Trans. Amer. Math. Soc., 341:721–748, 1994. MR1138950 [30] Y. Peres and D. Revelle. Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs. arXiv:math/0410430v2 [math.PR], 2004. MR2110019 [31] J. Pitman. Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times. Electron. J. Probab., 4:no. 11, 33 pp. (electronic), 1999. ISSN 1083-6489. MR1690315 [32] J. Pitman. Combinatorial stochastic processes, volume 1875 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2006. MR2245368 [33] J.L. Rémy. Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. RAIRO Inform. Théor., 19:179–195, 1985. MR0803997 [34] J. Schweinsberg. The loop-erased random walk and the uniform spanning tree on the fourdimensional discrete torus. Probability Theory and Related Fields, 144(3):319–370, 2009. MR2496437 [35] S.S. Wilks. Certain generalizations in the analysis of variance. Biometrika, 24:471–494, 1932.
URI:	http://wrap.warwick.ac.uk/id/eprint/5782