Critical random graphs: Diameter and mixing time
Nachmias, Asaf ; Peres, Yuval
Ann. Probab., Tome 36 (2008) no. 1, p. 1267-1286 / Harvested from Project Euclid
Let $\mathcal{C}_{1}$ 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 $\mathcal{C}_{1}$ is of order n1/3 and the mixing time of the lazy simple random walk on $\mathcal{C}_{1}$ 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).
Publié le : 2008-07-15
Classification:  Percolation,  random graphs,  random walk,  mixing time,  05C80,  82B43,  60C05
@article{1217360969,
     author = {Nachmias, Asaf and Peres, Yuval},
     title = {Critical random graphs: Diameter and mixing time},
     journal = {Ann. Probab.},
     volume = {36},
     number = {1},
     year = {2008},
     pages = { 1267-1286},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1217360969}
}
Nachmias, Asaf; Peres, Yuval. Critical random graphs: Diameter and mixing time. Ann. Probab., Tome 36 (2008) no. 1, pp.  1267-1286. http://gdmltest.u-ga.fr/item/1217360969/