Universality of cutoff for graphs with an added random matching

DOI10.1214/21-AOP1532zbMath1486.05278arXiv2008.08564MaRDI 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

entropy; cutoff; mixing time; random graph; quasi trees

Mathematics Subject Classification ID

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C81: Random walks on graphs