Rapid mixing of the down-up walk on matchings of a fixed size
| Autor: | Jain, Vishesh, Mizgerd, Clayton |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 12 pages; comments welcome |
| Databáze: | arXiv |
| Externí odkaz: |
|