TY - JOUR

T1 - Anatomy of the giant component

T2 - The strictly supercritical regime

AU - Ding, Jian

AU - Lubetzky, Eyal

AU - Peres, Yuval

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

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

VL - 35

SP - 155

EP - 168

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -