The diameter and mixing time of critical random graphs

Опубликовано 7 сентября 2016, 16:54

Let C_1 denote the largest connected component of the critical Erdos-Renyi random graph G(n,1/n). We show that, typically, the diameter of C_1 is of order n^{1/3} and the mixing time of the lazy simple random walk on 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}). Joint work with Yuval Peres.