You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Critical Random Graphs: Diameter and Mixing Time
Contributor:
Nachmias, Asaf;
Peres, Yuval
Published:
Institute of Mathematical Statistics, 2008
Published in:
The Annals of Probability, 36 (2008) 4, Seite 1267-1286
Language:
English
ISSN:
0091-1798
Origination:
Footnote:
Description:
Let [Unrepresented Character]₁ denote the largest connected component of the critical Erdős-Rényi random graph $G(n, \frac{1}{n})$. We show that, typically, the diameter of [Unrepresented Character]₁ is of order $n^\sfrac{1}{3}$ and the mixing time of the lazy simple random walk on [Unrepresented Character]₁ is of order n. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size $n^\sfrac{2}{3}$ of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that $p(d-1) \lesseqgtr 1 + O(n^\sfrac{-1}{3})$.