Faster Mixing of the Jerrum-Sinclair Chain

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