Mixing time of near-critical random graphs

DOI10.1214/11-AOP647zbMath1243.05217arXiv0908.3870MaRDI QIDQ428137

Yuval Peres, Eyal Lubetzky, Jian Ding

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 graphsrandom walkmixing time

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)

Related Items

Mixing times of random walks on dynamic configuration models, The mixing time of the giant component of a random graph, Random walk on sparse random digraphs, Random walks on the random graph, Hypercube percolation, Anatomy of the giant component: the strictly supercritical regime, Bounded-Size Rules: The Barely Subcritical Regime

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• Random walks and the effective resistance of networks
• Faster mixing and small bottlenecks
• Critical random graphs: Diameter and mixing time
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The electrical resistance of a graph captures its commute and cover times
• 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
• Faster mixing via average conductance
• Probability on Trees and Networks
• The mixing time of the giant component of a random graph
• Anatomy of a young giant component in the random graph
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Evolution of Random Graphs
• Component behavior near the critical point of the random graph process
• Diameters in Supercritical Random Graphs Via First Passage Percolation
• The Diameter of Sparse Random Graphs
• Poisson Cloning Model for Random Graphs