∑math20

Theoretical computer science · Result 131

Rapid mixing of graph switches for every degree sequence

1 paperLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of Polynomial mixing of the switch chain for every graphical degree sequence

Polynomial mixing of the switch chain for every graphical degree sequence

OpenAI · September 25, 2026

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.

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The Kannan–Tetali–Vempala conjecture asks for polynomial mixing of the switch chain for every graphical degree sequence. The formalization proves the simple undirected case: for \(n\ge4\), the lazy chain that proposes switches on four vertices has total-variation mixing time at distance \(1/4\) at most \(2n^8\). It also proves switch connectivity, the stated exponential total-variation bound, and a spectral gap of at least \(1/(24n^2\binom n4)\) when more than one graph realizes the degree sequence.

The paper's exactly uniform sampling algorithm is outside these selected chain estimates.

Comparator links

ResultComparator statement
Polynomial mixing and connectivity for every graphical degree sequenceSwitchChain.lean

Scope note on GitHub →