Universality of cutoff for graphs with an added random matching

DOI10.1214/21-AOP1532zbMath1486.05278arXiv2008.08564OpenAlexW3052291153MaRDI QIDQ2119210

Allan Sly, Perla Sousi, Jonathan Hermon

Publication date: 23 March 2022

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

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

zbMATH Keywords

entropycutoffmixing timerandom graphquasi trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random walks on graphs (05C81)

Related Items

Markov chains on finite fields with deterministic jumps, Speeding up random walk mixing by starting from a uniform vertex, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, Mixing time of fractional random walk on finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Total variation and separation cutoffs are not equivalent and neither one implies the other
• Cutoff on all Ramanujan graphs
• Some things we've learned (about Markov chain Monte Carlo)
• An entropic proof of cutoff on Ramanujan graphs
• Cutoff phenomena for random walks on random regular graphs
• Cutoff at the ``entropic time for sparse Markov chains
• Random walks on the random graph
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• The smallest eigenvalue for reversible Markov chains
• Markov chain decomposition for convergence rate analysis
• Biased random walks on Galton-Watson trees
• Cutoff for nonbacktracking random walks on sparse random graphs
• Speeding up Markov chains with deterministic jumps
• Comparing mixing times on sparse random graphs
• Cutoff for Ramanujan graphs via degree inflation
• Random walk on sparse random digraphs
• A threshold for cutoff in two-community random graphs
• Mixing time of the Chung-Diaconis-Graham random process
• Random doubly stochastic tridiagonal matrices
• The cutoff phenomenon for random birth and death chains
• Anatomy of a young giant component in the random graph
• Shuffling Cards and Stopping Times
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure