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

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. We use slightly different martingale arguments to obtain a much sharper result with little extra work.

11 pages; slightly expanded, reference added

Cited by in corpus (3)

• The phase transition in the configuration model
• Asymptotic normality of the size of the giant component in a random hypergraph
• Exploring hypergraphs with martingales