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

For a finite graph \(G=(V,E)\) $G=(V,E)$ let \(G^*\) $G^{\ast }$ be obtained by considering a random perfect matching of V and adding the corresponding edges to G with weight \(\varepsilon \) $\epsilon$ , 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)\) $({\epsilon }_n)$ , the (weighted) random walk on \((G_n^*)\) $(G_n^{\ast })$ has cutoff. For graphs with polynomial growth we show that \(\log \left( \frac{1}{\varepsilon _n}\right) \ll \log |V_n|\) $log\left(\frac{1}{{\epsilon }_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|\) $log|V_n|$ we show that \(\frac{1}{\varepsilon _n}\ll \log |V_n|\) $\frac{1}{{\epsilon }_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|\) $\frac{1}{{\epsilon }_n}\gtrsim log|V_n|$ .