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

Dates:

Date	Event
2010	Published

Volume:

Vol.15

Number of Pages:

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.