Critical random graphs: Diameter and mixing time

• 成果类型: Article
• 署名作者: Nachmias, Asaf; Peres, Yuval
• 署名单位: University of California System; University of California Berkeley; Microsoft
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/07-AOP358
• 发表日期: 2008
• 页码: 1267-1286
• 关键词: phase-transition; trees

摘要

Let C-1 denote the largest connected component of the critical Erdos-Renyi random graph G(n, 1/n). We show that, typically, the diameter of C-1 is of order n(1/3) and the mixing time of the lazy simple random walk on 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) <= 1 + O(n(-1/3)).