Edge percolation on a random regular graph of low degree

DOI10.1214/07-AOP361MaRDI QIDQ941299zbMATH OpenOpenAlexFDO

Authors Boris Pittel

Publication date 4 September 2008

Published in The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

Giant componentPercolationRandom graphThreshold probabilityTransition window

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Critical phenomena in equilibrium statistical mechanics (82B27) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Abstract: Consider a uniformly random regular graph of a fixed degree $dge3$, with $n$ vertices. Suppose that each edge is open (closed), with probability $p(q=1-p)$, respectively. In 2004 Alon, Benjamini and Stacey proved that $p^{\ast }=(d-1{)}^{-1}$ is the threshold probability for emergence of a giant component in the subgraph formed by the open edges. In this paper we show that the transition window around $p^{\ast }$ has width roughly of order $n^{-1/3}$. More precisely, suppose that $p=p(n)$ is such that $omega:=n^{1/3}|p-p^{\ast }|oinfty$. If $p<p^{\ast }$, then with high probability (whp) the largest component has $O((p-p^{\ast }{)}^{-2}logn)$ vertices. If $p>p^{\ast }$, and $logomegaggloglogn$, then whp the largest component has about $n(1-(ppi+q{)}^d)asympn(p-p^{\ast })$ vertices, and the second largest component is of size $(p-p^{\ast }{)}^{-2}(logn{)}^{1+o(1)}$, at most, where $pi=(ppi+q{)}^{d-1},piin(0,1)$. If $omega$ is merely polylogarithmic in $n$, then whp the largest component contains $n^{2/3+o(1)}$ vertices.

Review text

Let \(G(n)\) be a random graph uniformly selected from the class of d-regular graphs on \({1,...,n}\). Here d is a fixed integer larger than 2 and n tends to infinity. The edges of \(G(n)\) are independently open with a common probability \(p=p(n)\) and \(G(n,p)\) is the subgraph with open edges in \(G(n)\). The threshold probability for emergence of a giant component in \(G(n,p)\) is \(1/(d-1)\). Conditions on \(p\) are given so that with high probability the order can be determined of the width of the transition window around the threshold.

Recommendations

• The phase transition in the configuration model
• Critical percolation on random regular graphs
• Percolation in general graphs
• Critical percolation on random regular graphs
• The sharp threshold for percolation on expander graphs

Cites work

• A critical point for random graphs with a given degree sequence
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Bootstrap percolation on the random regular graph
• Component behavior near the critical point of the random graph process
• Differential equations for random processes and random graphs
• scientific article; zbMATH DE number 5819433 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• scientific article; zbMATH DE number 195103 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• On a random graph with immigrating vertices: Emergence of the giant component
• On the largest component of the random graph at a nearcritical stage
• On the number of sparse connected graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Random graph dynamics
• Random graphs.
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Some general results concerning the critical exponents of percolation processes
• Sudden emergence of a giant k-core in a random graph
• The asymptotic number of labeled graphs with given degree sequences
• The Asymptotic Number of Unlabelled Regular Graphs
• The birth of the giant component
• The Evolution of Random Graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Structure of a Random Graph at the Point of the Phase Transition

Cited in

(25)

• On percolation in random graphs with given vertex degrees
• On a random graph evolving by degrees
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• An old approach to the giant component problem
• Mean-field conditions for percolation on finite graphs
• Critical window for the vacant set left by random walk on random regular graphs
• The evolution of the cover time
• Critical percolation on random regular graphs
• Dynamics of random graphs with bounded degrees
• The emergence of a giant component in random subgraphs of pseudo-random graphs
• Critical percolation on random regular graphs
• Percolation on random graphs with a fixed degree sequence
• Asymptotics in percolation on high-girth expanders
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Percolation in general graphs
• The sharp threshold for percolation on expander graphs
• The giant component after percolation of product graphs
• The probability of unusually large components for critical percolation on random d-regular graphs
• Locality of random digraphs on expanders
• Percolation on dense random graphs with given degrees
• Sharp threshold for percolation on expanders
• Components, large and small, are as they should be. II: Supercritical percolation on regular graphs of constant degree
• The phase transition in site percolation on pseudo-random graphs
• Expansion properties of a random regular graph after random vertex deletions
• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase

This page was built for publication: Edge percolation on a random regular graph of low degree

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