Switch chain mixes fast?

0:00Random graphs with given degrees

Fix n labeled vertices and a list of degrees: how many neighbours each vertex must have. Usually many simple graphs realize the same list, and drawing one uniformly at random is a basic null model for networks. A natural random walk does it. Pick two edges on four distinct vertices, and if another way of pairing those four vertices uses two absent edges, swap them in. This switch keeps every degree. The question is how many switches it takes before the walk has forgotten where it started. In our check, we built the exact chain for 95 degree lists on 5 to 7 vertices; it always mixed within 129 steps. Kannan, Tetali and Vempala started this program with regular bipartite graphs, and the conjecture that grew from it says the switch chain mixes in polynomial time for every realizable degree list, in the bipartite, directed and simple undirected models. Cooper, Dyer and Greenhill proved it for regular graphs. Later work covered degree lists with quantitative restrictions, and Erdős and coauthors proved it for every family in which nudging the degrees changes the number of graphs by at most a polynomial factor. A 2026 preprint by Fu, Qin and Wang proved the bipartite case. For simple undirected graphs with arbitrary degrees, it was open.

1:23The claim

Result 131 is a single OpenAI preprint, 22 pages, dated September 25. It claims that for every n ≥ 4 and every graphical degree list, the lazy switch chain mixes to within 1/4 in total variation in at most 2n⁸ steps. The chain stays put with probability one half; otherwise it picks four vertices at random and one of the six ordered pairs of distinct perfect matchings on them, switching only if that is valid. When more than one graph has these degrees, its spectral gap is at least 1/(24 n² C(n, 4)). A corollary is an exactly uniform sampler that uses fair coin flips, stops with probability one, and runs in expected polynomial time. The bound is polynomial, and the paper does not claim it is tight. For seven vertices it allows more than 11 million steps, while our chains mixed in at most 129. The directed version of the conjecture is not addressed. OpenAI published a Lean formalization of the mixing bound, the spectral gap, the exponential total-variation bound and switch connectivity, but not of the exact sampler: 165 files and about 23,000 lines with imports, not counting Mathlib. We have not run the Lean check.

2:45How the proof goes

The proof works with bigger moves. Pick a pair of vertices. Every other vertex adjacent to exactly one of them can be handed to the other, as long as each of the two keeps its count. Resample that assignment uniformly: this is the undirected curveball trade. Each trade is a conditional expectation, and H is the sum over all pairs of the part each trade removes. The central estimate is that H squared dominates H, so every nonzero eigenvalue of H is at least one. In our check, H squared minus H never had a negative eigenvalue beyond rounding error, on all 95 degree lists, and every nonzero eigenvalue of H was in fact at least two. Squaring H gives terms for pairs of pairs. Two pairs that share a vertex live inside one triple. Encode that triple’s neighbours as a binary matrix with three rows and fixed row and column sums, adding one column for its internal edges when needed. Then a variance inequality, proved in an equivalent form by Fu, Qin and Wang and reproved here: the variance of a sum of three row functions is at most twice the sum of their variances. Empty and full columns are discarded. Every other column has a single one or a single zero, which picks out a row. The proof first handles those label assignments with the counts fixed, by swapping labels, then handles the counts themselves by a coupling. In our check, the ratio reached two on many random margins, even tiny ones, so the factor two cannot be lowered. Two disjoint pairs are harder: their trades do not commute, because both can rewire the four edges between the pairs. The paper shows that each such interaction is at least a switch term minus two errors, projections onto the event that two neighbours land on the same endpoint. A slice inequality bounds the sum of all those errors by the switch energy available, so the total disjoint contribution is never negative. Collecting terms, H squared is at least the sum of the squared triple terms, minus n − 3 copies of H, and since each pair lies in n − 2 triples, that is at least H. Next, any two graphs with the same degrees are joined by switches, by Havel’s classical realization argument, so the kernel of H is the constants and every variance is at most the energy of H. Each pair trade costs at most n² single swaps in comparison, and every switch arises from exactly two pair trades, so H is at most 2n² times the switch Laplacian. Since each particular switch happens with probability 1/(12 C(n, 4)), the gap follows, and since there are at most 2^C(n, 2) graphs, the mixing time is at most n⁸ + 1, within 2n⁸. In our check, the trades add up to exactly twice the switch Laplacian, and the comparison held with plenty of room.

5:41Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the mixing bound, the spectral gap and connectivity, but not the exact sampler; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the switch chain samples simple graphs with any prescribed degrees, approximately uniformly, in polynomial time, settling the simple undirected case of the Kannan, Tetali and Vempala conjecture. With the bipartite case settled in a recent preprint, the directed case is the one left.