Critical random graphs: Diameter and mixing time

Original · EN

Let C₁ denote the largest connected component of the critical Erdős--Rényi random graph G(n,1/n). We show that, typically, the diameter of C₁ is of order n¹/³ and the mixing time of the lazy simple random walk on C₁ is of order n. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size n²/³ of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d-1)≤1+O(n⁻¹/³).