Anatomy of the giant component: The strictly supercritical regime

Jian Ding, Eyal Lubetzky, Yuval Peres

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)155-168
Number of pages14
JournalEuropean Journal of Combinatorics
Volume35
DOIs
StatePublished - Jan 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Anatomy of the giant component: The strictly supercritical regime'. Together they form a unique fingerprint.

Cite this