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 | .
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: