Faster Mixing of the Jerrum-Sinclair Chain
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912307630571520 |
|---|---|
| author | Chen, Xiaoyu Feng, Weiming Ju, Zhe Miao, Tianshun Yin, Yitong Zhang, Xinyuan |
| author_facet | Chen, Xiaoyu Feng, Weiming Ju, Zhe Miao, Tianshun Yin, Yitong Zhang, Xinyuan |
| contents | We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}(Δ^2 m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $Δ$, for any constant edge weight $λ>0$. For general graphs with arbitrary, potentially unbounded $Δ$, this provides the first improvement over the classic $\widetilde{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02740 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Mixing of the Jerrum-Sinclair Chain Chen, Xiaoyu Feng, Weiming Ju, Zhe Miao, Tianshun Yin, Yitong Zhang, Xinyuan Data Structures and Algorithms Discrete Mathematics Probability We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}(Δ^2 m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $Δ$, for any constant edge weight $λ>0$. For general graphs with arbitrary, potentially unbounded $Δ$, this provides the first improvement over the classic $\widetilde{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. |
| title | Faster Mixing of the Jerrum-Sinclair Chain |
| topic | Data Structures and Algorithms Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2504.02740 |