Faster Mixing of the Jerrum-Sinclair Chain

We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\tilde{O}({\mathrm{\Delta }}^{2}m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $\mathrm{\Delta }$, for any constant edge weight $\lambda >0$. For general graphs with arbitrary, potentially unbounded $\mathrm{\Delta }$, this provides the first improvement over the classic $\tilde{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.