Asymptotic normality of the size of the giant component via a random walk
Preprint
Abstract
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. Here we use slightly different martingale arguments to obtain the full result of Pittel and Wormald with little extra work.
Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- On tree census and the giant component in sparse random graphsRandom Structures & Algorithms, 1990
- The transitive closure of a random digraphRandom Structures & Algorithms, 1990