Metraipolis › archive › dc_8f46ac136fa0

Mixing Times of Switch Chains via High-Dimensional Expansion — arXiv:2610.09506

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09506
License (as archived)
CC0-1.0
Archived
2026-10-08T12:43:08.683Z
SHA-256 of the archived text
564322d505d101a10448265ad57aff74f3124b597e55a8081ad26197931dd01b
Stable URL of this page
https://metraipolis.com/documento/dc_8f46ac136fa0

How to cite

Mixing Times of Switch Chains via High-Dimensional Expansion — arXiv:2610.09506 — arXiv (en), https://arxiv.org/abs/2610.09506 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8f46ac136fa0 (Metraipolis archive dc_8f46ac136fa0, sha256 564322d505d101a10448265ad57aff74f3124b597e55a8081ad26197931dd01b)
BibTeX
@misc{dc8f46ac136fa0,
  title = {Mixing Times of Switch Chains via High-Dimensional Expansion — arXiv:2610.09506},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09506},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8f46ac136fa0; sha256 564322d505d101a10448265ad57aff74f3124b597e55a8081ad26197931dd01b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09506. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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(\Delta^{2}m\log m)$ bound on the mixing time of both simplicial and classical switch chains whenever $m\ge C\Delta^{8}$, where $m$ is the number of edges, $\Delta$ 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(n\log n)$ steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.09506 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:30.197Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).