Critical random graphs: Diameter and mixing time

Abstract

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})\).