Faster mixing and small bottlenecks

DOI10.1007/S00440-006-0003-8zbMATH Open1113.60073OpenAlexW2013770427MaRDI QIDQ863483FDOQ863483

Authors: Nikolaos Fountoulakis, Bruce Reed 

Publication date: 26 January 2007

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00440-006-0003-8

Recommendations

• scientific article; zbMATH DE number 18982
• Vertex and edge expansion properties for rapid mixing
• The rapid mixing of random walks defined by an \(n\)-cube
• scientific article; zbMATH DE number 1195779
• Evolving sets, mixing and heat kernel bounds

zbMATH Keywords

Markov chainmixing timestationary distributionconductance

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Equation of state calculations by fast computing machines
• A critical point for random graphs with a given degree sequence
• Random walks in a convex body and an improved volume algorithm
• Random walks and anO*(n5) volume algorithm for convex bodies
• Polynomial-Time Approximation Algorithms for the Ising Model
• On the mixing time of a simple random walk on the super critical percolation cluster
• Mixing times for uniformly ergodic Markov chains
• Title not available (Why is that?)
• Some Inequalities for Reversible Markov Chains
• Faster mixing via average conductance
• Title not available (Why is that?)
• The random-cluster model on the complete graph
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• Blocking Conductance and Mixing in Random Walks

Cited In (21)

• The mixing time of the Newman-Watts small world
• Smoothed Analysis on Connected Graphs
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• The Mixing Time of the Newman-Watts Small-World Model
• The mixing advantage is less than 2
• Mixing time of near-critical random graphs
• Markov chain mixing time on cycles
• Evolving sets, mixing and heat kernel bounds
• On sensitivity of mixing times and cutoff
• Mixing time bounds via bottleneck sequences
• Intersection conductance and canonical alternating paths: methods for general finite Markov chains
• Sensitivity of mixing times of Cayley graphs
• Expansion in supercritical random subgraphs of expanders and its consequences
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Geometric bounds on the fastest mixing Markov chain
• The mixing time of the giant component of a random graph
• Title not available (Why is that?)
• Sensitivity of mixing times
• Random walks on the random graph
• Speeding up random walk mixing by starting from a uniform vertex

This page was built for publication: Faster mixing and small bottlenecks

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