Asymptotic normality of the size of the giant component via a random walk

Journal article

In this paper we give a simple new proof of a result of Pittel and Wormald concerning the asymptotic value and (suitably rescaled) limiting distribution of the number of vertices in the giant component of $G(n,p)$ above the scaling window of the phase transition. Nachmias and Peres used martingale arguments to study Karp's exploration process, obtaining a simple proof of a weak form of this result. We use slightly different martingale arguments to obtain a much sharper result with little extra work.

Authors: Bollobas, B; Riordan, O

• Publication status: Published
• Journal: J. Combinatorial Theory B 102 (2012), 53--61
• Volume: 102
• Issue: 1
• Pages: 53-61
• Publication date: 2010-10-21
• DOI: 10.1016/j.jctb.2011.04.003
• EISSN: 1096-0902
• ISSN: 0095-8956
• Language: English
• Keywords: math.PR; 05C80; math.CO