Polynomial mixing of the switch chain for every graphical degree sequence
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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence
curl -X POST /api/v1/records/openai-math/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?mathoverflow.netDaniel SoltészOct 10, 2026
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!