Rapid mixing of the down-up walk on matchings of a fixed size

Abstract

Let $G=(V,E)$ be a graph on $n$ vertices and let $m^{\ast }(G)$ denote the size of a maximum matching in $G$. We show that for any $\delta >0$ and for any $1\le k\le (1-\delta )m^{\ast }(G)$, the down-up walk on matchings of size $k$ in $G$ mixes in time polynomial in $n$. Previously, polynomial mixing was not known even for graphs with maximum degree $\Delta$, and our result makes progress on a conjecture of Jain, Perkins, Sah, and Sawhney [STOC, 2022] that the down-up walk mixes in optimal time $O_{\Delta ,\delta }(n\log n)$. In contrast with recent works analyzing mixing of down-up walks in various settings using the spectral independence framework, we bound the spectral gap by constructing and analyzing a suitable multi-commodity flow. In fact, we present constructions demonstrating the limitations of the spectral independence approach in our setting.

12 pages; comments welcome