Browse › Theoretical computer science › 131 Rapid mixing of graph switches for every degree sequence
Polynomial mixing of the switch chain for every graphical degree sequence
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove the simple-undirected form of the Kannan–Tetali–Vempala conjecture: the switch chain on simple undirected graphs mixes in polynomial time for every graphical degree sequence. For a lazy chain that proposes switches uniformly on four vertices, the total-variation mixing time at distance 1/4 is at most $2n^8$. We also give an exactly uniform sampler for every graphical labeled degree vector. It uses unbiased random bits, terminates almost surely, and has expected polynomial bit running time.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Rapid mixing of graph switches for every degree sequence: Lean formalization scope (lean/docs/131.md, result family 131, 2026). The release's scope note reports formal proofs of switch connectivity, the exponential total-variation estimate, the mixing-time bound $2n^8$, and the spectral-gap bound $1/(24n^2\binom n4)$, while excluding the exactly uniform sampling algorithm of Corollary 1.2. [family-level]
- OpenAI math release, SwitchChain.lean (Comparator challenge) (lean/ComparatorChallenges, 2026). Comparator statement file containing
switch_chain_main,switch_chain_tv_boundandswitch_connectivity, with proofs left assorryand supplied by the separate development. - OpenAI math release, lean/OAI/Probability/SwitchChain (Lean source directory, 2026). The proof development behind the comparator statements, with modules for the three-row variance step, disjoint-pair estimates, Havel-based connectivity and the mixing-time arithmetic (
Main.lean).
Related prior literature mentioned by others
- Weibo Fu, Qian Qin and Guanyang Wang, Spectral Gap for the Binary Fixed-Margin Swap Chain (arXiv:2606.22636v2, 2026-07-13). The AI Proved What? exposition identifies this bipartite predecessor and its three-row variance inequality as background to the manuscript's undirected argument; it is also cited in the manuscript's bibliography. [AI-generated per source]
Possibly relevant literature (found by the agent, not checked)
- S. J. Robertson, Mixing Times of Switch Chains via High-Dimensional Expansion (arXiv:2610.09506, 7 Oct 2026). Proves $O(\Delta^2 m\log m)$ mixing for the switch chain when $m\ge C\Delta^8$, which can be compared with the paper's uniform bound $t_{\mathrm{mix}}(d)\le 2n^8$ (Theorem 1.1); it does not cite the release.
- K. Tikhomirov and P. Youssef, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs (arXiv:2007.02729, 2020). Gives optimal Poincaré constants for the switch chain in a regular bipartite regime, relevant when comparing the spectral-gap lower bound $[24n^2\binom n4]^{-1}$ in Theorem 1.1 with known sharp gaps.
- P. Gao and C. Greenhill, Mixing time of the switch Markov chain and stable degree sequences (arXiv:2003.08497, 2020). Stability-based rapid-mixing results, including heavy-tailed/power-law sequences, belonging to the line of partial results that the introduction's history paragraph surveys.
- P. L. Erdős, E. Győri, T. R. Mezei, I. Miklós and D. Soltész, Half-graphs, other non-stable degree sequences, and the switch Markov chain (Electron. J. Combin. 28(3) (2021) P3.7). Exhibits non-P-stable families where the switch chain still mixes rapidly, relevant to the paper's point that Theorem 1.1 goes beyond P-stable families.
Digests and expositions
- AI Proved What?, Switch chain mixes fast? (episode 131, October 2026). This video and transcript explain the claimed bounds through Curveball trades, overlapping and disjoint pair estimates, and comparison with individual switches, and report small-instance numerical checks while stating that the authors have not run the Lean check. [AI-generated per source] [family-level]
News and blogs
- Joe Halliwell, Does any of the OpenAI maths have real-world consequences? (blog, 2026-10-08). The section on random networks discusses this paper's relevance to degree-preserving network null models and the gap between its $2n^8$ guarantee and practical simulation budgets; the post credits Claude Opus 5.5 as co-author. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 131
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026,
author = {{OpenAI}},
title = {{Polynomial mixing of the switch chain for every graphical degree sequence}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/main.pdf}{OAI:Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/131.md. The Lean statements have not been checked by people against the paper's claims.
Family 131: Rapid mixing of graph switches for every degree sequence
Resolves the simple-undirected Kannan–Tetali–Vempala conjecture: the lazy edge-switch chain mixes in $O(n^8)$ time for every graphical labeled degree sequence. The same degree-constrained graphs can also be sampled exactly uniformly by an almost-surely terminating algorithm with expected polynomial bit running time.
This is the only paper in this family.