Critical percolation on random regular graphs

Abstract

We show that for all $d\in \{3,\dots ,n-1\}$ the size of the largest component of a random $d$-regular graph on $n$ vertices around the percolation threshold $p=1/(d-1)$ is $\Theta (n^{2/3})$, with high probability. This extends known results for fixed $d\ge 3$ and for $d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method.

10 pages

References in corpus (3)

• Critical random graphs: Diameter and mixing time
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Percolation on random graphs with a fixed degree sequence