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

ABSTRACT: For a finite graph G=(V,E) let G∗ be obtained by considering a random perfect matching of V and adding the corresponding edges to G with weight ε , while assigning weight 1 to the original edges of G. We consider whether for a sequence (Gn) of graphs with bounded degrees and corresponding weights (εn) , the (weighted) random walk on (Gn∗) has cutoff. For graphs with polynomial growth we show that log1εn≪log|Vn| 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|Vn| we show that 1εn≪log|Vn| is sufficient for cutoff. In the special case of expander graphs we also provide a complete

SUBMITTER: Baran Z 

PROVIDER: S-EPMC12680896 | biostudies-literature | 2025

REPOSITORIES: biostudies-literature