Rapid mixing of graph switches for every degree sequence

Random rewiring reaches a fair random network quickly, for every possible list of degrees.

1 paper September 25, 2026 Explained by AI

A switch rewires two lines of a network so every dot keeps its number of lines. Repeating random switches eventually picks each network with those degrees equally often. This paper proves the wait is at most 2n⁸ steps for n dots, whatever the degree list (Lean proof listed). It also claims an exact sampler with polynomial average running time.

First step

1999

Kannan, Tetali and Vempala, the switch-chain program

Significance

Major

It settles the simple-network case of a conjecture that earlier work met only for restricted degree families.

Trust

Formal proof listed

Field

Theoretical computer science

1 paper

The explanation

Draw six dots and give each one exactly two lines to other dots. The list of line counts, 2 at every dot, is called a degree sequence. A dot's degree is just its number of lines. There are exactly 70 ways to draw such a network on six labelled dots. In 60 of them, the lines form one loop through all six dots. In the other 10, they form two separate triangles.

Now suppose you want one of those 70 networks at random, each equally likely. Scientists want this for real networks too. A random network with the same degrees is a basic baseline to compare a real network against. A degree list is called graphical when at least one simple network has it. Simple means no dot links to itself and no two dots share two lines.

A popular method never lists the options. It starts from any valid network and keeps making small random changes called switches. A switch removes two lines that share no dot and joins their four dots the other way. Take triangles 1-2-3 and 4-5-6. Remove lines 1–2 and 4–5, then add 1–4 and 2–5. Every dot keeps its two lines. The network is now one loop: 1-3-2-5-6-4-1. A switch is skipped if a new line already exists.

The paper's exact version works like this. Each step, it stays put with probability one halfSource 1. Otherwise it picks four dots at random and tries a random rewiring of them. Repeated over and over, this is a random walk called the switch chain. In the long run it lands on all valid networks equally often. The question is how long the run must be. The mixing time is the number of steps until the odds are nearly even. Here nearly even means at most one quarter of the probability sits in the wrong places.

I worked the six-dot example out exactly. From the worst starting network, 38 steps are enough. The paper's guaranteed limit is 2n⁸ steps, where n is the number of dotsSource 2. For six dots, that is 3,359,232 steps. The limit is very generous here. Its value is that it grows only like a fixed power of n. Such growth is called polynomial, and it counts as fast in this field.

This method has a long history. Kannan, Tetali and Vempala started the switch-chain program in a 1999 paper. They handled regular bipartite cases, where every dot has the same degree and lines run only between two sides. Cooper, Dyer and Greenhill showed fast mixing for regular simple networks in 2007. Later work covered irregular degrees under number limits. In 2022, Erdős and five coauthors covered every P-stable family. P-stable roughly means small nudges to the degrees never change the network count too wildly. Each result needed a whole family of degree lists to behave wellSource 3. The conjecture said fast mixing should hold for every graphical list. In 2026, Fu, Qin and Wang proved the bipartite version.

The one obstacle in the simple case is symmetrySource 4. A network's table of links reads the same across rows and down columns. The bipartite method reshuffles rows of a table freely, and that breaks the symmetry. This paper reshuffles neighbours between two chosen dots instead, which keeps the table symmetric. Reshuffles on separate pairs of dots can still interfere with each other. The paper shows that one interaction can push the wrong way, yet all of them together never doSource 5.

The result proves fast mixing for every graphical degree list on at least four dotsSource 2. It needs no condition on the list beyond being graphical. It covers only simple, undirected networks, not networks whose lines have directions. The limit is a guarantee, not a practical speed. For 100 dots, 2n⁸ is 20 million billion steps. The paper also claims an exact samplerSource 6. It always outputs each valid network with exactly equal chance. It stops with probability one, and its average running time is polynomialSource 7. No polynomial limit is claimed for every single run.

How sure is this? A computer proof checker called Lean has checked a formal version of the mixing limit. Lean also checked that switches connect every pair of valid networks, plus a related spectral-gap bound. The exact sampler is outside that check. No specialist review has been published yet.

What it doesn't show. This does not cover networks whose lines have directions, and it gives no practical step count.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if it holds. Lean checked the mixing limit, but the exact sampler is outside that check. The 2n⁸ limit is far from practical, and no specialist review is published.

Words used

Degree sequence: The list giving how many lines touch each dot of a network.
Graphical: A degree list that at least one simple network actually has.
Simple network: A network with no line from a dot to itself and no doubled lines.
Switch: Removing two lines with no shared dot and joining their four dots the other way.
Switch chain: A random walk that repeatedly tries random switches on a network.
Mixing time: How many steps a random walk needs before its odds are nearly even.
Polynomial: Growing no faster than a fixed power of the size, such as n⁸.
P-stable: A family of degree lists where small nudges never change the network count too wildly.

The original paper

Polynomial mixing of the switch chain for every graphical degree sequence (PDF, opens in a new tab)
September 25, 2026

Lean notes

All quoted lines (7)

With probability $1/2$ the chain stays at its current graph. Otherwise it chooses a four-element set $S\subseteq V$ uniformly, and then chooses uniformly one of the six ordered pairs $(F,F')$ of distinct perfect matchings of the complete graph on $S$ .
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
For every $n\ge4$ and every graphical degree vector $d$ , $t_{\mathrm{mix}}(d)\le 2n^8.$
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
These results explain substantial classes of degrees; the theorem here requires only that the individual degree vector be graphical.
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
A simple undirected graph has a symmetric adjacency matrix, so an arbitrary binary-matrix resampling does not preserve its state space. Our pair resamplings preserve that symmetry by redistributing neighbors between two vertices.
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
The additional estimate here gives quantitative control of those interactions: although an individual disjoint-pair term may be negative, their full sum is positive semidefinite.
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
There is a uniform randomized algorithm that, given any finite graphical labeled degree vector $d=(d_1,\ldots,d_n)$ , uses unbiased random bits, terminates almost surely, and outputs a graph chosen exactly uniformly from the simple undirected graphs on $\{1,\ldots,n\}$ with labeled degree vector $d$ .
Polynomial mixing of the switch chain for every graphical degree sequence Back to text
The time bound is in expectation; no polynomial bound on every random execution is asserted.
Polynomial mixing of the switch chain for every graphical degree sequence Back to text