Critical percolation on random regular graphs

We show that for all d\in \{3,\ldots ,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\geq 3 and for d=n-1, confirming a prediction of Nachmi...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the American Mathematical Society 2018-08, Vol.146 (8), p.3321-3332
Main Authors: JOOS, FELIX, PERARNAU, GUILLEM
Format: Article
Language:English
Subjects:
A. ALGEBRA, NUMBER THEORY, AND COMBINATORICS
Grafs, Teoria de
Graph theory
Matemàtica discreta
Matemàtiques i estadística
Teoria de grafs
Àrees temàtiques de la UPC
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that for all d\in \{3,\ldots ,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\geq 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.
ISSN:0002-9939
1088-6826
DOI:10.1090/proc/14021