Phase transition for random walks on graphs with added weighted random matching
Open Access
- 28 November 2024
- journal article
- research article
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 193 (3-4) , 989-1074
Abstract
For a finite graph $$G=(V,E)$$ let $$G^*$$ be obtained by considering a random perfect matching of V and adding the corresponding edges to G with weight $$\varepsilon $$ , while assigning weight 1 to the original edges of G . We consider whether for a sequence $$(G_n)$$ of graphs with bounded degrees and corresponding weights $$(\varepsilon _n)$$ , the (weighted) random walk on $$(G_n^*)$$ has cutoff. For graphs with polynomial growth we show that $$\log \left( \frac{1}{\varepsilon _n}\right) \ll \log |V_n|$$ is a sufficient condition for cutoff. Under the additional assumption of vertex-transitivity we establish that this condition is also necessary. For graphs where the entropy of the simple random walk grows linearly up to some time of order $$\log |V_n|$$ we show that $$\frac{1}{\varepsilon _n}\ll \log |V_n|$$ is sufficient for cutoff. In the special case of expander graphs we also provide a complete picture for the complementary regime $$\frac{1}{\varepsilon _n}\gtrsim \log |V_n|$$ .
Keywords
All Related Versions
Funding Information
- DPMMS EPSRC Doctoral Training Partnership
- Natural Sciences and Engineering Research Council of Canada
- DPMMS EPSRC International Doctoral Scholarship
- Trinity Internal Graduate Studentship
This publication has 25 references indexed in Scilit:
- A Finitary Structure Theorem for Vertex-Transitive Graphs of Polynomial GrowthCombinatorica, 2021
- CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHSJournal of the Institute of Mathematics of Jussieu, 2021
- Mixing time of the Chung–Diaconis–Graham random processProbability Theory and Related Fields, 2020
- Speeding up Markov chains with deterministic jumpsProbability Theory and Related Fields, 2020
- Cutoff at the “entropic time” for sparse Markov chainsProbability Theory and Related Fields, 2018
- Markov Chains and Mixing Times2017
- Introduction to Random Graphs2015
- Anatomy of a young giant component in the random graphRandom Structures & Algorithms, 2010
- Stein’s method for concentration inequalitiesProbability Theory and Related Fields, 2006
- Evolving sets, mixing and heat kernel boundsProbability Theory and Related Fields, 2005