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

2023/06/22 by Zsuzsanna Baran, Jonathan Hermon, Baran, Zsuzsanna +5
Computer Science · Mathematics · #Advanced Graph Theory Research #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2306.13077

openalex publication_date 2023/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 (G_n) of graphs with bounded degrees and corresponding weights (ε_n), the (weighted) random walk on (G_n^*) has cutoff. For graphs with polynomial growth we show that log((1)/(ε_n))≪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 (1)/(ε_n)≪log|V_n| is sufficient for cutoff. In case of expander graphs we also provide a complete picture for the complementary regime (1)/(ε_n)\gtrsimlog|V_n|.

Related

• Universality of cutoff for graphs with an added random matching
• Cutoff for random lifts of weighted graphs
• Explicit expanders with cutoff phenomena
• Cutoff for mixtures of permuted Markov chains: reversible case
• The phase transition in random graphs - a simple proof