The phase transition in the configuration model

Abstract

Let $G=G(d)$ be a random graph with a given degree sequence $d$, such as a random $r$-regular graph where $r\ge 3$ is fixed and $n=|G|\to \infty$. We study the percolation phase transition on such graphs $G$, i.e., the emergence as $p$ increases of a unique giant component in the random subgraph $G[p]$ obtained by keeping edges independently with probability $p$. More generally, we study the emergence of a giant component in $G(d)$ itself as $d$ varies. We show that a single method can be used to prove very precise results below, inside and above the `scaling window' of the phase transition, matching many of the known results for the much simpler model $G(n,p)$. This method is a natural extension of that used by Bollobas and the author to study $G(n,p)$, itself based on work of Aldous and of Nachmias and Peres; the calculations are significantly more involved in the present setting.

37 pages

References in corpus (3)

• Component sizes of the random graph outside the scaling window
• Asymptotic normality of the size of the giant component via a random walk
• Edge percolation on a random regular graph of low degree

Cited by in corpus (26)

• Stochastic epidemics in a homogeneous community
• Stochastic epidemics in a heterogeneous community (Part III of the book Stochastic Epidemic Models and Inference)
• Statistical inference for epidemic processes in a homogeneous community (Part IV of the book Stochastic Epidemic Models and Inference)
• Critical window for the configuration model: finite third moment degrees
• An old approach to the giant component problem
• Heavy-tailed configuration models at criticality
• Asymptotic normality of the size of the giant component in a random hypergraph
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• How to determine if a random graph with a fixed degree sequence has a giant component
• Rigid representations of the multiplicative coalescent with linear deletion
• Exploring hypergraphs with martingales
• The augmented multiplicative coalescent and critical dynamic random graph models
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Central limit theorems in the configuration model
• Mesoscopic scales in hierarchical configuration models
• Preferential attachment without vertex growth: emergence of the giant component
• Generating random networks that consist of a single connected component with a given degree distribution
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Eternal multiplicative coalescent is encoded by its Lévy-type processes
• Critical Percolation on Random Networks with Prescribed Degrees
• Percolation on random graphs with a fixed degree sequence
• Tail bounds for the height and width of a random tree with a given degree sequence
• Epidemics on critical random graphs with heavy-tailed degree distribution
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Multiscale genesis of a tiny giant for percolation on scale-free random graphs
• The giant in random graphs is almost local