Probability Theory and Related Fields Statistics, Probability and Uncertainty

Phase transition for random walks on graphs with added weighted random matching

Zsuzsanna Baran, Jonathan Hermon, Anđela Šarković, Perla Sousi
Springer Nature · 2024-11-28 · DOI 10.1007/s00440-024-01342-9

Abstract

Abstract For a finite graph $$G=(V,E)$$ G = ( V , E ) let $$G^*$$ 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)$$ ( G n ) of graphs with bounded degrees and corresponding weights $$(\varepsilon _n)$$ ( ε n ) , the (weighted) random walk on $$(G_n^*)$$ ( G n ∗ ) has cutoff. For graphs with polynomial growth we show that $$\log \left( \frac{1}{\varepsilon _n}\right) \ll \log |V_n|$$ log 1 ε n ≪ 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|$$ log | V n | we show that $$\frac{1}{\varepsilon _n}\ll \log |V_n|$$ 1 ε n ≪ 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|$$ 1 ε n ≳ log | V n | .

Read at publisher →