Mixing Times of Switch Chains via High-Dimensional Expansion
Abstract
The switch chain is a Markov chain defined on the set of labelled realizations of a given graphical degree sequence. At each step, a pair of vertex-disjoint edges is chosen at random and the process attempts to replace them with a uniformly chosen perfect matching of the same four vertices, rejecting any proposal that would create a multiple edge. The resulting process is reversible with respect to the uniform distribution on all realizations. We investigate the mixing time of this chain by viewing realizations as the facets of a simplicial complex and studying a variant of the original process called the simplicial switch chain, which we analyze using tools from the theory of high-dimensional expansion. Our technical contributions include a proof that links of faces of sufficiently high codimension are strong spectral expanders and a comparison between the Dirichlet energies of large block updates and two-edge updates. Our main result is an O(Δ2mlog m) bound on the mixing time of both simplicial and classical switch chains whenever m≥ CΔ8, where m is the number of edges, Δ is the maximum prescribed degree, and C>0 is an absolute constant. For sequences on n vertices with fixed maximum degree, this proves that the chain mixes in O(nlog n) steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.
Related
- Stability of quasi-stationary measures in high-dimensional products of mixing Markov chains
- Very high genus double Hurwitz numbers via mixing times
- Rapid mixing of quantum spin chains at any finite temperature
- From Ehrenfest to Heisenberg scales: a hierarchy of mixing times for a phase-randomized quantum baker walk
- Boundary control for optimal mixing by two-dimensional second-grade fluids
BibTeX
@misc{robertson2026mixing,
title = {{Mixing Times of Switch Chains via High-Dimensional Expansion}},
author = {Sawyer Jack Robertson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09506},
eprint = {2610.09506},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09506},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Mixing Times of Switch Chains via High-Dimensional Expansion
AU - Sawyer Jack Robertson
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09506
UR - https://arxiv.org/abs/2610.09506
AB - The switch chain is a Markov chain defined on the set of labelled realizations of a given graphical degree sequence. At each step, a pair of vertex-disjoint edges is chosen at random and the process attempts to replace them with a uniformly chosen perfect matching of the same four vertices, rejecting any proposal that would create a multiple edge. The resulting process is reversible with respect to the uniform distribution on all realizations. We investigate the mixing time of this chain by viewing realizations as the facets of a simplicial complex and studying a variant of the original process called the simplicial switch chain, which we analyze using tools from the theory of high-dimensional expansion. Our technical contributions include a proof that links of faces of sufficiently high codimension are strong spectral expanders and a comparison between the Dirichlet energies of large block updates and two-edge updates. Our main result is an O(Δ^2mlog m) bound on the mixing time of both simplicial and classical switch chains whenever m≥ CΔ^8, where m is the number of edges, Δ is the maximum prescribed degree, and C>0 is an absolute constant. For sequences on n vertices with fixed maximum degree, this proves that the chain mixes in O(nlog n) steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.
ER -