TY - JOUR
T1 - Anatomy of the giant component
T2 - The strictly supercritical regime
AU - Ding, Jian
AU - Lubetzky, Eyal
AU - Peres, Yuval
PY - 2014/1
Y1 - 2014/1
N2 - In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdo{double acute}s-Rényi random graph G(n,p) as it emerges from the critical window, i.e.for p = (1 + ε) / n where ε3n → ∞ and ε = o (1), in terms of a tractable contiguous model. Here we provide the analogous description for the supercritical giant component, i.e.the largest component of G(n,p) for p = λ / n where λ > 1 is fixed. The contiguous model is roughly as follows. Take a random degree sequence and sample a random multigraph with these degrees to arrive at the kernel; replace the edges by paths whose lengths are i.i.d.geometric variables to arrive at the 2-core; attach i.i.d.Poisson-Galton-Watson trees to the vertices for the final giant component. As in the case of the emerging giant, we obtain this result via a sequence of contiguity arguments at the heart of which are Kim's Poisson-cloning method and the Pittel-Wormald local limit theorems.
AB - In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdo{double acute}s-Rényi random graph G(n,p) as it emerges from the critical window, i.e.for p = (1 + ε) / n where ε3n → ∞ and ε = o (1), in terms of a tractable contiguous model. Here we provide the analogous description for the supercritical giant component, i.e.the largest component of G(n,p) for p = λ / n where λ > 1 is fixed. The contiguous model is roughly as follows. Take a random degree sequence and sample a random multigraph with these degrees to arrive at the kernel; replace the edges by paths whose lengths are i.i.d.geometric variables to arrive at the 2-core; attach i.i.d.Poisson-Galton-Watson trees to the vertices for the final giant component. As in the case of the emerging giant, we obtain this result via a sequence of contiguity arguments at the heart of which are Kim's Poisson-cloning method and the Pittel-Wormald local limit theorems.
UR - http://www.scopus.com/inward/record.url?scp=84882608773&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84882608773&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2013.06.004
DO - 10.1016/j.ejc.2013.06.004
M3 - Article
AN - SCOPUS:84882608773
SN - 0195-6698
VL - 35
SP - 155
EP - 168
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -