On tree census and the giant component in sparse random graphs

Abstract

Abstract For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn /2) and G ( n, Prob (edge) = c/n) define t n (k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t n (k) ‐ nh(k)]n −1/2 } is shown to be Gaussian in the limit n →∞, with h(k) = k k−2 c k−1 e −kc /k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 − T) −2 (1 − 2Tθ)θ(1 − θ) for the first model and n(1 − T) −2 θ(1 − θ) for the second model. Here Te −T = ce −c , T <1, and θ = 1 − T/c . A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc −1 ( β + β 2 /2 ) and variance n [ c −1 (β + β 2 /2) − c −2 ( c + 1)β 2 ], where βe β = c. It is also proven that almost surely the giant component consists of a giant two‐connected core of size about n (1 − T )β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.