Edge percolation on a random regular graph of low degree

Abstract

Consider a uniformly random regular graph of a fixed degree $d\ge 3$, 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 }|\to \infty$. If $p<p^{\ast }$, then with high probability (whp) the largest component has $O((p-p^{\ast }{)}^{-2}\log n)$ vertices. If $p>p^{\ast }$, and $\log \omega \gg \log \log n$, then whp the largest component has about $n(1-(p\pi +q{)}^d)\asymp n(p-p^{\ast })$ vertices, and the second largest component is of size $(p-p^{\ast }{)}^{-2}(\log n{)}^{1+o(1)}$, at most, where $\pi =(p\pi +q{)}^{d-1},\pi \in (0,1)$. If $\omega$ is merely polylogarithmic in $n$, then whp the largest component contains $n^{2/3+o(1)}$ vertices.

Published in at http://dx.doi.org/10.1214/07-AOP361 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Percolation on finite graphs and isoperimetric inequalities

Cited by in corpus (6)

• The phase transition in the configuration model
• Giant vacant component left by a random walk in a random d-regular graph
• An old approach to the giant component problem
• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase
• Sharp threshold for percolation on expanders
• Percolation on random graphs with a fixed degree sequence