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 $(G_n)$ of graphs with bounded degrees and corresponding weights $({\epsilon }_n)$, the (weighted) random walk on $(G_n^{\ast })$ has cutoff. For graphs with polynomial growth we show that $\log \left(\frac{1}{{\epsilon }_n}\right)\ll \log \mathrm{\mid }{V}_n\mathrm{\mid }$ 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 \mathrm{\mid }{V}_n\mathrm{\mid }$ we show that $\frac{1}{{\epsilon }_n}\ll \log \mathrm{\mid }{V}_n\mathrm{\mid }$ is sufficient for cutoff. In case of expander graphs we also provide a complete picture for the complementary regime $\frac{1}{{\epsilon }_n}\gtrsim \log \mathrm{\mid }{V}_n\mathrm{\mid }$.