Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 15(2010) > Paper 25 open journal systems 


Critical random graphs: limiting constructions and distributional properties

Louigi Addario-Berry, McGill University
Nicolas Broutin, INRIA
Christina Goldschmidt, University of Warwick


Abstract
We consider the Erdös--Rényi random graph $G(n,p)$ inside the critical window, where $p=1/n+λ n-4/3$ for some $λ∈ R$. We proved in [1] 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 → ∞$ 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 [29] 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


Full text: PDF

Pages: 741-775

Published on: May 24, 2010
Bibliography
  1. Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina. The continuum limit of critical random graphs. arXiv:0903.4730v1 [math.PR], 2009+.
  2. Aldous, David. The continuum random tree. I. Ann. Probab. 19 (1991), no. 1, 1--28. MR1085326 (91i:60024)
  3. Aldous, David. The continuum random tree. II. An overview. Stochastic analysis (Durham, 1990), 23--70, London Math. Soc. Lecture Note Ser., 167, Cambridge Univ. Press, Cambridge, 1991. MR1166406 (93f:60010)
  4. Aldous, David. The continuum random tree. III. Ann. Probab. 21 (1993), no. 1, 248--289. MR1207226 (94c:60015)
  5. Aldous, David. Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab. 22 (1994), no. 2, 527--545. MR1288122 (95i:60007)
  6. Aldous, David. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), no. 2, 812--854. MR1434128 (98d:60019)
  7. Aldous, David J.; Pitman, Jim. Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 (1994), no. 4, 487--512. MR1293075 (95k:60055)
  8. Aldous, David; Miermont, Grégory; Pitman, Jim. Weak convergence of random $p$-mappings and the exploration process of inhomogeneous continuum random trees. Probab. Theory Related Fields 133 (2005), no. 1, 1--17. MR2197134 (2007f:60009)
  9. Aldous, David J. Exchangeability and related topics. École d'été de probabilités de Saint-Flour, XIII---1983, 1--198, Lecture Notes in Math., 1117, Springer, Berlin, 1985. MR0883646 (88d:60107)
  10. Athreya, Krishna B.; Ney, Peter E. Branching processes. Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972. xi+287 pp. MR0373040 (51 #9242)
  11. Bertoin, Jean; Goldschmidt, Christina. Dual random fragmentation and coagulation and an application to the genealogy of Yule processes. Mathematics and computer science. III, 295--308, Trends Math., Birkhäuser, Basel, 2004. MR2090520 (2005i:60162)
  12. Bertoin, Jean; Pitman, Jim. Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 (1994), no. 2, 147--166. MR1268525 (95b:60097)
  13. Blackwell, David; Kendall, David. The martin boundary of Pólya's urn scheme, and an application to stochastic population growth. J. Appl. Probability 1 1964 284--296. MR0176518 (31 #790)
  14. Bollobás, Béla. Random graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. xviii+498 pp. ISBN: 0-521-80920-7; 0-521-79722-5 MR1864966 (2002j:05132)
  15. Chaumont, Loic.; Yor, Marc. Exercises in probability. A guided tour from measure theory to random processes, via conditioning. Cambridge Series in Statistical and Probabilistic Mathematics, 13. Cambridge University Press, Cambridge, 2003. xvi+236 pp. ISBN: 0-521-82585-7 MR2016344 (2004m:60001)
  16. de Finetti, Bruno. Funzione caratteristica di un fenomeno aleatorio. Atti della R. Academia Nazionale dei Lincei, Serie 6. Memorie, Classe di Scienze Fisiche, Mathematice e Naturale, 4 1931 251---299.
  17. Ding, Jian; Kim, Jeong Han; Lubetzky, Eyal; Peres, Yuval. Anatomy of a young giant component in the random graph. arXiv:0906.1839v1 [math.CO], 2009.
  18. Dufresne, Daniel. Algebraic properties of beta and gamma distributions, and applications. Adv. in Appl. Math. 20 (1998), no. 3, 285--299. MR1618423 (99i:60036)
  19. F. Eggenberger and G. Pólya. Uber die Statistik verketteter Vorgange. Zeitschrift fur Angewandte Mathematik und Mechanik, 3: 1923 279--289.
  20. Erdős, P.; Rényi, A. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 1960 17--61. MR0125031 (23 #A2338)
  21. Evans, Steven N.; Pitman, Jim; Winter, Anita. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 (2006), no. 1, 81--126. MR2221786 (2007d:60003)
  22. Feller, William. An introduction to probability theory and its applications. Vol. II. Second edition John Wiley & Sons, Inc., New York-London-Sydney 1971 xxiv+669 pp. MR0270403 (42 #5292)
  23. Freedman, David A. Bernard Friedman's urn. Ann. Math. Statist 36 1965 956--970. MR0177432 (31 #1695)
  24. Gordon, Louis. A stochastic approach to the gamma function. Amer. Math. Monthly 101 (1994), no. 9, 858--865. MR1300491 (95k:33003)
  25. Janson, Svante; Knuth, Donald E.; Łuczak, Tomasz; Pittel, Boris. The birth of the giant component. With an introduction by the editors. Random Structures Algorithms 4 (1993), no. 3, 231--358. MR1220220 (94h:05070)
  26. Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847 (2001k:05180)
  27. Johnson, Norman L.; Kotz, Samuel; Balakrishnan, N. Continuous univariate distributions. Vol. 1. Second edition. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1994. xxii+756 pp. ISBN: 0-471-58495-9 MR1299979 (96j:62028)
  28. Le Gall, Jean-François. Random trees and applications. Probab. Surv. 2 (2005), 245--311 (electronic). MR2203728 (2007h:60078)
  29. Łuczak, Tomasz; Pittel, Boris; Wierman, John C. The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 (1994), no. 2, 721--748. MR1138950 (94d:05123)
  30. Peres, Yuval; Revelle, David. Mixing times for random walks on finite lamplighter groups. Electron. J. Probab. 9 (2004), no. 26, 825--845 (electronic). MR2110019 (2005m:60007)
  31. Pitman, Jim. Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times. Electron. J. Probab. 4 (1999), no. 11, 33 pp. (electronic). MR1690315 (2000e:60137)
  32. Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. x+256 pp. ISBN: 978-3-540-30990-1; 3-540-30990-X MR2245368 (2008c:60001)
  33. Rémy, Jean-Luc. Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire. (French) [An iterative procedure for enumerating binary trees and its application to their random generation] RAIRO Inform. Théor. 19 (1985), no. 2, 179--195. MR0803997 (87h:68132)
  34. Schweinsberg, Jason. The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus. Probab. Theory Related Fields 144 (2009), no. 3-4, 319--370. MR2496437 (2010e:60211)
  35. S.S. Wilks. Certain generalizations in the analysis of variance. Biometrika, 24 (1932) 471--494.
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489