Mixing time of near-critical random graphs

DOI10.1214/11-AOP647zbMATH Open1243.05217arXiv0908.3870MaRDI QIDQ428137FDOQ428137

Authors: Jian Ding, Eyal Lubetzky, Yuval Peres 

Publication date: 19 June 2012

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

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].

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

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

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)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Random graphs.
• Probability on trees and networks
• Component behavior near the critical point of the random graph process
• Title not available (Why is that?)
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Random walks and the effective resistance of networks
• The Evolution of Random Graphs
• Poisson Cloning Model for Random Graphs
• Title not available (Why is that?)
• On the mixing time of a simple random walk on the super critical percolation cluster
• Isoperimetry and heat kernel decay on percolation clusters.
• Mixing times for uniformly ergodic Markov chains
• 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
• Faster mixing via average conductance
• The mixing time of the giant component of a random graph
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• Critical random graphs: Diameter and mixing time
• Anatomy of a Young giant component in the random graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Diameters in supercritical random graphs via first passage percolation
• The diameter of sparse random graphs
• Component sizes of the random graph outside the scaling window
• Faster mixing and small bottlenecks

Cited In (15)

• Hypercube percolation
• The Mixing Time of the Newman-Watts Small-World Model
• Critical random graphs: Diameter and mixing time
• Random walk on sparse random digraphs
• Anatomy of the giant component: the strictly supercritical regime
• Anatomy of a Young giant component in the random graph
• Diameters in supercritical random graphs via first passage percolation
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Mixing time of PageRank surfers on sparse random digraphs
• 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
• Mixing times of random walks on dynamic configuration models
• Random walks on the random graph
• On the mixing time of a simple random walk on the super critical percolation cluster

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)