A local limit theorem for the critical random graph

Remco W van der Hofstad (Technische Universiteit Eindhoven)
Wouter Kager (VU University)
Tobias Müller (Tel Aviv University)


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


  1. D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), 812-854. Math. Review 98d:60019
  2. B. Bollob·s. Random graphs Cambridge Studies in Advanced Mathematics. 73 (2001), Cambridge University Press, Cambridge, second edition. Math. Review 2002j:05132
  3. 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
  4. 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
  5. 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
  6. J. Spencer. Enumerating graphs and Brownian motion. Comm. Pure Appl. Math. 50 (1997), 291-294. Math. Review 97k:05105
  7. E.M. Wright. The number of connected sparsely edged graphs. J. Graph Theory 1 (1977), 317-330. Math. Review 463026
  8. 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
  9. E.M. Wright. The number of connected sparsely edged graphs. III. Asymptotic results. J. Graph Theory 4 (1980), 393-407. Math. Review 82d:05070

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.