The Kannan-Tetali-Vempala conjecture for simple undirected graphs

For a graphical degree vector $d=(d_1,\dots,d_n)$ , let $\Omega_d$ be the simple undirected graphs on $\{1,\dots,n\}$ with degrees $d$ . The switch chain removes two disjoint edges and inserts a different perfect matching on their four endpoints when both new edges are absent. Kannan, Tetali and Vempala began this program for bipartite graphs and suggested broad applicability; rapid mixing was then proved for regular sequences (Cooper-Dyer-Greenhill) and for P-stable families, and the bipartite case was settled in 2026. The modern form of the conjecture (Erdos, Greenhill, Mezei, Miklos, Soltesz and Soukup, Conjecture 1.1) asks for rapid mixing for every realizable degree sequence in the bipartite, directed and simple undirected models. Does the switch chain on $\Omega_d$ mix in time polynomial in $n$ for every graphical $d$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Markov chain mixing time; sampling graphs with given degrees
Posed by: Ravi Kannan, Prasad Tetali and Santosh Vempala (SODA 1997, RSA 1999); undirected form as Conjecture 1.1 of Erdos, Greenhill, Mezei, Miklos, Soltesz and Soukup (2022)
Year posed: 1997
Years open: 29y
Solved: 2026-09-25
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 30 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Claims Theorem 1.1: for every $n\ge4$ and every graphical labeled degree vector $d$ , the lazy switch chain has total-variation mixing time at most $2n^8$ and, if $|\Omega_d|>1$ , spectral gap at least $[24n^2\binom n4]^{-1}$ . Corollary: an exactly uniform sampler for any graphical $d$ with expected polynomial bit running time, terminating almost surely. This settles the simple undirected formulation; the bipartite formulation was proved earlier by Fu, Qin and Wang (listed separately), and the directed formulation is not addressed. The exponent 8 is not claimed to be sharp.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named.

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction, Theorem 1.1 and Corollary 1.2, read against the conjecture as cited. The proof was not refereed; it adapts the Fu-Qin-Wang variance inequality from the bipartite case. Lean-checked on the release's own Comparator challenge SwitchChain together with its solution module OAI.Probability.SwitchChain.Main, both fetched at the pinned commit; the challenge is not listed in the release's formalization catalogue (lean/formalization.yaml), the statement was read here but not independently audited, and the development was not rebuilt here. The formal statements (OAI.Problem315.switch_chain_main, switch_chain_tv_bound, switch_connectivity) define the lazy kernel exactly as in the paper (holding probability 1/2, a uniform four-set and one of six ordered matching pairs) and state, for n >= 4 and every graphical d, mixing time at distance 1/4 at most 2 n^8, spectral gap at least 1/(24 n^2 C(n,4)) when there is more than one state, and switch connectivity. That is the headline claim. The exact uniform sampler (Corollary 1.2) is not formalized.

The Kannan-Tetali-Vempala conjecture for simple undirected graphs

What was actually shown

What the AI did

Verification

Sources

Discussion