On the fluctuations of the giant component (Q2703028)

This paper deals with the structure of the sparse random graph \(G(n,p)\) with \(p={c\over n}\) (\(c> 1\), a constant). Such a graph is obtained from the complete undirected graph on \(n\) vertices by deleting each edge independently of others with probability \(1-p\). It is well known that, as \(n\to\infty\), such a random graph contains a giant component with high probability. This giant component is the only large connected component in the graph whose size is close to \(ng(c)\) (\(g(c)\) being the single positive solution of \(1- t-e^{-ct}= 0\)). In this paper, an alternative proof of the central limit theorem for the fluctuations of the size of the giant component in sparse random graphs is provided. The proof presented here differs from earlier proofs in the sense that the argument investigates a depth-first search algorithm; through first-passage analysis using couplings and martingale limit theorems. As a consequence an upper bound for the rate of convergence is provided. The paper concludes by raising several interesting questions (suitable for future research) concerning the proof of the central limit theorem presented here.