Mixing time of near-critical random graphs

DOI10.1214/11-AOP647MaRDI QIDQ428137zbMATHFDO

Authors Jian Ding, Eyal Lubetzky, Yuval Peres

Publication date 19 June 2012

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.3870

zbMATH Keywords

random walkmixing timerandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Abstract: Let $mathcal{C}_1$ be the largest component of the ErdH{o}s--R'{e}nyi random graph $mathcalG(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 $lo{g}^{2}n$ by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, $p=(1+varepsilon)/n$ where $lambda=varepsilo{n}^{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+varepsilon)/n$ with $lambda=varepsilo{n}^{3}noinfty$ and $lambda=o(n)$, the mixing time on $mathcal{C}_1$ is with high probability of order $(n/lambda)lo{g}^{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-varepsilon)/n$ with $lambda$ as above].

Recommendations

• Critical random graphs: Diameter and mixing time
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Random walks on the random graph
• Mixing time for random walk on supercritical dynamical percolation
• The mixing time of the giant component of a random graph

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1195779 (Why is no real title available?)
• scientific article; zbMATH DE number 1195781 (Why is no real title available?)
• scientific article; zbMATH DE number 1380601 (Why is no real title available?)
• scientific article; zbMATH DE number 1834589 (Why is no real title available?)
• scientific article; zbMATH DE number 782053 (Why is no real title available?)
• Anatomy of a Young giant component in the random graph
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Component behavior near the critical point of the random graph process
• Component sizes of the random graph outside the scaling window
• Critical random graphs: Diameter and mixing time
• Diameters in supercritical random graphs via first passage percolation
• Faster mixing and small bottlenecks
• Faster mixing via average conductance
• Isoperimetry and heat kernel decay on percolation clusters.
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing times for uniformly ergodic Markov chains
• On the mixing time of a simple random walk on the super critical percolation cluster
• Poisson Cloning Model for Random Graphs
• Probability on trees and networks
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• Random graphs.
• Random walks and the effective resistance of networks
• The Evolution of Random Graphs
• The diameter of sparse random graphs
• The electrical resistance of a graph captures its commute and cover times
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The mixing time of the giant component of a random graph

Cited in

(15)

• Anatomy of the giant component: the strictly supercritical regime
• Random walks on the random graph
• Mixing times of random walks on dynamic configuration models
• Critical random graphs: Diameter and mixing time
• Anatomy of a Young giant component in the random graph
• Hypercube percolation
• On the mixing time of a simple random walk on the super critical percolation cluster
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Mixing Time of the Newman-Watts Small-World Model
• Mixing time of PageRank surfers on sparse random digraphs
• Diameters in supercritical random graphs via first passage percolation
• Convergence of mixing times for sequences of random walks on finite graphs
• Bounded-size rules: the barely subcritical regime
• The mixing time of the giant component of a random graph
• Random walk on sparse random digraphs

This page was built for publication: Mixing time of near-critical random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428137)