Anatomy of the giant component: The strictly supercritical regime

preprint2012arXivOpen access

Abstract

In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdős-Rényi random graph G(n,p)G(n,p) as it emerges from the critical window, i.e. for p=(1+ε)/np = (1+ε)/n where ε3n→∞ε^3 n \to\infty and ε=o(1)ε=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)G(n,p) for p=λ/np = λ/n where λ>1λ>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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.