Graph switches with prescribed degrees

Source and verification

This article explains family 131 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Degree-constrained graphs and switches

A labeled degree vector $d=(d_1,\dots ,d_n)$ is graphical if some simple undirected graph on $\{1,\dots ,n\}$ has those degrees. Let ${\Omega }_d$ be the set of all such graphs, and let ${\pi }_d$ be the uniform distribution on that finite nonempty set. Labels are retained: graphs related by a relabeling are generally different outcomes.

A switch removes two disjoint edges and replaces them by another perfect matching on their four vertices, provided the two new edges are absent. For example,

$$\{12,34\}⟼\{13,24\}$$

preserves every degree. The absence condition prevents multiple edges, and four distinct vertices prevent loops.

The manuscript uses a precise lazy chain. With probability $1/2$, stay put. Otherwise choose a four-element vertex set uniformly and then one of the six ordered pairs of distinct perfect matchings on it. Perform the indicated switch if legal; reject the proposal otherwise. Write $P$ for this transition matrix. Every pair of distinct neighboring graphs has transition probability

$$P(G,G^{\prime })=\frac{1}{12\left(\genfrac{}{}{0ex}{}{n}{4}\right)}.$$

Reversing the switch gives the same probability. Thus $P$ is reversible with respect to ${\pi }_d$. The holding probability removes periodicity, while switch connectivity, discussed below, gives irreducibility. (OpenAI, 2026)

For probability measures $\mu ,\nu$ on ${\Omega }_d$, their total variation distance is

$$\begin{array}{rl}& \Vert \mu -\nu {\Vert }_{\mathrm{TV}}\\ & =\frac{1}{2}\sum _{G\in {\Omega }_d}|\mu (G)-\nu (G)|.\end{array}$$

The mixing time at distance $1/4$ is the least integer $t$ for which $P^t(G,\cdot )$ is within $1/4$ of ${\pi }_d$ for every starting graph $G$.

🏷️ Mixing and exact sampling statements

Source theorem for every graphical degree vector

For $n\ge 4$, the chain above satisfies

$$t_{\mathrm{mix}}(d)\le 2n^8.$$

If $|{\Omega }_d|>1$, its spectral gap is at least

$${\gamma }_0=\frac{1}{24n^2\left(\genfrac{}{}{0ex}{}{n}{4}\right)}.$$

There is also an exactly uniform sampler using unbiased random bits, with almost-sure termination and expected bit running time polynomial in the explicit binary input length. (OpenAI, 2026)

The spectral gap is $1$ minus the largest eigenvalue of $P$ on mean-zero functions. The theorem concerns all graphical sequences, without a regularity, maximum-degree, or stability assumption. Its host graph is complete: the state space contains every simple graph with the specified degrees. It does not assert rapid mixing for switch chains restricted to arbitrary host graphs.

The exact sampler has an expected runtime guarantee. Its rare correction branch can be exponentially expensive, and unbiased rejection draws have unbounded tails. This differs from a sampler with a polynomial bound on every execution and a small nonzero distributional error. If ${\Omega }_d$ is a singleton, mixing time is zero; vectors with fewer than four entries can be enumerated directly for sampling.

🏷️ A four-vertex calculation

For $d=(1,1,1,1)$, the state space consists of the three perfect matchings

$$\begin{array}{c}A=\{12,34\},B=\{13,24\},\\ C=\{14,23\}.\end{array}$$

From each state, each of the other two has transition probability $1/12$. Therefore

$$P=\left(\begin{array}{ccc}5/6& 1/12& 1/12\\ 1/12& 5/6& 1/12\\ 1/12& 1/12& 5/6\end{array}\right).$$

The constant vector has eigenvalue $1$; both mean-zero directions have eigenvalue $3/4$. Starting from $A$,

$$P^t(A,\cdot )-{\pi }_d=(3/4{)}^t({\delta }_A-{\pi }_d),$$

so the total variation distance is $(2/3)(3/4{)}^t$ and the mixing time is exactly $4$. This elementary calculation checks the proposal normalization. It also shows that the universal $2n^8$ bound is a worst-case guarantee, not an estimate of typical convergence time.

🏷️ Pair resampling as an orthogonal projection

Instead of analyzing individual switches directly, fix a vertex pair $a=\{u,v\}$. Keep all edges away from that pair, the edge $uv$, and the set of vertices adjacent to both or neither endpoint. The remaining vertices are adjacent to exactly one endpoint. Redistribute those neighbors uniformly between $u$ and $v$, subject to their fixed degrees.

If there are $N$ such neighbors and $q$ must be assigned to $u$, the conditional space is the uniform subset slice

$$\{S\subseteq [N]:|S|=q\}.$$

Let $E_a$ average a function over this conditional space, and put

$$h_a=I-E_a,H=\sum _{a\in \left(\genfrac{}{}{0ex}{}{[n]}{2}\right)}{h}_a.$$

Under the inner product $⟨f,g⟩={\mathbb{E}}_{{\pi }_d}[fg]$, conditional expectation is an orthogonal projection. Hence $h_a^2=h_a$, and $⟨f,h_{a}f⟩$ is the expected conditional variance left after fixing the pair’s preserved data.

The central source estimate is

$$H^2⪰H,$$

where $A⪰B$ means $⟨f,(A-B)f⟩\ge 0$ for every real $f$. A nonnegative eigenvalue $\lambda$ of $H$ must then satisfy ${\lambda }^2\ge \lambda$, so it is either zero or at least one. To convert this into a useful gap, one must identify the kernel and prove the operator estimate globally.

🏷️ Triple estimates and disjoint-pair interactions

For a three-vertex set $T$, write $H_T={\sum }_{a\subset T}{h}_a$. The manuscript proves a local inequality $H_T^2⪰H_T$ by converting the conditional graph space into a three-row binary-matrix space with fixed margins.

Columns record adjacency to vertices outside $T$. Internal edges must also be represented: with one internal edge, an extra column marks its two endpoints; with two internal edges, it marks the middle vertex of the path. Empty and complete internal graphs require no extra column. This gives a bijection with the full conditional matrix space, preserving uniform measure and the relevant resampling operators.

The three-row input is a variance inequality. For centered functions $g_i$ of row $i$,

$$\mathrm{Var}\left(\sum _{i=1}^3{g}_i\right)\le 2\sum _{i=1}^3\mathrm{Var}(g_i).$$

To see its operator consequence, let $P_{i}f$ denote conditioning on row $i$ within a fixed conditional cell, and set $b={\sum }_i\Vert P_{i}f{\Vert }_2^2$. For centered $f$,

$$\begin{array}{rl}b& =⟨f,\sum _i{P}_{i}f⟩\\ & \le \Vert f{\Vert }_2\sqrt{2b},\end{array}$$

so $b\le 2\Vert f{\Vert }_2^2$. Since conditioning on the third row is exactly resampling the other two,

$$⟨f,H_{T}f⟩=3\Vert f{\Vert }_2^2-b\ge \Vert f{\Vert }_2^2.$$

This proves the triple gap. The source proves the row variance inequality by separating assignments of column labels from their random counts; it is not an independence assertion about rows. (OpenAI, 2026)

Now expand the full square. Let $D$ be the sum of $h_a{h}_b$ over ordered disjoint pairs $a,b$. Each vertex pair belongs to $n-2$ triples, while each ordered pair of intersecting distinct pairs belongs to exactly one triple. Therefore

$$H^2=\sum _{|T|=3}{H}_T^2-(n-3)H+D.$$

Disjoint vertex pairs do not make their resamplings independent: the edges between the pairs couple the updates. Individual contributions to $D$ can have negative quadratic forms. The source’s second essential estimate is positivity of the whole sum, $D⪰0$.

The proof conditions on preserved data, reduces one interaction to at most rank-one dependence, and bounds its negative part by projections onto centered indicators that two neighbors receive the same endpoint. A slice comparison controls the sum of those projections by available switch energy. This collective accounting supplies $D⪰0$; commutation of disjoint updates cannot simply be assumed.

Combining the two inputs gives

$$H^2⪰(n-2)H-(n-3)H=H.$$

The triple variance and disjoint-sum positivity are the substantial local source theorems behind this short final calculation.

🏷️ Connectivity, comparison, and the mixing bound

Switch connectivity can be proved by transforming every graph to one deterministic degree realization. In the remaining unfrozen vertices, select the first vertex $v$, and prescribe its neighbors to be those with largest residual degrees, breaking ties by label.

If an undesired neighbor $i$ is present and a desired neighbor $j$ is absent, then $d_j\ge d_i$ within the remaining graph. Removing a possible edge $ij$ from both neighborhood counts preserves this inequality. Since $v$ is a neighbor of $i$ but not $j$, there must be another vertex $k$ adjacent to $j$ but not $i$. The switch

$$\{vi,jk\}⟼\{vj,ik\}$$

improves $v$‘s neighborhood without disturbing frozen vertices. Freeze $v$ once its prescribed neighbors are attained and repeat. The prescription depends only on the current residual degree vector, so all starting graphs reach the same graph.

If $Hf=0$, every conditional variance vanishes, so $f$ is constant on each pair-resampling space. Every switch belongs to such a space, and connectivity makes $f$ constant globally. Thus the operator gap gives

$${\mathrm{Var}}_{{\pi }_d}(f)\le ⟨f,Hf⟩.$$

Let $L$ be the unnormalized Laplacian of the switch graph, with each distinct switch neighbor counted once. On a subset slice, decompose a permutation into at most $N\le n$ transpositions and apply Cauchy–Schwarz along that path. This bounds full resampling variance by $n^2$ times the sum of transposition energies. Every graph switch appears in exactly two pair-resampling descriptions, giving

$$H⪯2n^{2}L,I-P=\frac{L}{12\left(\genfrac{}{}{0ex}{}{n}{4}\right)}.$$

The claimed gap ${\gamma }_0$ follows. Laziness ensures nonnegative eigenvalues, so contraction on the centered subspace gives

$$\Vert P^t(G,\cdot )-{\pi }_d{\Vert }_{\mathrm{TV}}\le \frac{1}{2}\sqrt{|{\Omega }_d|}{e}^{-{\gamma }_{0}t}.$$

Here the square root comes from the $L^2({\pi }_d)$ norm of a point-mass density, followed by Cauchy–Schwarz. Since $|{\Omega }_d|\le 2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ and ${\gamma }_0^{-1}\le n^6$, the time needed to reduce this bound to $1/4$ is at most $n^8+1\le 2n^8$. (OpenAI, 2026)

🏷️ Exactness through a rare correction

Finite-time mixing yields an approximate law $p$, not exactly ${\pi }_d$. The source obtains exactness by making $p$ sufficiently accurate that

$$(1-\delta )p(G)\le {\pi }_d(G)$$

pointwise. Then the residual

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

is a probability distribution, and $(1-\delta )p+\delta r={\pi }_d$ exactly.

For the cost calculation, put $B=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, $D=4B+10$, and $\delta =2^{-D}$. The spectral estimate reaches total variation at most ${\delta }^2$ in $O(n^8)$ steps. Writing $M=|{\Omega }_d|$, we have $M\delta \le 1$, and therefore

$$\begin{array}{rl}(1-\delta )p(G)& \le (1-\delta )(1/M+{\delta }^2)\\ & \le 1/M.\end{array}$$

The ordinary branch runs the chain. Only the branch of probability $\delta$ enumerates all graphs and tabulates $p$ exactly. This is feasible as a finite rational calculation: with $q=12\left(\genfrac{}{}{0ex}{}{n}{4}\right)$, the matrix $qP$ has integer entries, and $p$ has denominator $q^t$ after $t$ steps. Dense propagation over at most $2^B$ states costs $2^{2B}\mathrm{poly}(n)$ bit operations; numerator bit lengths remain polynomial because $t$ is polynomial.

The rare branch contributes at most

$$\delta 2^{2B}\mathrm{poly}(n)=2^{-2B-10}\mathrm{poly}(n)$$

to expected work. Exact uniform integer draws from unbiased bits implement both rational distributions, with almost-sure termination. This argument requires exact tabulation of the implemented approximate law; knowing only that it is close to uniform is insufficient. (OpenAI, 2026)

🏷️ Key steps and proof outlines

Isolating the only dependent four-vertex configuration

The gap proof uses conditional expectation operators $E_a$ for resampling a vertex pair $a$, and orthogonal projections $h_a=I-E_a$. For disjoint pairs $a=\{i,j\}$ and $b=\{k,l\}$, the cross term $⟨h_{a}f,h_{b}f⟩$ need not be positive. “Disjoint-pair interactions” identifies its entire negative part inside a two-dimensional space.

Condition on the graph outside these four vertices, their internal pair edges, and each outside vertex’s neighbor counts into each pair. The remaining data are a binary $2\times 2$ cross-edge matrix $M$, an outside assignment set $U$ for $i$, and an outside assignment set $W$ for $k$. Let $s$ be the total number of cross edges, $r$ the first row sum, and $c$ the first column sum. The degrees impose $|U|=q_0-r$ and $|W|=q_1-c$, for fixed conditional parameters $q_0,q_1$. The sets $U,W$ may overlap because they describe different edges.

The $a$-resampling invariants are $X=(c,W)$ and the $b$-resampling invariants are $Y=(r,U)$. For $s=0,1,3,4$, these variables are independent under the conditional uniform law. The only nontrivial case is $s=2$, with six possible cross matrices. Their multiplicities by row and column sum are:

$r\backslash c$	$0$	$1$	$2$
$0$	$0$	$1$	$0$
$1$	$1$	$2$	$1$
$2$	$0$	$1$	$0$

Outside assignment counts can change the probabilities, but they preserve this support pattern. In particular, the events $D_r=\{r\ne 1\}$ and $D_c=\{c\ne 1\}$ are disjoint. This small table locates the dependency that a general commutativity argument would miss. (OpenAI, 2026)

A rank-one dependence calculation

Let $p_r,p_c$ be the probabilities of those events. When both are positive, normalize their centered indicators:

$$u=\frac{1_{D_c}-p_c}{\sqrt{p_c(1-p_c)}},v=\frac{1_{D_r}-p_r}{\sqrt{p_r(1-p_r)}}.$$

Disjointness gives $⟨u,v⟩=-\rho$, where

$$\rho =\sqrt{\frac{p_c{p}_r}{(1-p_c)(1-p_r)}}\in (0,1).$$

The strict upper bound follows from positive probability at the center. If either event has probability zero, the corresponding dependence disappears. The source proves that all centered dependence between functions of $X$ and functions of $Y$ is carried by these two indicators: $E_{a}v=-\rho u$ and $E_{b}u=-\rho v$, while the remaining centered subspaces are orthogonal.

For the component $f=xu+yv$ in their span,

$$h_{a}f=y(v+\rho u),h_{b}f=x(u+\rho v),$$

and therefore

$$2⟨h_{a}f,h_{b}f⟩=2xy\rho (1-{\rho }^2)\ge -(x^2+y^2)(1-{\rho }^2).$$

The inequality follows from $2|xy|\le x^2+y^2$ and $\rho <1$. It supplies an explicit error bound rather than asserting that the two projections commute.

Negative terms are paid by retained positive energy

The line spanned by $v+\rho u=v-E_{a}v$ has a concrete interpretation on an $a$-fiber: it is the centered indicator that the two singleton neighbors $k,l$ are assigned to the same endpoint of $a$. Let $R_{a,b}$ project onto the corresponding fiberwise line. The reverse line is contained in the range of $R_{b,a}$. Projection onto a containing subspace has greater squared norm, so these two operators bound the negative plane contribution.

On the orthogonal complement of functions of $X$ and $Y$, both $h_a$ and $h_b$ act as the identity. The cross-edge switch projection $g_{a,b}$ lies in that complement, producing the useful positive term. Together these facts give

$$2⟨h_{a}f,h_{b}f⟩\ge 2\Vert g_{a,b}f{\Vert }^2-\Vert R_{a,b}f{\Vert }^2-\Vert R_{b,a}f{\Vert }^2.$$

The following slice comparison proves, for each fixed $a$, that the sum of $\Vert R_{a,b}f{\Vert }^2$ over disjoint $b$ is at most the corresponding sum of $\Vert g_{a,b}f{\Vert }^2$. Summing the displayed inequality therefore cancels the errors globally. This is why the proof retains the positive switch energy instead of discarding it in a local lower bound. Combined with the separate overlapping-pair calculation, it yields $H^2\ge H$ for $H={\sum }_a{h}_a$, the operator inequality feeding the subsequent comparison to the actual switch chain. (OpenAI, 2026)

🏷️ Reading connections

Contingency-table sampling develops the same approximate-law and residual-mixture distinction in another finite state space. Perfect-matching counting treats broader counting and prescribed-degree sampling interfaces; those guarantees do not by themselves imply rapid mixing of a particular local chain.

🏷️ Manuscripts and verification scope

• Polynomial mixing of the switch chain for every graphical degree sequence — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Its selected comparators cover connectivity, the spectral gap, and mixing estimates. The exactly uniform sampling algorithm is outside that documented selection. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Polynomial mixing of the switch chain for every graphical degree sequence.