Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
The diameter and mixing time of critical random graphs

Speaker  Asaf Nachmias

Affiliation  University of California - Berkeley

Host  Yuval Peres

Duration  00:53:39

Date recorded  27 February 2007

Let C1 denote the largest connected component of the critical Erdos-Renyi random graph G(n,1/n). We show that, typically, the diameter of C1 is of order n1/3 and the mixing time of the lazy simple random walk on C1 is of order n. The latter answers a question of Benjamini, Kozma and Wormald.

These results extend to clusters of size n2/3 of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d-1) ≤ 1 + O(n-1/3).

Joint work with Yuval Peres.

©2007 Microsoft Corporation. All rights reserved.
> The diameter and mixing time of critical random graphs