Faster Mixing of the Jerrum-Sinclair Chain

We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}(Δ^2 m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $Δ$, for any constant edge weight $λ>0$. For general graphs with arbitrary, potentially unbounded $Δ$, this provides the first improvement over the classic $\widetilde{O}(n^2 m)$ mixing time bound of Jerrum and Sinclair (1989) and Sinclair (1992). To achieve this, we develop a general framework for analyzing mixing times, combining ideas from the classic canonical path method with the "local-to-global" approaches recently developed in high-dimensional expanders, introducing key innovations to both techniques.