MIXING TIME OF NEAR-CRITICAL RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Ding, Jian; Lubetzky, Eyal; Peres, Yuval
• 署名单位: University of California System; University of California Berkeley; Microsoft
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/11-AOP647
• 发表日期: 2012
• 页码: 979-1008
• 关键词: simple random-walk; giant component; EVOLUTION; diameter; trees

摘要

Let C-1 be the largest component of the Erdos-Renyi random graph G(n, p). The mixing time of random walk on C-1 in the strictly supercritical regime, p = c/n with fixed c > 1, was shown to have order log(2) n by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, p = (1 + epsilon)/n where lambda = epsilon(3)n is bounded, Nachmias and Peres proved that the mixing time on C-1 is of order n. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of C-1 in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper, we show that for p = (1 + epsilon)/n with lambda = epsilon(3)n -> infinity and lambda = 0(n), the mixing time on C-1 is with high probability of order (n/lambda) log(2) lambda. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime [i.e., p = (1 - epsilon)/n with lambda as above].