Which chord of an even cycle preserves its spectral gap
Add one edge of conductance $w>0$ to the cycle $C_n$, $n=2m\ge4$, and run the random walk on the resulting weighted graph. We show that the spectral gap of the walk is largest exactly when the new edge joins two antipodal vertices, and that in this case the gap equals $1-\cos(\pi/m)$, the gap of the cycle itself, for every $w$. Every other chord strictly lowers the gap, with an explicit bound. If instead the walk is Metropolized so that its stationary law stays uniform, every chord, antipodal or not, strictly lowers the gap. These are one-edge cases of questions of Diaconis about which added edges speed up a random walk most.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-11
- DOI
- https://doi.org/10.5281/zenodo.24125373
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint