Sampling graphs with given degrees

OpenAI's proof (2026) that the switch chain on simple graphs with given degrees mixes in polynomial time for every graphical degree vector, through the operator inequality H^2 >= H for pair resamplings, and an exact uniform sampler with expected polynomial running time.

Four lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. The switch chain
2. A variance inequality for three rows
3. Disjoint pair resamplings
4. Exact uniform sampling

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Finite Markov chains, eigenvalues of symmetric matrices and conditional expectation.