Rapid mixing of the down-up walk on matchings of a fixed size
<|reference_start|>Rapid mixing of the down-up walk on matchings of a fixed size: Let $G = (V,E)$ be a graph on $n$ vertices and let $m^*(G)$ denote the size of a maximum matching in $G$. We show that for any $\delta > 0$ and for any $1 \leq k \leq (1-\delta)m^*(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.<|reference_end|>
@article{jain2024rapid,
    title={Rapid mixing of the down-up walk on matchings of a fixed size},
    author={Vishesh Jain and Clayton Mizgerd},
    journal={arXiv preprint arXiv:2408.03466},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.03466},
    primaryClass={cs.DS math.CO}
}