Critical percolation on random regular graphs

Felix Joos, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

128 Downloads (Pure)

Abstract

We show that for all d ∈ {3,...,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 Θ(n2/3), with high probability. This extends known results for fixed d ≥ 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.
Original languageEnglish
Pages (from-to)3321-3332
JournalProceedings of the American Mathematical Society
Issue number146
Early online date20 Mar 2018
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'Critical percolation on random regular graphs'. Together they form a unique fingerprint.

Cite this