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

For a finite graph $G=(V,E)$ let $G^{\ast }$ be obtained by considering a random perfect matching of V and adding the corresponding edges to G with weight $\epsilon$ , while assigning weight 1 to the original edges of G. We consider whether for a sequence $\left(G_n\right)$ of graphs with bounded degrees and corresponding weights $\left({\epsilon }_n\right)$ , the (weighted) random walk on $\left(G_n^{\ast }\right)$ has cutoff. For graphs with polynomial growth we show that $log\left(\frac{1}{{\epsilon }_n}\right)\ll log\left|V_n\right|$ 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}{{\epsilon }_n}\ll log\left|V_n\right|$ is sufficient for cutoff. In the special case of expander graphs we also provide a complete picture for the complementary regime $\frac{1}{{\epsilon }_n}\gtrsim log\left|V_n\right|$ .

The online version contains supplementary material available at 10.1007/s00440-024-01342-9.