Let $\mathcal{ C}_1$ denote the largest connected component of the critical Erd\H{ o}s--R\'{ e}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)\le1+O(n^{ -1/3})$.

Categories: math.PR math.CO

Critical random graphs: Diameter and mixing time