Mixing time of near-critical random graphs

Abstract

Let ${\mathcal{C}}_1$ be the largest component of the Erdős--Rényi random graph $\mathcal{G}(n,p)$. The mixing time of random walk on ${\mathcal{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 ${\mathcal{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 ${\mathcal{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\to \infty$ and $\lambda =o(n)$, the mixing time on ${\mathcal{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].

Published in at http://dx.doi.org/10.1214/11-AOP647 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Critical random graphs: Diameter and mixing time
• The diameter of sparse random graphs
• Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time
• Component sizes of the random graph outside the scaling window
• Diameters in supercritical random graphs via first passage percolation

Cited by in corpus (4)

• Mixing times for the interchange process
• Bounded-size rules: The barely subcritical regime
• Slightly subcritical hypercube percolation
• Graph-Theoretic Analysis of Belief System Dynamics under Logic Constraints