Anatomy of the giant component: the strictly supercritical regime

DOI10.1016/J.EJC.2013.06.004MaRDI QIDQ2509745zbMATH OpenOpenAlexFDO

Authors Jian Ding, Eyal Lubetzky, Yuval Peres

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.6112

zbMATH Keywords

contiguous modelPittel-Wormald local limit theoremsPoisson-Galton-Watson trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: In a recent work of the authors and Kim, we derived a complete description of the largest component of the ErdH{o}s-R'enyi random graph $G(n,p)$ as it emerges from the critical window, i.e. for $p=(1+epsilon)/n$ where $epsilo{n}^{3}noinfty$ and $epsilon=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=lambda/n$ where $lambda>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.

Recommendations

• Anatomy of a Young giant component in the random graph
• A new approach to the giant component problem
• Component structure of the configuration model: barely supercritical case
• scientific article; zbMATH DE number 6011074
• Giant components in random graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Anatomy of a Young giant component in the random graph
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Component behavior near the critical point of the random graph process
• Counting connected graphs inside-out
• Critical random graphs: limiting constructions and distributional properties
• Cycles in a random graph near the critical point
• Diameters in supercritical random graphs via first passage percolation
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Mixing time of near-critical random graphs
• Poisson Cloning Model for Random Graphs
• Random graphs.
• The asymptotic number of labeled graphs with given degree sequences
• The continuum random tree. III
• The diameter of sparse random graphs
• The Evolution of Random Graphs
• The mixing time of the giant component of a random graph
• The Structure of a Random Graph at the Point of the Phase Transition
• Tree-valued Markov chains derived from Galton-Watson processes

Cited in

(25)

• Random walks on the random graph
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Depth first exploration of a configuration model
• The maximal length of 2-path in random critical graphs
• Finding paths in sparse random graphs requires many queries
• Anatomy of a Young giant component in the random graph
• A principle of moderate deviations for the size of the largest component in an Erdős-Rényi random graph in the supercritical case
• Finding and using expanders in locally sparse graphs
• Diameters in supercritical random graphs via first passage percolation
• Asymptotics in percolation on high-girth expanders
• Component structure of the configuration model: barely supercritical case
• Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
• Cycle lengths in sparse random graphs
• Voter models on subcritical scale‐free random graphs
• Speeding up random walk mixing by starting from a uniform vertex
• Heavy and light paths and Hamilton cycles
• Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs
• Discursive voter models on the supercritical scale-free network
• Expansion in supercritical random subgraphs of expanders and its consequences
• Giant rainbow trees in sparse random graphs
• Average-case and smoothed analysis of graph isomorphism
• From Delaunay triangulation to topological data analysis: generation of more realistic synthetic power grid networks
• Canonical labeling of sparse random graphs
• Low-temperature sampling on sparse random graphs

This page was built for publication: Anatomy of the giant component: the strictly supercritical regime

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509745)