Critical random graphs: Diameter and mixing time

Details Critical random graphs: Diameter and mixing time Critical random graphs: Diameter and mixing time

2007-01-11

arxiv.org/abs/math/0701316v4

Annals of Probability 2008, Vol. 36, No. 4, 1267-1286

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/07-AOP358 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of

Scientific paper

10.1214/07-AOP358

Let $\mathcal{C}_1$ denote the largest connected component of the critical Erd\H{o}s--R\'{e}nyi random graph $G(n,{\frac{1}{n}})$. We show that, typically, the diameter of $\mathcal{C}_1$ is of order $n^{1/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 $n^{2/3}$ of $p$-bond percolation on any $d$-regular $n$-vertex graph where such clusters exist, provided that $p(d-1)\le1+O(n^{-1/3})$.

Affiliated with

Also associated with

No associations

Rating

Critical random graphs: Diameter and mixing time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Critical random graphs: Diameter and mixing time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical random graphs: Diameter and mixing time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642945