A local limit theorem for the critical random graph
Wouter Kager (VU University)
Tobias Müller (Tel Aviv University)
Abstract
We consider the limit distribution of the orders of the $k$ largest components in the Erdos-Rényi random graph inside the "critical window" for arbitrary $k$. We prove a local limit theorem for this joint distribution and derive an exact expression for the joint probability density function.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 122-131
Publication Date: February 19, 2009
DOI: 10.1214/ECP.v14-1451
References
- D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), 812-854. Math. Review 98d:60019
- B. Bollob·s. Random graphs Cambridge Studies in Advanced Mathematics. 73 (2001), Cambridge University Press, Cambridge, second edition. Math. Review 2002j:05132
- S. Janson, D.E. Knuth, T. Luczak, and B. Pittel. The birth of the giant component. Random Structures Algorithms 4 (1993), 231-358. Math. Review 94h:05070
- T. Luczak, B. Pittel, and J.C. Wierman. The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 (1994), 721-748. Math. Review 94d:05123
- B. Pittel. On the largest component of the random graph at a nearcritical stage. J. Combin. Theory Ser. B 82 (2001), 237-269. Math. Review 2002j:05134
- J. Spencer. Enumerating graphs and Brownian motion. Comm. Pure Appl. Math. 50 (1997), 291-294. Math. Review 97k:05105
- E.M. Wright. The number of connected sparsely edged graphs. J. Graph Theory 1 (1977), 317-330. Math. Review 463026
- E.M. Wright. The number of connected sparsely edged graphs. II. Smooth graphs and blocks. J. Graph Theory 2 (1978), 299-305. Math. Review 0505805
- E.M. Wright. The number of connected sparsely edged graphs. III. Asymptotic results. J. Graph Theory 4 (1980), 393-407. Math. Review 82d:05070
This work is licensed under a Creative Commons Attribution 3.0 License.