Edge percolation on a random regular graph of low degree

Details Edge percolation on a random regular graph of low degree Edge percolation on a random regular graph of low degree

2008-08-26

arxiv.org/abs/0808.3516v1

Annals of Probability 2008, Vol. 36, No. 4, 1359-1389

Mathematics

Probability

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

Scientific paper

10.1214/07-AOP361

Consider a uniformly random regular graph of a fixed degree $d\ge3$, 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^*=(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^*$ has width roughly of order $n^{-1/3}$. More precisely, suppose that $p=p(n)$ is such that $\omega:=n^{1/3}|p-p^*|\to\infty$. If $pp^*$, and $\log\omega\gg\log\log n$, then whp the largest component has about $n(1-(p\pi+q)^d)\asymp n(p-p^*)$ vertices, and the second largest component is of size $(p-p^*)^{-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.

Affiliated with

Also associated with

No associations

Rating

Edge percolation on a random regular graph of low degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Edge percolation on a random regular graph of low degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge percolation on a random regular graph of low degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281693