Spectral gaps for transpositions with forbidden fixed points
We prove that the unit-rate transposition Laplacian on permutations of m >= 4 symbols avoiding t specified fixed points has spectral gap at least max{1, m-min(t,4)}. For the walk that holds with probability 1/2 and otherwise proposes a uniformly chosen transposition, rejecting a forbidden result, the gap is therefore at least max{1, m-min(t,4)}/[2 binom(m,2)]. With exactly two forbidden fixed points, the unit-rate gap is exactly m-2 for every m >= 3. With three it is exactly (3(m-2)-sqrt((m-2)^2+8))/2 for every m >= 4; the matching lower bound uses an exact computer-algebra certificate. The manuscript, its exact verification and the computer-algebra certificate were produced with AI assistance; the release includes written proofs, exact certificates and the ancillary programs.
Authors
- Mark T. Short
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24174780
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint