Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.26303 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918430454579200 |
|---|---|
| author | Greaves, Gary R. W. Zhu, Haoran |
| author_facet | Greaves, Gary R. W. Zhu, Haoran |
| contents | We establish a sharp lower bound on the spectral gap of the biased adjacent-transposition Markov chain on the symmetric group. As a consequence, we resolve a longstanding conjecture of Fill, proving that among all regular probability vectors, the minimum spectral gap of the transition matrix is attained by the uniform probability vector. We also characterise the regular probability vectors attaining the minimum spectral gap and determine the exact multiplicity of the corresponding second-largest eigenvalue. Our proof relies on a novel algebraic decomposition of the transition matrix into elementary orthogonal projections. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26303 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Spectral gap of biased adjacent-transposition chains Greaves, Gary R. W. Zhu, Haoran Probability Combinatorics We establish a sharp lower bound on the spectral gap of the biased adjacent-transposition Markov chain on the symmetric group. As a consequence, we resolve a longstanding conjecture of Fill, proving that among all regular probability vectors, the minimum spectral gap of the transition matrix is attained by the uniform probability vector. We also characterise the regular probability vectors attaining the minimum spectral gap and determine the exact multiplicity of the corresponding second-largest eigenvalue. Our proof relies on a novel algebraic decomposition of the transition matrix into elementary orthogonal projections. |
| title | Spectral gap of biased adjacent-transposition chains |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2603.26303 |