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

Abstract

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 |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|$ we show that $\frac{1}{{\epsilon }_n}\ll \log |V_n|$ 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 |V_n|$.

We added Theorem 1.7, a new result regarding more general graphs $(G_n)$, added Section 7 presenting some conjectures about more general graphs and a sketch proof of Theorem 1.7, and made some further smaller changes