
Speaker Asaf Nachmias Affiliation University of California  Berkeley Host Yuval Peres Duration 00:53:39 Date recorded 27 February 2007 Let C_{1} denote the largest connected component of the critical ErdosRenyi 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 pbond percolation on any dregular nvertex graph where such clusters exist, provided that p(d1) ≤ 1 + O(n^{1/3}). Joint work with Yuval Peres.
©2007 Microsoft Corporation. All rights reserved.
By the same speakerPeople also watched 