Critical random graphs: Diameter and mixing time

Abstract

Let ${\mathcal{C}}_1$ denote the largest connected component of the critical Erdős--Rényi random graph $G(n,\frac{1}{n})$. We show that, typically, the diameter of ${\mathcal{C}}_1$ is of order $n^{1/3}$ and the mixing time of the lazy simple random walk on ${\mathcal{C}}_1$ is of order $n$. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size $n^{2/3}$ of $p$-bond percolation on any $d$-regular $n$-vertex graph where such clusters exist, provided that $p(d-1)\le 1+O(n^{-1/3})$.

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

References in corpus (4)

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• The Evolution of the Mixing Rate
• Random subgraphs of the 2D Hamming graph: the supercritical phase
• Critical percolation on random regular graphs

Cited by in corpus (1)

• The continuum limit of critical random graphs