Random graphs with prescribed degrees: a universal switch-chain mixing bound

← All digests

Family 131 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Suppose we know how many connections each vertex of a network has, but want to randomize which vertices are connected. Such random graphs provide a baseline: a feature seen in the original network can be compared with what its degree pattern alone would produce.

A natural procedure repeatedly selects two disjoint edges and rewires their endpoints, preserving every degree. This is the switch chain. It is easy to implement and has the desired uniform distribution as an equilibrium. The harder question is how long it takes to forget its starting graph.

Some degree patterns may seem particularly awkward: a few vertices can have very high degree while others have very low degree, creating constraints that are invisible in regular graphs. A general guarantee must cover every feasible degree vector, not merely a well-behaved class.

This manuscript claims polynomial mixing for all graphical labeled degree vectors in simple undirected graphs, resolving that version of the Kannan–Tetali–Vempala conjecture. It also derives an exactly uniform sampler with expected polynomial bit cost. The latter time guarantee is in expectation, not a bound on every execution.

2. Background and essential definitions

A simple undirected graph has no loops and at most one edge between any two distinct vertices. The degree $d_i$ is the number of neighbors of vertex $i$. A vector $d=(d_1,\ldots,d_n)$ is graphical if at least one such graph realizes it.

Let $\Omega_d$ be the set of graphs on labeled vertices $\{1,\ldots,n\}$ with this exact degree vector. Uniform sampling means assigning probability $1/|\Omega_d|$ to each labeled graph. Graphs that are isomorphic after relabeling are still distinct outcomes when their edge sets differ.

A switch removes disjoint edges, say $ab$ and $cd$, and replaces them by another pairing such as $ac$ and $bd$, provided the new edges are absent. Each of the four vertices loses and gains one edge, so degrees are preserved.

The paper uses a precise lazy chain. With probability one half it does nothing. Otherwise it chooses a four-vertex set uniformly, then one of the six ordered pairs of distinct perfect matchings on those vertices. If the proposed removal edges are present and the proposed insertion edges absent, it performs the switch; otherwise it stays put.

Laziness avoids periodic oscillations. Symmetry of the transition probabilities gives the uniform stationary law $\pi_d$. But stationarity alone does not say how quickly a run approaches it.

The total variation distance between laws $\mu,\nu$ is

$$\|\mu-\nu\|_{\mathrm{TV}} =\frac12\sum_{G\in\Omega_d}|\mu(G)-\nu(G)|.$$

The mixing time used here is the smallest number of steps after which this distance is at most $1/4$, uniformly over the starting graph.

3. Development history and previous partial results

Kannan, Tetali, and Vempala initiated a broad program of sampling degree-constrained graphs by simple Markov chains. The modern conjecture has separate bipartite, directed, and simple-undirected formulations. Establishing one does not automatically establish the others.

For undirected regular graphs, Cooper, Dyer, and Greenhill proved rapid mixing, with a later correction preserving a polynomial guarantee. Their regular-graph analysis and corrigendum form an important early case. Subsequent work treated irregular degrees under quantitative restrictions.

Stability conditions provided another route. Roughly, a family is P-stable when small perturbations of a degree vector do not create vastly more realizations than the original vector, with a polynomial bound uniform across the family. Erdős and coauthors proved rapid mixing for every P-stable family. This covers many useful classes but is an additional hypothesis beyond the feasibility of an individual degree vector.

The source also cites Fu, Qin, and Wang’s 2026 bipartite result, formulated for binary matrices with fixed row and column sums. Its conditional-projection analysis is a methodological starting point. An undirected adjacency matrix must also remain symmetric, so arbitrary matrix resampling cannot simply be imported unchanged.

The pair updates used here belong to the Curveball family of network randomizations. Carstens, Berger, and Strona developed the undirected version. Such updates can interact even when their selected vertex pairs are disjoint. The manuscript’s claimed new estimate controls those interactions in aggregate.

For exact sampling, the source uses the rare residual-mixture method of Göbel, Liu, Manurangsi, and Pappik, with explicit tabulation and bit-cost accounting for this chain.

4. What the new manuscripts claim

For every $n\ge4$ and every graphical labeled degree vector $d$, the stated lazy switch chain satisfies

$$t_{\mathrm{mix}}(d)\le2n^8.$$

This is a worst-start bound at total variation distance $1/4$, measured in the discrete steps defined above. Different implementations that choose proposals in different ways have different step probabilities, so the numerical constant should not be transferred without checking the convention.

When there is more than one realization, the paper gives a spectral-gap lower bound

$$\gamma\ge\frac{1}{24n^2\binom n4}.$$

The spectral gap quantifies the slowest nonconstant mode of relaxation. Together with a bound on the state-space size, it gives the mixing estimate and permits much higher accuracy by running longer.

The exact-sampling corollary covers every finite graphical vector, including fewer than four vertices by direct treatment. One uniform randomized algorithm uses unbiased random bits, terminates almost surely, and returns exactly the uniform law on $\Omega_d$. Its expected bit running time is polynomial in the explicit binary encoding length of the degree vector.

A rare branch may take exponential time, and random integer sampling has unbounded tails. The theorem does not provide a polynomial upper bound on every run. This distinction is part of the claim rather than an implementation detail.

5. Why the advance matters

Provisional importance: 3/5. The result would settle a broad sampling conjecture for the simple-undirected model and justify a basic randomization procedure without regularity or stability assumptions on the degree sequence.

Uniform degree-constrained graphs are widely used as mathematical null models. A general mixing theorem supplies a principled worst-case guarantee that the chain’s stationary distribution is reached at a polynomial rate, rather than relying solely on empirical signs of convergence.

The exact sampler adds a different kind of result: its output has no residual sampling bias. It does so by allowing rare expensive computations, illustrating why exactness, expected time, and worst-case time must be assessed separately.

The rating reflects a substantial advance in graph sampling and Markov-chain analysis. The bound $2n^8$ is not a claim that this many steps are necessary, nor that it is a useful stopping prescription for every real network. Practical convergence can be much faster, and assessing it is a separate task.

6. The main idea

Resample an entire pair of neighborhoods

Instead of analyzing one switch immediately, consider two vertices $i,j$. Keep all edges outside the pair fixed, keep the edge $ij$ fixed, and record for every other vertex whether it is adjacent to zero, one, or both of $i,j$.

Only vertices adjacent to exactly one endpoint can change their assignment. If there are $N$ such vertices and $i$ must receive $q$ of them, the conditional state space is exactly the set of $q$-element subsets of an $N$-element set. Resampling uniformly from this slice preserves simplicity, all degrees, and adjacency-matrix symmetry.

Conditional averaging over such a resampling is a linear projection $E_a$, where $a$ denotes the vertex pair. Set $h_a=I-E_a$, which measures the fluctuation not removed by conditioning, and sum over all pairs:

$$H=\sum_a h_a.$$

The central operator claim is $H^2\succeq H$, meaning that $\langle f,(H^2-H)f\rangle\ge0$ for every real function $f$ on the graph state space. Once only constant functions lie in the kernel, this inequality yields a positive relaxation rate.

Control overlapping and disjoint interactions separately

Expanding $H^2$ produces terms from pairs of updates. If their vertex pairs overlap, the interaction can be represented through a three-row binary matrix with fixed margins. The manuscript controls a variance expression by separating the allocation of labels from the random counts of those labels.

Disjoint vertex pairs present a subtler issue. In an undirected graph they can still interact through edges between the two pairs, so their averaging operators need not commute. Individual contributions can be negative.

The manuscript identifies a restricted form of this dependence and bounds the negative terms by projections associated with assignments on subset slices. Summing over all pairs makes the available positive switch energy compensate for the negative interactions. It then compares the larger neighborhood resamplings with ordinary two-edge switches, retaining the proposal constants needed for the explicit gap.

Correct a tiny residual bias on a rare branch

For exact sampling, first run the chain long enough that its finite-time law $p$ is extremely close to uniform. Choose a small $\delta>0$ so that $(1-\delta)p(G)\le\pi_d(G)$ for every graph. Then

$$r(G)=\frac{\pi_d(G)-(1-\delta)p(G)}{\delta}$$

is a probability law, and $(1-\delta)p+\delta r=\pi_d$ exactly.

Most executions sample from $p$ by running the chain. With probability $\delta$, the algorithm enumerates all realizations and tabulates the rational finite-time law to sample from $r$. The rare branch is expensive, but $\delta$ is chosen small enough that its contribution to expected time is polynomial. The ordinary branch does not need to know the number of realizations.

7. Scope, limitations, and open questions

The host is the complete graph: any edge is allowed as long as degrees and simplicity are respected. Prescribed forbidden edges or an arbitrary host graph can change connectivity and mixing. The theorem does not establish rapid mixing of every host-restricted switch chain.

This also remains the simple-undirected formulation. Directed graphs, bipartite graphs, loops, multiple edges, and unlabeled sampling have different state spaces or proposal rules. Related results may exist, but they are not consequences to attach automatically to this theorem.

The exact sampler’s expected-time guarantee permits extraordinarily rare long runs. Truncating them would generally change the output law unless another correction were provided. Conversely, the mixing theorem directly supports approximate sampling with a controlled finite run length.

Sharper exponents, practical stopping rules, and extensions to restricted hosts remain natural questions. The source’s inequalities and exact-correction construction are reported as stated, without independent proof verification.

8. Sources and further reading

The linked regular-graph and P-stability papers describe the main earlier undirected cases. The bipartite and Curveball papers explain the resampling background, while the perfect-sampling reference explains the residual mixture. Related counting and sampling claims for arbitrary hosts appear in family 113, with different guarantees.

Source manuscripts

• M1. OpenAI, Polynomial mixing of the switch chain for every graphical degree sequence (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.