The diameter and mixing time of critical random graphs
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.
Speaker Details
Asaf Nachmias is a Mathematics graduate student at UC Berkeley under the supervision of Prof. Yuval Peres and conducting research in Probability theory and Combinatorics. His current favorite hobby is to cook a wicked stirfry dinner with almost any leftovers in the kitchen, blasting Tom Waits in the background.
- Date:
- Speakers:
- Asaf Nachmias
- Affiliation:
- University of California - Berkeley
-
-
Asaf Nachmias
-
Jeff Running
-