Rapid mixing of the switch chain for every degree sequence
From OpenAI Aftermath
Rapid mixing of the switch chain for every degree sequence concerns the switch Markov chain on simple graphs with a prescribed degree sequence, which repeatedly replaces two disjoint edges by another perfect matching of their four endpoints when the result is still simple. The Kannan–Tetali–Vempala conjecture, in its modern form, predicts that such chains mix in polynomial time for every realizable degree sequence. A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims this for simple undirected graphs, with an explicit polynomial bound, together with an exactly uniform sampler. The collection includes a Lean formalization of the mixing statements. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Kannan, Tetali and Vempala initiated the switch-chain programme and treated regular bipartite sequences. Cooper, Dyer and Greenhill proved rapid mixing for regular simple graphs, with a corrigendum that keeps a polynomial bound; Feder, Guetz, Mihail and Saberi treated early irregular families, and Greenhill and Sfragara proved rapid mixing under quantitative restrictions on the degrees. Amanatidis and Kleer developed a route through strong stability.
- Erdős, Greenhill, Mezei, Miklós, Soltész and Soukup proved rapid mixing for every P-stable family, building on stability conditions of Jerrum and Sinclair and of Jerrum, McKay and Sinclair; later work of Erdős, Miklós and Soukup and of Erdős, Lippner, Nevo and Soukup gives further P-stable families. The modern conjecture covers the bipartite, directed and simple-undirected models.
- Fu, Qin and Wang proved the bipartite formulation, equivalently the problem for binary matrices with fixed margins. The pair updates used here belong to the Curveball framework of Verhelst, of Strona and coauthors, and of Carstens, Berger and Strona.
The original result
- Claims.
- Theorem 1.1 of Polynomial mixing of the switch chain for every graphical degree sequence states that, for every n ≥ 4 and every graphical degree vector d on n labeled vertices, the lazy chain that proposes a switch on a uniformly chosen set of four vertices has total-variation mixing time at distance 1/4 at most 2n8, and that its spectral gap is at least 1/(24n2·C(n,4)) when more than one graph realizes d.
- Corollary 1.2 states that there is a randomized algorithm, using unbiased random bits, that terminates almost surely and outputs a graph with a given labeled degree vector exactly uniformly, with expected bit running time bounded by a polynomial in the encoding length of the degree vector.
- Method, as described: for each pair of vertices, the neighbours adjacent to exactly one of them are redistributed uniformly between the two, a Curveball-type update. The central estimate is the operator inequality H2 ⪰ H for the sum H of the corresponding projections, proved through the squared-generator method of Caputo: overlapping pairs are controlled by a three-row variance inequality that reproves the inequality of Fu, Qin and Wang's Theorem 5.1, and disjoint pairs by a rank-one interaction bound and a slice comparison. Comparison with individual switches then gives the gap and the mixing time, and the exact sampler corrects the finite-time law of the chain.
- Sources. The manuscript Polynomial mixing of the switch chain for every graphical degree sequence at commit
1581d4c. - Formalization, as described by the repository. The scope note states that the formalization proves the simple undirected case: for n ≥ 4 the lazy four-vertex switch chain has total-variation mixing time at distance 1/4 at most 2n8, together with switch connectivity, the stated exponential total-variation bound and the spectral gap of at least 1/(24n2·C(n,4)) when more than one graph realizes the degree sequence. It states that the exact uniform sampling algorithm is outside these chain estimates. The Comparator statement is
SwitchChain.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | S. J. Robertson, Mixing Times of Switch Chains via High-Dimensional Expansion, arXiv:2610.09506v1 | Related (cites the result) | Proves a mixing-time bound of order Δ2m log m for the classical switch chain and a simplicial variant whenever m ≥ CΔ8, where m is the number of edges and Δ the maximum degree, hence mixing in order n log n steps for bounded maximum degree, which it presents as resolving a conjecture of Cooper, Dyer and Greenhill. Its introduction remarks that OpenAI has announced polynomial mixing for all simple undirected degree sequences, "a claim which is pending verification by the mathematical community". | arXiv preprint, version 1. The manuscript states that ChatGPT-6 assisted with the proofs of the main steps and with copyediting, and that the author developed the overall proof strategy. |
| 2026-10-07 | R. Gounder, Kohze/counting-and-sampling-review, Approximate Counting and Uniform Sampling: A Critical Review of Matroid Intersections, Contingency Tables, and Graph Switch Chains | Review (narrative) | A narrative review of six counting and sampling manuscripts of the collection, including this one. For the switch chain it records the stated mixing bound and exact sampler, and notes that the gap constants of the binary-matrix swap chain and of this simple-undirected chain cannot be exchanged merely because both updates are called switches. | GitHub repository with a manuscript; its LaTeX source includes a dedicated AI disclosure. |
| 2026-10-08 | D. Kiselev, DaniilKi/curveball-error-budget | Application (planning tool) | A software project that turns the collection's operator bound into a conservative sufficient number of Curveball trades for a given degree sequence and error tolerance, with exact arithmetic, a derived gap corollary for the ordinary undirected Curveball chain and scoped Lean reference results. The README states that no speed, accuracy or power advantage, new mixing theorem or new sampler is established, and that a related NetworKit pull request was withdrawn by its author. | GitHub repository (prerelease 0.5.0); a Zenodo software deposit archives version 0.1.0. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full": the mixing-time bound, the spectral gap, the total-variation bound and connectivity are stated, and the exact sampler is not. It notes that mixing is defined by hand, with the mixing time given through Nat.find of an existence proof that is part of the statement. It records a Comparator pass. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K: run 38051470892 and the project's reading record | Verification (two kernels); review (statement reading) | Records that Lean's default kernel and the nanoda kernel accept the SwitchChain solution, in 370 s. The reading record classifies the formal statement as narrower than the manuscript, as declared, and clears a check for degenerate definitions: for n ≥ 4 the transition kernel divides by a positive number and its rows sum to one, and the mixing time defined through Nat.find does not depend on the existence proof supplied. The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions (time-outs, memory, errors) does not list SwitchChain, so it was accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-11 | M. T. Short, sevenevesai/SharpSwitchGap, Sharp spectral gaps for the switch and Curveball chains on every graphical degree sequence (archived at Zenodo 10.5281/zenodo.23295359) | Extension (sharp constants; partly formal) | States spectral gaps of at least 1/(6·C(n,4)) for the switch chain and 2/C(n,2) for the chain performing a Curveball trade on a uniformly chosen vertex pair, both attained for every degree vector with exactly two realizations, and hence mixing times at most n6/4 + 1 and n4/16 + 1, against this manuscript's 1/(24n2·C(n,4)) and 2n8. Both gap bounds are reported as checked by the Lean kernel against the collection's pinned definitions; the equality cases and the mixing-time corollary are listed as not formalized, and the three-row and graph-triple inputs are taken from the collection's formalization. | Preprint with a Lean project; the README states that it has not been peer reviewed and that the manuscript and its Lean verification were produced with AI assistance and reviewed by the author. |
| 2026-10-16 | J. Jardine, Lattice24, referee review in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap and no minor notes. The reviewer states that it read all sections line by line, including the exact sampler, and that brute-force numerical computations for every degree vector with n = 4, 5, 6 and for 278 sorted classes with n = 7 found the smallest nonzero eigenvalue of the operator H equal to 2, with a one-dimensional kernel. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscript.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
