All Title Author
Keywords Abstract

Mathematics  2007 

Critical random graphs: Diameter and mixing time

DOI: 10.1214/07-AOP358

Full-Text   Cite this paper   Add to My Lib

Abstract:

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})$.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

微信:OALib Journal