{"id":"openai-math/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence","pdf":"https://github.com/openai/math/blob/main/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence-September-25-2026","tags":["markov-chains","graph-sampling","combinatorics"],"score":0,"title":"Polynomial mixing of the switch chain for every graphical degree sequence","domain":"Theoretical computer science","family":"131","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-25","reactions":{},"discussion":[{"url":"https://mathoverflow.net/a/515910","date":"2026-10-10","kind":"web","site":"mathoverflow.net","text":"Rapid mixing of graph switches for every degree sequence: I worked on this one in a team. I recall that we were all convinced that it's rapidly mixing. Glad that OpenAI finally proved it!","added":"2026-10-24","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Daniel Soltész"}],"formalized":false,"family_title":"Rapid mixing of graph switches for every degree sequence"}