Edge percolation on a random regular graph of low degree

Simple item page
dc.creatorPittel, Boris
dc.date2008-08-26
dc.date.accessioned2026-07-07T09:58:28Z
dc.date.available2026-07-07T09:58:28Z
dc.descriptionConsider 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 $ω:=n^{1/3}|p-p^*|\to\infty$. If $p<p^*$, then with high probability (whp) the largest component has $O((p-p^*)^{-2}\log n)$ vertices. If $p>p^*$, and $\logω\gg\log\log n$, then whp the largest component has about $n(1-(pπ+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 $π=(pπ+q)^{d-1},π\in(0,1)$. If $ω$ is merely polylogarithmic in $n$, then whp the largest component contains $n^{2/3+o(1)}$ vertices.
dc.descriptionPublished 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)
dc.identifierhttps://arxiv.org/abs/0808.3516
dc.identifierhttp://arxiv.org/abs/0808.3516
dc.identifierAnnals of Probability 2008, Vol. 36, No. 4, 1359-1389
dc.identifierdoi:10.1214/07-AOP361
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167731
dc.subjectProbability
dc.subject05432, 60K35, 82B27, 60G42, 82C20 (Primary)
dc.titleEdge percolation on a random regular graph of low degree
dc.typetext

Files

Collections

arXiv