64c3814
==== TABLE OF CONTENTS ====
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//disjoint.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//exact-sampling.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//introduction.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//main.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//mixing.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//references.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//rows.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//setup.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//slice.tex
Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//triples.tex
===========================
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//disjoint.tex ====
\section{Disjoint pair resamplings}
\label{dis:section}
The resamplings indexed by disjoint vertex pairs need not commute:
they both alter the four edges between the two pairs. Carstens, Berger,
and Strona already noted this dependence of undirected
trades~\cite[Section~2.3 of the arXiv version]{CBS18}. We show that
one interaction is bounded below by a cross-edge switch term minus two
errors. Each error is a projection onto an equal-assignment indicator
in one pair fiber. Section~\ref{sl:section} will bound the sum of these
errors by the available switch energy.
For disjoint vertex pairs $a,b$, let $T_{a,b}$ toggle the four edges between
$a$ and $b$ when their $2$-by-$2$ cross matrix has every row and column sum
one, and leave the graph unchanged otherwise. This map is a degree-preserving
involution, and hence acts as a self-adjoint isometry on functions. Define
\begin{equation}
g_{a,b}=\frac{I-T_{a,b}}2=g_{b,a}.
\label{sl:def-cross}
\end{equation}
Thus $g_{a,b}$ is an orthogonal projection.
Fix an $a$-fiber $\mathcal F$, and write $b=\{k,l\}$. If both $k$ and $l$
are singleton vertices in this fiber, let $x_k,x_l$ indicate assignment to
the first endpoint of $a$, and set
\begin{equation}
z_{kl}^{\mathcal F}
=\mathbf 1_{\{x_k=x_l\}}
-\mathbb P(x_k=x_l\mid\mathcal F).
\label{sl:def-equality}
\end{equation}
On $\mathcal F$, define $R_{a,b}$ to be orthogonal projection onto the span
of $z_{kl}^{\mathcal F}$, or zero if this function is zero. If either vertex
is not a singleton, also use the zero operator. Taking the direct sum over
all $a$-fibers defines an orthogonal projection $R_{a,b}$ on the graph
space. Unlike $g_{a,b}$, this projection is directed: $R_{a,b}$ and
$R_{b,a}$ use different fibers. Its definition is independent of the chosen
ordering of the two endpoints of $a$.
\begin{proposition}[Disjoint-pair interaction]\label{dis:interaction}
For disjoint vertex pairs $a,b$ and every real function $f$ on
$\Omega_d$,
\begin{equation}\label{dis:bound}
2\langle h_a f,h_b f\rangle
\ge 2\|g_{a,b}f\|^2
-\|R_{a,b}f\|^2-\|R_{b,a}f\|^2.
\end{equation}
\end{proposition}
\begin{proof}
Write $a=\{i,j\}$ and $b=\{k,l\}$, with $i$ and $k$ the first
endpoints in the orders used to define the slice projections, and put
$O=V\setminus(a\cup b)$. Partition $\Omega_d$ by recording the graph
on $O$, the edges $ij,kl$, and, separately for each $w\in O$, its
numbers of neighbors in $a$ and in $b$. Both pair resamplings preserve
these data. In particular, each full $a$-fiber or $b$-fiber is contained
in a cell of this partition. We prove the inequality on each nonempty
cell, using its conditional uniform measure throughout.
\paragraph{The cell and its two conditional expectations.}
Let $A_0,B_0\subseteq O$ be the outside vertices with exactly one
neighbor in $a,b$, respectively. A graph $G$ in the cell is encoded by
\[
M=\begin{pmatrix}
\mathbf 1_{\{ik\in E(G)\}}&\mathbf 1_{\{il\in E(G)\}}\\
\mathbf 1_{\{jk\in E(G)\}}&\mathbf 1_{\{jl\in E(G)\}}
\end{pmatrix},
\qquad U\subseteq A_0,\qquad W\subseteq B_0,
\]
where $U$ contains those outside singletons assigned to $i$, and $W$
those assigned to $k$. The total $s$ of the four entries of $M$ is fixed
by the sum of the degrees in $a$ and the recorded data. Set
\[
r=M_{ik}+M_{il},\qquad c=M_{ik}+M_{jk}.
\]
For fixed integers $q_0,q_1$, the remaining degree constraints are
exactly
\begin{equation}\label{dis:sizes}
|U|=q_0-r,\qquad |W|=q_1-c.
\end{equation}
Indeed, these equations enforce the degrees of $i,k$; the degrees of
$j,l$ then follow from the fixed pair totals. Each outside degree is
already enforced by the recorded graph and counts. This also proves
that every binary matrix of total $s$ and every pair of subsets
satisfying \eqref{dis:sizes} give a valid graph in the cell. The sets
$A_0,B_0$ may overlap: the two assignments use different edges and
preserve the two recorded neighbor counts separately. Thus overlap
adds no constraint. All these encodings have the same probability.
Within the cell, the full $a$-fiber data are equivalent to
$X=(c,W)$. Namely, $c$ and $s-c$ specify the counts from $k,l$ to $a$,
and $W$ specifies all remaining edges not incident to $a$. Together
with the cell data this is exactly the defining information of an
$a$-fiber. Similarly, the full $b$-fiber data are $Y=(r,U)$. Therefore
\begin{equation}\label{dis:conditional}
E_a=\mathbb E[\,\cdot\mid X],\qquad
E_b=\mathbb E[\,\cdot\mid Y].
\end{equation}
Let $\mathcal A,\mathcal B$ be the subspaces of functions of $X,Y$,
respectively, with constants included, and let
$\mathcal J=(\mathcal A+\mathcal B)^\perp$.
The involution defining $g_{a,b}$ preserves $X$ and $Y$. Hence its
antisymmetric projection kills both subspaces, and, by
self-adjointness,
\begin{equation}\label{dis:g-range}
\operatorname{ran}g_{a,b}\subseteq\mathcal J.
\end{equation}
\paragraph{Independent cases.}
If $s=0$ or $s=4$, the cross matrix is fixed and $X,Y$ are independent.
If $s=1$ or $s=3$, every feasible combination of its row total $r$ and
column total $c$ determines a unique matrix: it specifies the position
of its unique one or its unique zero. Since the subset restrictions
in \eqref{dis:sizes} are separate, $X,Y$ again have a product law.
For $s=2$, all six cross matrices appear in the following display,
placed according to their first row sum $r$ and first column sum $c$:
\begin{equation}\label{dis:table}
\begin{array}{c|ccc}
&c=0&c=1&c=2\\ \hline
r=0&\varnothing&
\begin{psmallmatrix}0&0\\1&1\end{psmallmatrix}&\varnothing\\[8pt]
r=1&\begin{psmallmatrix}0&1\\0&1\end{psmallmatrix}&
\begin{psmallmatrix}1&0\\0&1\end{psmallmatrix},\quad
\begin{psmallmatrix}0&1\\1&0\end{psmallmatrix}&
\begin{psmallmatrix}1&0\\1&0\end{psmallmatrix}\\[8pt]
r=2&\varnothing&
\begin{psmallmatrix}1&1\\0&0\end{psmallmatrix}&\varnothing
\end{array}.
\end{equation}
Let $m_{rc}$ count the matrices in cell $(r,c)$ of this display:
$m_{11}=2$, the four adjacent cells have count one, and the corners
have count zero. Write $D_r=\{r\ne1\}$ and $D_c=\{c\ne1\}$.
The top and bottom matrices realize $D_r$, and the side matrices
realize $D_c$, so the two events are disjoint. Call $r=c=1$ the center;
its two matrices are exchanged by $T_{a,b}$. If both events have positive
probability, the center is feasible: occurrence of $D_r$ implies
feasibility of a subset $W$ of size $q_1-1$, and occurrence of $D_c$
implies feasibility of a subset $U$ of size $q_0-1$. Together these
subsets realize either central matrix. Thus, if the center is absent,
at most one of the events occurs, and the support lies in a single
row or column of \eqref{dis:table}; the law of $X,Y$ is a product.
If the center is present but one of the events has probability zero,
the same conclusion holds. For example, if $r=1$ always, then $U$ is
uniform of fixed size, independently of $c,W$; the multiplicity in
\eqref{dis:table} depends only on $c$.
Whenever $X,Y$ are independent, both $E_aE_b$ and $E_bE_a$ equal the
projection onto constants in the cell. Consequently $h_a h_b$ is the
orthogonal projection onto $\mathcal J$, and
\[
2\langle h_a f,h_b f\rangle
=2\|\operatorname{proj}_{\mathcal J}f\|^2
\ge 2\|g_{a,b}f\|^2
\]
by \eqref{dis:g-range}. This is stronger than \eqref{dis:bound}.
\paragraph{The remaining correlation has rank one.}
It remains to consider $s=2$ when both events and the center have
positive probability. Put $p_r=\mathbb P(D_r)$ and
$p_c=\mathbb P(D_c)$, and define centered unit vectors
\[
u=\frac{\mathbf 1_{D_c}-p_c}{\sqrt{p_c(1-p_c)}}\in\mathcal A,
\qquad
v=\frac{\mathbf 1_{D_r}-p_r}{\sqrt{p_r(1-p_r)}}\in\mathcal B.
\]
Their correlation is
\begin{equation}\label{dis:rho}
\langle u,v\rangle=-\rho,\qquad
\rho=\sqrt{\frac{p_cp_r}{(1-p_c)(1-p_r)}}\in(0,1),
\end{equation}
since $D_r,D_c$ are disjoint and $1-p_c-p_r$ is the positive center
probability.
With the counts $m_{rc}$ associated with \eqref{dis:table}, for every
occurring $X=(c,W)$ and each feasible subset $U$ of size $q_0-r$,
\[
\mathbb P\bigl(Y=(r,U)\mid X=(c,W)\bigr)
=\frac{m_{rc}}{\displaystyle\sum_{t=0}^2
\binom{|A_0|}{q_0-t}m_{tc}},
\]
where a binomial coefficient is zero when its lower index is outside
$\{0,\ldots,|A_0|\}$. Thus the conditional law of $Y$ given $X$
depends only on whether $c=1$. When $c\ne1$, necessarily $r=1$ and
$U$ is uniform of size $q_0-1$; when $c=1$, the displayed formula has
no dependence on $W$.
Symmetrically, the conditional law of $X$ given $Y$ depends only on
whether $r=1$. It follows that
\[
E_a\mathcal B\subseteq\operatorname{span}(1,u),\qquad
E_b\mathcal A\subseteq\operatorname{span}(1,v),\qquad
E_a v=-\rho u,\quad E_b u=-\rho v.
\]
Let $\mathcal A'$ be the centered functions in $\mathcal A$
orthogonal to $u$, and define $\mathcal B'$ symmetrically. The
conditional-expectation inclusions show that
$\mathcal A'\perp\mathcal B$ and $\mathcal B'\perp\mathcal A$.
We therefore have the orthogonal decomposition
\begin{equation}\label{dis:decomposition}
\operatorname{span}(1)\ \oplus\ \mathcal A'\ \oplus\
\mathcal B'\ \oplus\ \operatorname{span}(u,v)\ \oplus\ \mathcal J.
\end{equation}
All these summands are invariant under $E_a,E_b$. The first three
contribute zero to $\langle h_a f,h_b f\rangle$, and $\mathcal J$
contributes $\|\operatorname{proj}_{\mathcal J}f\|^2$.
On the plane in \eqref{dis:decomposition}, write the component of
$f$ as $xu+yv$. Its images under $h_a$ and $h_b$, respectively, are
\[
y(v+\rho u),\qquad x(u+\rho v).
\]
The parenthesized vectors have squared norm $1-\rho^2$ and mutual
inner product $\rho(1-\rho^2)$. Hence the plane contribution obeys
\begin{equation}\label{dis:plane}
2xy\rho(1-\rho^2)
\ge -(x^2+y^2)(1-\rho^2)
=-\|y(v+\rho u)\|^2-\|x(u+\rho v)\|^2.
\end{equation}
Here $2|xy|\le x^2+y^2$ and $0<\rho<1$ justify the inequality
for either sign of $xy$.
\paragraph{The error lines belong to the slice projections.}
The vector $y(v+\rho u)$ is the orthogonal projection of the full
function $f$ onto the line spanned by $v+\rho u$: the spanning vector is
orthogonal to $u$, has inner product $1-\rho^2$ with $v$, and
all other summands of \eqref{dis:decomposition} are orthogonal to
the plane. The symmetric assertion holds for $x(u+\rho v)$.
We claim that the first line belongs to
$\operatorname{ran}R_{a,b}$. Examine
$v+\rho u=v-E_a v$ on each $X$-slice, which, by
\eqref{dis:conditional}, is a full global $a$-fiber. If $c\ne1$,
then $D_r$ is deterministically false and this difference is zero.
If $c=1$, both $k,l$ are singleton vertices for the pair $a$.
Moreover, $D_r$ occurs exactly when their assignments to the two
endpoints of $a$ are equal. Writing these assignments as $x_k,x_l$,
on this fiber we have
\[
v-E_a v=
\frac{\mathbf 1_{\{x_k=x_l\}}-
\mathbb P(x_k=x_l\mid X)}{\sqrt{p_r(1-p_r)}}.
\]
This is a scalar multiple of the centered function defining
$R_{a,b}$, including when that function vanishes. Thus the line
belongs to its fiberwise direct-sum range. Likewise the other line
belongs to $\operatorname{ran}R_{b,a}$. Orthogonal projection onto
a subspace has no larger norm than projection onto a containing
subspace: if $\Pi$ projects onto a line contained in
$\operatorname{ran}R$, then $\Pi R=\Pi$ and
$\|Rf\|^2\ge\|\Pi Rf\|^2=\|\Pi f\|^2$. Consequently
\[
\|y(v+\rho u)\|^2\le\|R_{a,b}f\|^2,\qquad
\|x(u+\rho v)\|^2\le\|R_{b,a}f\|^2.
\]
Combining these inequalities with \eqref{dis:plane} and
\eqref{dis:g-range} proves \eqref{dis:bound} on the cell.
Finally, $E_a,E_b,g_{a,b}$ preserve the cells. So do $R_{a,b}$ and
$R_{b,a}$, since their defining full pair fibers are contained in
the cells. Averaging the conditional inequalities proves the
asserted global inequality.
\end{proof}
We retain the positive term in Proposition~\ref{dis:interaction} to
control the two directed error terms after summation. The estimate needed for that step is, for each fixed $a$,
\[
\sum_{b:\,b\cap a=\varnothing}\|R_{a,b}f\|^2
\le \sum_{b:\,b\cap a=\varnothing}\|g_{a,b}f\|^2.
\]
We prove this estimate next, using the uniform subset structure of
each $a$-fiber.
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//disjoint.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//exact-sampling.tex ====
\section{Exact uniform sampling}
\label{sec:exact-sampling}
We use the rare residual-mixture construction of G\"obel, Liu,
Manurangsi, and Pappik~\cite[Section~3.1, Algorithm~1 and
Theorem~6]{GLMP2024}. Their Corollary~15 computes the approximate law
by powers of the transition matrix. Exact tabulation is also used in
the contingency-table sampler~\cite[Sections~6.3--6.4]{OpenAIContingency2026}. Here we
establish the tabulation and bit-cost bounds directly for the rational
switch chain.
The idea is to sample from a very accurate finite-time law $p$ most of
the time, and to correct its remaining bias on a rare branch. For a
suitably small $\delta>0$, we will have $(1-\delta)p\le\pi_d$ pointwise.
Then
\[
r=\frac{\pi_d-(1-\delta)p}{\delta}
\]
is a probability law, and the mixture $(1-\delta)p+\delta r$ is exactly
$\pi_d$. Only the branch of probability $\delta$ enumerates the state
space and tabulates $p$ to sample from $r$. We choose $\delta$
exponentially small enough to pay for that enumeration in expectation;
the chain still reaches the required accuracy in polynomially many
steps.
\begin{proof}[Proof of Corollary~\ref{cor:exact-sampling}]
We use the usual explicit binary encoding of the degree vector, with
delimiters between its entries. Let $n$ be the number of entries of
$d$. For $n<4$,
enumerate the at most $2^3$ simple graphs and retain those with the
specified labeled degrees. The unbiased integer draw described below
samples uniformly from this nonempty constant-size set. We may
therefore assume $n\ge4$ and use the notation of
Section~\ref{sec:introduction}. Havel's greedy degree-realization
procedure~\cite{Havel55}, with deterministic tie-breaking, constructs
one graph $G_0\in\Omega_d$ in polynomial bit time.
\paragraph{An accurate rational law.}
Set
\begin{equation}\label{exact:parameters}
\begin{gathered}
B=\binom n2,\qquad M=|\Omega_d|\le2^B,\qquad
q=12\binom n4,\\
D=4B+10,\qquad \delta=2^{-D},\qquad
t=\left\lceil\gamma_0^{-1}(B+2D+2)\right\rceil,
\end{gathered}
\end{equation}
where $\gamma_0=[24n^2\binom n4]^{-1}$ is from
Equation~\eqref{mix:gamma}. Thus $D=O(n^2)$ and $t=O(n^8)$.
Write $p_G=P_d^t(G_0,G)$. If $M>1$, Equation~\eqref{mix:TV} gives
\[
\|p-\pi_d\|_{\mathrm{TV}}
\le\frac12\sqrt M\,e^{-\gamma_0t}
\le\frac12\,2^{B/2}e^{-(B+2D+2)}
\le2^{-2D}=\delta^2.
\]
The last inequality follows from $2<e$ and $B,D\ge0$.
If $M=1$, then $p=\pi_d$, so the same bound holds.
Applying total variation to the singleton event $\{G\}$ gives
$p_G\le1/M+\delta^2$. Since $M\delta\le2^{B-D}\le1$,
\begin{equation}\label{exact:domination}
(1-\delta)p_G
\le\frac{1-\delta}{M}+(1-\delta)\delta^2
\le\frac1M
\qquad(G\in\Omega_d).
\end{equation}
The parameters in Equation~\eqref{exact:parameters}, apart from the
analytical quantity $M$, are computable from $n$ in polynomial bit
time. The ordinary sampling branch below does not need to know $M$.
For distinct $G,H$, the proof of Theorem~\ref{thm:main} shows that
$qP_d(G,H)$ is one for switch neighbors and zero otherwise. The row
sum identity gives
\[
qP_d(G,G)=q-\bigl|\{H\ne G:H\text{ is a switch neighbor of }G\}\bigr|,
\]
which is also a nonnegative integer. Hence $A=qP_d$ is a
nonnegative integer matrix whose rows sum to $q$. Starting with the
integer point mass $a^{(0)}$ at $G_0$, define
\begin{equation}\label{exact:law}
a^{(s+1)}=a^{(s)}A\quad(0\le s<t).
\qquad
p_G=\frac{a_G^{(t)}}{q^t},
\qquad
\sum_{G\in\Omega_d}a_G^{(t)}=q^t.
\end{equation}
All numerators are nonnegative integers.
We can tabulate this law exactly when needed. Enumerate all $2^B$
adjacency bit strings and retain exactly those whose labeled degrees
are $d$; this also computes $M$. Each degree test has polynomial bit
cost. For every retained pair of graphs, the switch-neighbor test and
the corresponding entry of $A$ are computable in polynomial bit time.
Dense propagation in Equation~\eqref{exact:law} uses at most $tM^2$
integer multiply-add operations. At step $s$, every numerator and
every partial nonnegative sum is at most $q^s$ or $q^{s+1}$,
respectively. Their bit lengths are therefore $O(t\log q)$, which is
polynomial in $n$. With, for example, schoolbook integer arithmetic,
the complete enumeration and tabulation cost at most
\begin{equation}\label{exact:tabulation-cost}
2^{2B}\operatorname{poly}(n)
\end{equation}
bit operations. The enumerated graph universe depends only on $n$,
not on the accuracy parameter $D$.
\paragraph{Exact correction.}
We first specify the elementary random choice used throughout.
For an integer $K\ge1$, a uniform element of $\{0,\ldots,K-1\}$ is
obtained by drawing $\lceil\log_2 K\rceil$ independent unbiased bits
and repeating if the resulting integer is at least $K$; for $K=1$
use zero bits. Each attempt succeeds with probability greater than
$1/2$, except that a power of two succeeds with probability one.
The draw is exact, terminates almost surely, and uses fewer than two
attempts in expectation. An attempt has bit cost polynomial in
$\log(K+1)$.
Draw $D$ fresh unbiased bits. If they are not all zero, run exactly
$t$ steps of $P_d$ from $G_0$ and output the resulting graph.
Each step uses one bit for the holding decision and the preceding
integer draw to choose a uniform four-element vertex set and one of
the six ordered matching pairs. A four-set can be selected by
unranking its index in the lexicographic list, in polynomial bit
time. This implements $P_d$ exactly. The branch has output law $p$,
terminates almost surely, and has expected polynomial bit cost.
If the $D$ bits are all zero, perform the exact tabulation above and
write $a_G=a_G^{(t)}$. Form the integer weights
\begin{equation}\label{exact:weights}
w_G=2^Dq^t-M(2^D-1)a_G,
\qquad
\sum_{G\in\Omega_d}w_G=Mq^t.
\end{equation}
They are nonnegative by Equation~\eqref{exact:domination}; their sum
uses $\sum_Ga_G=q^t$. Their bit lengths are
$O(D+t\log q+\log M)$, again polynomial in $n$. Draw a uniform
integer in $\{0,\ldots,Mq^t-1\}$ and select its interval in the
cumulative weights $w_G$. This samples exactly the probability law
\[
r_G=\frac{w_G}{Mq^t}
=\frac{1/M-(1-\delta)p_G}{\delta}.
\]
Use fresh random bits in all draws after the branch decision.
The correction branch has probability $\delta$, so the output law is
\begin{equation}\label{exact:mixture}
(1-\delta)p_G+\delta r_G=\frac1M
\qquad(G\in\Omega_d).
\end{equation}
Thus the output is exactly uniform.
\paragraph{Bit cost and termination.}
Every enumeration and integer computation on the correction branch
is finite. All rejection draws terminate almost surely; only finitely
many such draws are invoked on either branch. Hence the complete
algorithm terminates almost surely. The preprocessing, branch choice,
and ordinary branch have expected polynomial bit cost. By
Equation~\eqref{exact:tabulation-cost}, the conditional expected cost
of the correction branch, including its final exact integer draw and
cumulative scan, is at most $2^{2B}\operatorname{poly}(n)$. Its
contribution to the unconditional expectation is
\[
\delta\,2^{2B}\operatorname{poly}(n)
=2^{-2B-10}\operatorname{poly}(n)
\le\operatorname{poly}(n).
\]
All loops, graph tests, and integer computations are specified by one
algorithm, and the input explicitly lists $n$ degrees. The resulting
expected bit bound is therefore a fixed polynomial in the input
length. The correction branch may take exponential time, and the
rejection draws have unbounded tails; the conclusion is an expected
bound, not a polynomial bound on every execution.
\end{proof}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//exact-sampling.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//introduction.tex ====
\section{Introduction}
\label{sec:introduction}
Let $V=\{1,\ldots,n\}$, where $n\ge4$, and let
$d=(d_1,\ldots,d_n)\in\{0,\ldots,n-1\}^n$ be graphical.
Write $\Omega_d$ for the nonempty set of simple undirected graphs on $V$
whose labeled degree vector is $d$, and let $\pi_d$ be the uniform
probability measure on $\Omega_d$. A \emph{switch} removes two disjoint
edges and inserts a different perfect matching on their four vertices,
provided both new edges are absent. This preserves simplicity and
every vertex degree.
We use the following precise discrete-time convention. 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$. If both edges of $F$ are present and both
edges of $F'$ are absent, it replaces $F$ by $F'$; otherwise it stays
put. Denote the transition kernel by $P_d$. For probability measures
on $\Omega_d$, set
\[
\|\mu-\nu\|_{\mathrm{TV}}
=\frac12\sum_{G\in\Omega_d}|\mu(G)-\nu(G)|,
\]
and define
\[
t_{\mathrm{mix}}(d)
=\min\left\{t\in\mathbb Z_{\ge0}:
\max_{G\in\Omega_d}\|P_d^t(G,\cdot)-\pi_d\|_{\mathrm{TV}}
\le\frac14\right\}.
\]
\begin{theorem}\label{thm:main}
For every $n\ge4$ and every graphical degree vector $d$,
\[
t_{\mathrm{mix}}(d)\le 2n^8.
\]
If $|\Omega_d|>1$, the spectral gap of $P_d$ is at least
$[24n^2\binom n4]^{-1}$.
\end{theorem}
\begin{samepage}
\begin{corollary}[Exact uniform sampling]\label{cor:exact-sampling}
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$. Its expected bit running time is bounded by a fixed
polynomial in the binary encoding length of $d$.
\end{corollary}
The corollary includes vectors of length less than four, which are
handled directly. Section~\ref{sec:exact-sampling} proves it by
correcting the finite-time law of the chain. The time bound is in
expectation; no polynomial bound on every random execution is asserted.
\end{samepage}
\paragraph{History and significance.}
Uniform sampling with prescribed degrees provides a basic null model
for networks and a natural problem in approximate counting.
Kannan, Tetali, and Vempala initiated the switch-chain program, treated
regular bipartite sequences, and raised the possibility of broad
applicability~\cite{KTV99}. For simple undirected graphs, Cooper, Dyer,
and Greenhill established rapid mixing for regular sequences; their
corrigendum preserves the polynomial bound with a corrected
exponent~\cite{CDG07,CDG12}. Feder, Guetz, Mihail, and Saberi studied
early irregular families~\cite{FGMS06}, and Greenhill and Sfragara
proved rapid mixing under quantitative restrictions on the degrees,
correcting and extending Greenhill's earlier irregular-degree
argument~\cite{Greenhill15,GS18}. Amanatidis and Kleer developed a route through
strong stability~\cite{AK20}.
Stability conditions for degree-constrained sampling were developed by
Jerrum and Sinclair~\cite{JS90} and by Jerrum, McKay, and
Sinclair~\cite{JMS92}. Erd\H{o}s, Greenhill, Mezei, Mikl\'os,
Solt\'esz, and Soukup subsequently
proved rapid mixing for every P-stable family~\cite{Unified22}.
P-stability requires a polynomial bound, uniform over the family, on
the ratio between the number of realizations of nearby perturbed
sequences and that of the original sequence. Recent work of
Erd\H{o}s, Mikl\'os, and Soukup~\cite{EMS25} and of Erd\H{o}s, Lippner,
Nevo, and Soukup~\cite{ELNS25} gives further P-stable families from
regions in which every admissible degree vector is graphical.
These results explain substantial classes of degrees; the theorem
here requires only that the individual degree vector be graphical.
The modern Kannan--Tetali--Vempala conjecture predicts rapid mixing
for every realizable degree specification in each of the bipartite, directed, and
simple-undirected models; see \cite[Conjecture~1.1]{Unified22}.
Theorem~\ref{thm:main} resolves its simple-undirected formulation
affirmatively. Our off-diagonal transition probabilities agree with
the simple-undirected kernel displayed in
\cite[Equation~(3.1)]{Unified22}.
Fu, Qin, and Wang proved the bipartite formulation, equivalently the
fixed-margin binary-matrix problem~\cite{FQW26}. They compare the
swap chain with a two-row heat bath and reduce its spectral analysis
to a three-row conditional-projection inequality. We reprove the
equivalent variance inequality of their Theorem~5.1, retaining the
separation of label assignments and block counts and the adjacent-count
coupling developed in their Lemmas~5.2--5.4. 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.
These pair updates belong to the Curveball framework. For binary
matrices with fixed margins, Verhelst developed a multiple-swap
procedure~\cite{Verhelst08}. Strona, Nappo, Boccacci, Fattorini, and
San-Miguel-Ayanz later independently formulated a version called the
Curveball algorithm~\cite{Strona14,Strona16,CK18}; Carstens, Berger,
and Strona developed its undirected version~\cite{CBS18}.
They also observed that undirected trades on disjoint vertex pairs can
be dependent. 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.
For prescribed degrees on arbitrary explicitly listed simple undirected
unweighted hosts, OpenAI~\cite[Corollary~10.1]{OpenAIPerfectMatchings2026}
gives a fully polynomial randomized approximation scheme for counting
labeled subgraphs with those degrees and, when feasible, a sampler within
total-variation distance $\tau$ of their uniform law. For rational
$0<\tau<1$, the sampling bit cost on every execution is polynomial in the
full input length and $\tau^{-1}$. These broader-host guarantees do not
assert mixing of a host-restricted switch chain: Theorem~\ref{thm:main}
concerns the complete host, while Corollary~\ref{cor:exact-sampling}
gives exact uniform sampling with expected polynomial bit cost.
\paragraph{Proof strategy.}
For an unordered vertex pair $a$, we resample which of its two endpoints
receives each neighbor adjacent to exactly one of them. All other
adjacencies and the number assigned to each endpoint remain fixed.
Each conditional space is therefore a uniform subset slice: all subsets
of one fixed size from the available neighbors. Let $E_a$ be its
averaging projection, $h_a=I-E_a$, and $H=\sum_a h_a$.
The central estimate is $H^2\succeq H$, where $\succeq$ denotes the
order of quadratic forms. Once the kernel of $H$ is shown to consist
of constants, comparison with individual switches gives the stated
gap and mixing time.
The reduction from $H$ to its restrictions on triples follows the
squared-generator method of Caputo~\cite[Section~1.1]{Caputo08}, also
used for binary matrices by Fu, Qin, and Wang~\cite[Lemma~4.1]{FQW26}.
The expansion groups terms according to whether the two indexing pairs
intersect. Caputo's disjoint terms are controlled by commutation
\cite[Equation~(1.11)]{Caputo08}.
Here the undirected trades need a separate estimate; this is where
the slice comparison and the disjoint-pair calculation enter.
First, all three pair resamplings on a vertex triple can be represented
by updates of a three-row binary matrix with fixed margins. When needed,
one extra column records the internal edges of the triple. We prove that the
variance of a sum of three row functions is at most twice the sum of
their variances. To see the structure behind this estimate, discard
columns of sum zero or three. Each remaining column chooses either
the row containing its unique one or the row containing its unique zero.
We first control these label assignments with their counts fixed,
then control the random counts themselves. The resulting variance
bound controls all overlapping pair resamplings.
Second, after fixing the data preserved by two disjoint pair
resamplings, the dependence between their conditional data has rank
at most one. Its negative contribution is bounded by projections onto
centered indicators that two neighbors receive the same endpoint.
A slice inequality bounds the sum of these projections by the switch
energy available on the same slice. Summing cancels the negative
contributions and completes the estimate for $H$. The three-row
variance inequality and the slice projection comparison are stated
separately from the graph argument, making their scope explicit.
\paragraph{Organization.}
Section~\ref{sec:setup} defines the pair resamplings and their conditional
projections. Section~\ref{row:section} proves the three-row inequality,
and Section~\ref{tri:section} applies it to overlapping updates.
Section~\ref{dis:section} identifies the errors in one disjoint-pair
interaction. Section~\ref{sl:section} controls their sum by a slice
comparison and proves positivity of the full disjoint contribution.
Section~\ref{mix:section} combines these estimates, proves connectivity,
and tracks the comparison and proposal constants through the mixing
bound. Section~\ref{sec:exact-sampling} then gives an exact uniform
sampler with expected polynomial bit cost. All proof ingredients are
supplied in the paper.
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//introduction.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!55!black,citecolor=blue!55!black,urlcolor=blue!55!black]{hyperref}
\hypersetup{pdftitle={Polynomial mixing of the switch chain for every graphical degree sequence},pdfauthor={OpenAI}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\title{Polynomial mixing of the switch chain\\for every graphical degree sequence}
\author{OpenAI}
\date{September 25, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove the simple-undirected form of the Kannan--Tetali--Vempala
conjecture: the switch chain on simple undirected graphs mixes in polynomial
time for every graphical degree sequence. For a lazy chain that proposes
switches uniformly on four vertices, the total-variation mixing time at
distance $1/4$ is at most $2n^8$.
We also give an exactly uniform sampler for every graphical labeled degree
vector. It uses unbiased random bits, terminates almost surely, and has
expected polynomial bit running time.
\end{abstract}
\input{sections/introduction}
\input{sections/setup}
\input{sections/rows}
\input{sections/triples}
\input{sections/disjoint}
\input{sections/slice}
\input{sections/mixing}
\input{sections/exact-sampling}
\input{sources/references}
\end{document}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//main.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//mixing.tex ====
\section{From pair resampling to the switch chain}
\label{mix:section}
We now combine the local estimates, identify the kernel of the resulting
operator, and compare it with the chain in Theorem~\ref{thm:main}.
\subsection{The global operator inequality}
We use the triangle regrouping of Caputo's squared-generator method
\cite[Section~1.1, Equations~(1.13)--(1.15)]{Caputo08}.
The exact correction counts how often each pair belongs to a triple.
Here Corollary~\ref{dis:nonnegative} supplies the disjoint-term
positivity that commutation supplies in that framework.
\begin{proposition}\label{mix:global}
The pair-resampling operator satisfies
\begin{equation}\label{mix:H-square}
H^2\succeq H.
\end{equation}
\end{proposition}
\begin{proof}
Let $D$ be the ordered disjoint-pair sum from
Equation~\eqref{dis:D}. Every ordered pair of distinct intersecting vertex
pairs belongs to the unique triple formed by their union. Each single
vertex pair belongs to $n-2$ triples, and $h_a^2=h_a$. Expanding the
squares therefore gives the exact identity
\begin{equation}\label{mix:expansion}
H^2=\sum_{T\in\binom V3} H_T^2-(n-3)H+D.
\end{equation}
Proposition~\ref{tri:gap} and Corollary~\ref{dis:nonnegative} imply
\[
H^2\succeq\sum_{T\in\binom V3}H_T-(n-3)H
=(n-2)H-(n-3)H=H.
\]
\end{proof}
\subsection{Connectivity and the kernel}
We give a direct connectivity argument to ensure that the operator bound
controls every centered function. It uses Havel's classical
degree-realization switching argument~\cite[Theorem~3]{Havel55},
with deterministic tie-breaking to select the same realization from
every starting graph.
\begin{lemma}\label{mix:connectivity}
Any two graphs in $\Omega_d$ can be joined by a sequence of valid switches.
\end{lemma}
\begin{proof}
We transform every realization into the same recursively prescribed
graph. Suppose a set of vertices has already been frozen, and let $R$ be
the remaining vertex set. The edges involving frozen vertices will no
longer change. Write $d_i^R$ for the degrees in the current induced graph
on $R$.
Choose the first vertex $v\in R$ in label order. Prescribe its desired
neighbors to be the $d_v^R$ vertices of $R\setminus\{v\}$ of highest
residual degree, breaking ties by label. If the current neighbors differ
from this prescribed set, there are a missing desired neighbor $j$ and
an undesired neighbor $i$. Their residual degrees satisfy
$d_j^R\ge d_i^R$. With neighborhoods taken in the induced graph on $R$,
put
\[
A=N_R(j)\setminus\{i\},\qquad
B=N_R(i)\setminus\{j\}.
\]
Removing a possible edge $ij$ subtracts the same amount from both
neighborhood sizes, so $|A|\ge |B|$. Moreover $v\in B\setminus A$.
Consequently $A\setminus B$ is nonempty. A vertex $k$ in this set is
distinct from $v,i,j$, and the membership conditions say precisely that
$vi,jk$ are edges while $vj,ik$ are absent. The valid switch
\[
\{vi,jk\}\longmapsto\{vj,ik\}
\]
changes no other edge at $v$, so it retains every previously attained
desired neighbor and increases their number by one. Repetition therefore
realizes the prescribed neighborhood. If fewer than four residual
vertices remain, a discrepancy would still force the four distinct
vertices just constructed; hence no discrepancy can occur.
Freeze $v$ and continue on $R\setminus\{v\}$. Its residual degree vector
is now determined by the previous vector and the prescribed neighborhood,
independently of the starting realization. It is graphical because the
current graph realizes it. Inductively, the prescription fixes the same
edges from every starting graph. All switches occur entirely among
unfrozen vertices, and the procedure terminates after all vertices are
frozen. Thus every realization is connected to the same graph. Reversing
one of these paths proves the claim.
\end{proof}
\begin{corollary}\label{mix:poincare}
The kernel of $H$ consists exactly of the constant functions. For every
real function $f$ on $\Omega_d$,
\begin{equation}\label{mix:H-poincare}
\operatorname{Var}_{\pi_d}(f)\le \langle f,Hf\rangle.
\end{equation}
\end{corollary}
\begin{proof}
Since the $h_a$ are orthogonal projections,
\[
\langle f,Hf\rangle=\sum_{a\in\binom V2}\|h_af\|^2.
\]
Its vanishing forces $f$ to be constant on every pair fiber. Every valid
switch exchanges two singleton assignments in a pair fiber: take either
opposite vertex pair of the toggled four-cycle. Thus $f$ is constant along
switches, and Lemma~\ref{mix:connectivity} makes it constant on $\Omega_d$.
The converse is immediate.
The operator $H$ is positive semidefinite. By
Proposition~\ref{mix:global}, each eigenvalue $\lambda$ satisfies
$\lambda^2\ge\lambda$, and hence is either zero or at least one.
Its kernel has just been identified, so its restriction to the centered
subspace is bounded below by the identity. Subtracting the mean of $f$
gives Equation~\eqref{mix:H-poincare}.
\end{proof}
\subsection{Comparison with single switches}
We compare a whole-fiber resampling with exchanges of two singleton
assignments inside that fiber. This is the fiberwise heat-bath
comparison principle used by Carstens and Kleer for bipartite switch
and Curveball chains~\cite[Theorems~2 and~7 and Appendix~A]{CK18}.
The argument below proves the required undirected comparison with
its own constant and counts the multiplicity of each switch.
Let $L$ be the unnormalized Laplacian of the switch graph:
\begin{equation}\label{mix:L}
(Lf)(G)=\sum_{G'\text{ a switch neighbor of }G}
\bigl(f(G)-f(G')\bigr).
\end{equation}
Each distinct neighbor appears once in this sum.
For a vertex pair $a$, define $J_a$ on each of its fibers by
\[
J_a=\sum_{1\le k<\ell\le N}(I-\tau_{k\ell}),
\]
where the $N$ singleton vertices have been indexed and $\tau_{k\ell}$
exchanges their assignments. Combining these operators over all fibers
defines $J_a$ on the full graph space.
\begin{lemma}\label{mix:comparison}
The operators above satisfy
\begin{equation}\label{mix:comparison-bounds}
h_a\preceq n^2J_a,\qquad
\sum_{a\in\binom V2}J_a=2L,\qquad
H\preceq2n^2L.
\end{equation}
\end{lemma}
\begin{proof}
First work in one nonconstant uniform $q$-subset fiber with $N$ singleton
labels. Let $S_0$ be a uniform $q$-subset and let $\sigma$ be an independent
uniform permutation of the $N$ labels. Then $\sigma S_0$ is uniform and
independent of $S_0$, so
\[
\operatorname{Var}(f)=\frac12\mathbb E
\bigl(f(S_0)-f(\sigma S_0)\bigr)^2.
\]
Fix, for each permutation, a decomposition into at most $N$
transpositions, obtained for example by decomposing its cycles. Pad with
identities to length $N$. Conditional on $\sigma$, every intermediate
subset is uniform. Cauchy--Schwarz along the resulting path gives
\begin{align*}
\operatorname{Var}(f)
&\le \frac{N^2}{2}\sum_{k<\ell}
\mathbb E_{\mathrm{slice}}
\bigl(f-\tau_{k\ell}f\bigr)^2\\
&=N^2\left\langle f,
\sum_{k<\ell}(I-\tau_{k\ell})f\right\rangle.
\end{align*}
Indeed, Cauchy--Schwarz costs a factor $N$, and each of the $N$ steps has
conditional squared difference bounded by the sum of all transposition
squared differences displayed above. Identity steps contribute zero.
Constant fibers require no estimate. Since $N\le n$, averaging over
fibers proves $h_a\preceq n^2J_a$.
Each switch has two pair-trade realizations, as observed in
Lemma~2 of~\cite{CBS18}. To check this count in the present notation,
consider a particular transition
\[
\{uv,xy\}\longmapsto\{ux,vy\}.
\]
The four distinct vertices form the toggled cycle $u,v,y,x,u$. Taking
$a=\{u,y\}$ exchanges the assignments of singleton vertices $v,x$;
taking $a=\{v,x\}$ exchanges those of singleton vertices $u,y$. These
are two occurrences of this transition. They are also the only ones:
a singleton transposition toggles precisely the four edges between its
indexing pair and the two exchanged singleton vertices. Thus its
indexing pair must be one of the two parts of the unique bipartition of
the toggled four-cycle. Each choice determines its transposition uniquely.
It follows pointwise that $\sum_aJ_a=2L$. Summing the first comparison
now proves the last one.
\end{proof}
Combining Corollary~\ref{mix:poincare} and Lemma~\ref{mix:comparison}, we
obtain
\begin{equation}\label{mix:L-poincare}
\operatorname{Var}_{\pi_d}(f)\le 2n^2\langle f,Lf\rangle.
\end{equation}
In particular, if $|\Omega_d|>1$, the spectral gap of $L$ is at least
$1/(2n^2)$.
\subsection{The prescribed chain and its mixing time}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
If $|\Omega_d|=1$, the mixing time is zero. Suppose henceforth that
$|\Omega_d|>1$. For any distinct switch neighbors $G,G'$, their transition
uniquely specifies its four-element vertex set and the ordered pair of
removed and added matchings. Under the proposal rule of
Section~\ref{sec:introduction},
\[
P_d(G,G')=\frac12\,\frac1{\binom n4}\,\frac16
=\frac1{12\binom n4}.
\]
The reverse transition has the same probability, so $\pi_d$ is
reversible, and the diagonal probabilities give
\begin{equation}\label{mix:normalization}
I-P_d=\frac{L}{12\binom n4}.
\end{equation}
By Equation~\eqref{mix:L-poincare}, the spectral gap of $P_d$ is at least
\begin{equation}\label{mix:gamma}
\gamma_0=\frac1{24n^2\binom n4}.
\end{equation}
The holding probability also ensures nonnegative eigenvalues: write
$P_d=(I+Q)/2$, where $Q$ is the reversible Markov kernel consisting of
the proposal step, including rejected proposals. Jensen's inequality and
stationarity show that $Q$ is a contraction on $L^2(\pi_d)$, so its
eigenvalues lie in $[-1,1]$. Thus every eigenvalue of $P_d$ on the centered
subspace lies in $[0,1-\gamma_0]$, and for a centered function $f$,
\[
\|P_d^t f\|\le(1-\gamma_0)^t\|f\|
\le e^{-\gamma_0t}\|f\|.
\]
The density of a point mass at $G$, minus one, has squared norm
$|\Omega_d|-1$. Reversibility evolves this density by $P_d$. Therefore
Cauchy--Schwarz yields, uniformly over starting states,
\begin{equation}\label{mix:TV}
\|P_d^t(G,\cdot)-\pi_d\|_{\mathrm{TV}}
\le\frac12\sqrt{|\Omega_d|}\,e^{-\gamma_0t}.
\end{equation}
In particular, total variation is at most $1/4$ when
\[
t=\left\lceil
24n^2\binom n4\left(\log2+\frac12\log|\Omega_d|\right)
\right\rceil.
\]
Here and throughout, logarithms are natural. Since there are at most
$2^{\binom n2}$ labeled simple graphs,
\[
\log2+\frac12\log|\Omega_d|
\le \left(1+\frac{n(n-1)}4\right)\log2\le n^2
\qquad(n\ge4).
\]
Also $24n^2\binom n4\le n^6$. The displayed time is consequently at most
$n^8+1\le2n^8$, as claimed.
\end{proof}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//mixing.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//references.tex ====
\begin{thebibliography}{99}
\bibitem{AK20}
G.~Amanatidis and P.~Kleer,
\emph{Rapid mixing of the switch Markov chain for strongly stable degree sequences},
Random Structures \& Algorithms \textbf{57} (2020), no.~3, 637--657.
\href{https://doi.org/10.1002/rsa.20949}{doi:10.1002/rsa.20949}.
\bibitem{Caputo08}
P.~Caputo,
\emph{On the spectral gap of the Kac walk and other binary collision processes},
ALEA. Latin American Journal of Probability and Mathematical Statistics
\textbf{4} (2008), 205--222.
\href{https://alea.impa.br/articles/v4/04-10.pdf}{Primary article}.
\bibitem{CLL06}
E.~Carlen, E.~H.~Lieb, and M.~Loss,
\emph{An Inequality of Hadamard Type for Permanents},
Methods and Applications of Analysis \textbf{13} (2006), no.~1, 1--18.
\href{https://arxiv.org/abs/math/0508096v1}{arXiv:math/0508096v1}.
\bibitem{CBS18}
C.~J.~Carstens, A.~Berger, and G.~Strona,
\emph{A unifying framework for fast randomization of ecological networks with fixed (node) degrees},
MethodsX \textbf{5} (2018), 773--780.
\href{https://doi.org/10.1016/j.mex.2018.06.018}{doi:10.1016/j.mex.2018.06.018}.
Extended version: \href{https://arxiv.org/abs/1609.05137v3}{arXiv:1609.05137v3}.
Numbered sections and lemmas cited here refer to the extended version.
\bibitem{CK18}
C.~J.~Carstens and P.~Kleer,
\emph{Speeding up Switch Markov Chains for Sampling Bipartite Graphs
with Given Degree Sequence},
Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques (APPROX/RANDOM 2018),
Leibniz International Proceedings in Informatics \textbf{116}, 36:1--36:18.
\href{https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.36}{doi:10.4230/LIPIcs.APPROX-RANDOM.2018.36}.
\bibitem{CDG07}
C.~Cooper, M.~Dyer, and C.~Greenhill,
\emph{Sampling regular graphs and a peer-to-peer network},
Combinatorics, Probability and Computing \textbf{16} (2007), no.~4, 557--593.
\href{https://doi.org/10.1017/S0963548306007978}{doi:10.1017/S0963548306007978}.
\bibitem{CDG12}
C.~Cooper, M.~Dyer, and C.~Greenhill,
\emph{Corrigendum: Sampling regular graphs and a peer-to-peer network},
preprint (2012),
\href{https://arxiv.org/abs/1203.6111v1}{arXiv:1203.6111v1}.
\bibitem{DGU14}
M.~Dyer, C.~Greenhill, and M.~Ullrich,
\emph{Structure and eigenvalues of heat-bath Markov chains},
Linear Algebra and its Applications \textbf{454} (2014), 57--71.
\href{https://doi.org/10.1016/j.laa.2014.04.018}{doi:10.1016/j.laa.2014.04.018}.
\bibitem{Unified22}
P.~L.~Erd\H{o}s, C.~Greenhill, T.~R.~Mezei, I.~Mikl\'os,
D.~Solt\'esz, and L.~Soukup,
\emph{The mixing time of switch Markov chains: a unified approach},
European Journal of Combinatorics \textbf{99} (2022), 103421.
\href{https://doi.org/10.1016/j.ejc.2021.103421}{doi:10.1016/j.ejc.2021.103421}.
\href{https://arxiv.org/abs/1903.06600v5}{arXiv:1903.06600v5}.
\bibitem{ELNS25}
P.~L.~Erd\H{o}s, G.~Lippner, N.~Nevo, and L.~Soukup,
\emph{Any fully graphic region of degree sequences can be sampled rapidly},
preprint (2025),
\href{https://arxiv.org/abs/2511.13564v1}{arXiv:2511.13564v1}.
\bibitem{EMS25}
P.~L.~Erd\H{o}s, I.~Mikl\'os, and L.~Soukup,
\emph{Fully graphic degree sequences and P-stable degree sequences},
Advances in Applied Mathematics \textbf{163} (2025), 102805.
\href{https://doi.org/10.1016/j.aam.2024.102805}{doi:10.1016/j.aam.2024.102805}.
\bibitem{FGMS06}
T.~Feder, A.~Guetz, M.~Mihail, and A.~Saberi,
\emph{A Local Switch Markov Chain on Given Degree Graphs with Application
in Connectivity of Peer-to-Peer Networks},
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2006), 69--76.
\href{https://doi.org/10.1109/FOCS.2006.5}{doi:10.1109/FOCS.2006.5}.
\bibitem{Filmus16}
Y.~Filmus,
\emph{An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube},
Electronic Journal of Combinatorics \textbf{23} (2016), no.~1, P1.23.
\href{https://doi.org/10.37236/4567}{doi:10.37236/4567}.
\bibitem{FQW26}
W.~Fu, Q.~Qin, and G.~Wang,
\emph{Spectral Gap for the Binary Fixed-Margin Swap Chain},
preprint (2026), \href{https://arxiv.org/abs/2606.22636v2}{arXiv:2606.22636v2}.
\bibitem{GLMP2024}
A.~G\"obel, J.~Liu, P.~Manurangsi, and M.~Pappik,
\emph{Perfect sampling from rapidly mixing Markov chains},
preprint (2024),
\href{https://arxiv.org/abs/2410.00882v2}{arXiv:2410.00882v2},
version~2, December~6, 2024.
\bibitem{Greenhill15}
C.~Greenhill,
\emph{The switch Markov chain for sampling irregular graphs},
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2015), 1564--1572.
\href{https://doi.org/10.1137/1.9781611973730.103}{doi:10.1137/1.9781611973730.103}.
\bibitem{GS18}
C.~Greenhill and M.~Sfragara,
\emph{The switch Markov chain for sampling irregular graphs and digraphs},
Theoretical Computer Science \textbf{719} (2018), 1--20.
\href{https://doi.org/10.1016/j.tcs.2017.11.010}{doi:10.1016/j.tcs.2017.11.010}.
\href{https://arxiv.org/abs/1701.07101v2}{arXiv:1701.07101v2}.
\bibitem{Havel55}
V.~Havel,
\emph{Pozn\'amka o existenci kone\v{c}n\'ych graf\r{u}}
[A remark on the existence of finite graphs],
\v{C}asopis pro p\v{e}stov\'an\'i matematiky
\textbf{80} (1955), no.~4, 477--480.
\href{https://doi.org/10.21136/CPM.1955.108220}{doi:10.21136/CPM.1955.108220}.
\bibitem{JMS92}
M.~Jerrum, B.~D.~McKay, and A.~Sinclair,
\emph{When is a graphical sequence stable?},
in A.~Frieze and T.~\L uczak (eds.), Random Graphs, vol.~2,
Wiley, 1992.
\href{https://users.cecs.anu.edu.au/~bdm/papers/DegSeqStable.pdf}{Author-hosted copy}.
\bibitem{JS90}
M.~Jerrum and A.~Sinclair,
\emph{Fast uniform generation of regular graphs},
Theoretical Computer Science \textbf{73} (1990), no.~1, 91--100.
\href{https://doi.org/10.1016/0304-3975(90)90164-D}{doi:10.1016/0304-3975(90)90164-D}.
\bibitem{KTV99}
R.~Kannan, P.~Tetali, and S.~Vempala,
\emph{Simple Markov-chain algorithms for generating bipartite graphs and tournaments},
Random Structures \& Algorithms \textbf{14} (1999), no.~4, 293--308.
\href{https://doi.org/10.1002/(SICI)1098-2418(199907)14:4\%3C293::AID-RSA1\%3E3.0.CO;2-G}{doi:10.1002/(SICI)1098-2418(199907)14:4\textless293::AID-RSA1\textgreater3.0.CO;2-G}.
An extended abstract appeared in Proceedings of SODA 1997, pp.~193--200.
\bibitem{OpenAIPerfectMatchings2026}
OpenAI,
\emph{A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs},
OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026/main.pdf}{OAI:A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026},
2026.
\bibitem{OpenAIContingency2026}
OpenAI,
\emph{Exact Uniform Sampling of Contingency Tables with Arbitrary Margins},
OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026/main.pdf}{OAI:Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026},
2026.
\bibitem{Strona14}
G.~Strona, D.~Nappo, F.~Boccacci, S.~Fattorini, and J.~San-Miguel-Ayanz,
\emph{A fast and unbiased procedure to randomize ecological binary matrices
with fixed row and column totals},
Nature Communications \textbf{5} (2014), 4114.
\href{https://doi.org/10.1038/ncomms5114}{doi:10.1038/ncomms5114}.
\bibitem{Strona16}
G.~Strona, D.~Nappo, F.~Boccacci, S.~Fattorini, and J.~San-Miguel-Ayanz,
\emph{Corrigendum: A fast and unbiased procedure to randomize ecological binary
matrices with fixed row and column totals},
Nature Communications \textbf{7} (2016), 13086.
\href{https://doi.org/10.1038/ncomms13086}{doi:10.1038/ncomms13086}.
\bibitem{Verhelst08}
N.~D.~Verhelst,
\emph{An efficient MCMC algorithm to sample binary matrices with fixed marginals},
Psychometrika \textbf{73} (2008), no.~4, 705--728.
\href{https://doi.org/10.1007/s11336-008-9062-3}{doi:10.1007/s11336-008-9062-3}.
\end{thebibliography}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//references.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//rows.tex ====
\section{A variance inequality for three rows}\label{row:section}
The estimate in this section concerns arbitrary binary matrices with three
rows and prescribed margins. It will control resamplings on a vertex
triple, but does not require a graph interpretation. The equivalent
conditional-projection inequality was proved by Fu, Qin and Wang
\cite[Theorem~5.1]{FQW26}. We give a proof using label transpositions
and conditional variance, separating the randomness of the labels from
that of the block sizes. The count distribution and adjacent-total
coupling below correspond to their Lemmas~5.2--5.4; all steps are
included here.
The transposition and invariant-coordinate strategy for the fixed-block
argument was inspired by the symmetric-group heat-flow method of
Carlen, Lieb and Loss \cite[Section~2]{CLL06}. The variance proof below
is self-contained; the three-row inequality and count coupling retain
the Fu--Qin--Wang attribution above.
\begin{lemma}[Fixed block sizes]\label{row:fixed-blocks}
Let $(U_1,U_2,U_3)$ and $(W_1,W_2,W_3)$ be independent uniform ordered
partitions of finite labeled sets $U$ and $W$, with all six block sizes
prescribed. For arbitrary real functions $g_i=g_i(U_i,W_i)$,
\begin{equation}\label{row:fixed-variance}
\operatorname{Var}\Bigl(\sum_{i=1}^3 g_i\Bigr)
\le 2\sum_{i=1}^3\operatorname{Var}(g_i).
\end{equation}
\end{lemma}
\begin{proof}
Subtract the mean from each $g_i$. On the finite conditional space, let
\[
J=\sum_{\tau}(I-T_\tau),
\]
where $\tau$ ranges over transpositions of two labels within $U$ or
within $W$, and $T_\tau$ acts on functions by permuting those labels.
Every $T_\tau$ is a self-adjoint involution, so
\begin{equation}\label{row:transposition-energy}
\langle f,Jf\rangle
=\frac12\sum_\tau\mathbb E(f-T_\tau f)^2.
\end{equation}
The permutations of $U$ and $W$ act transitively on the ordered
partitions with their prescribed sizes. Since transpositions generate
these permutations, the kernel of $J$ consists precisely of constants.
This also covers empty blocks and label sets; a one-state space has no
nonzero centered functions.
The space of functions of $(U_i,W_i)$ is invariant under $J$.
Indeed, a transposition within $U$ changes such a function only when it
exchanges a label in $U_i$ with one outside $U_i$. The resulting block
is determined by $U_i$ and the two labels, regardless of which other
block contains the outside label. The same observation applies to $W$.
Every spectral projection of the finite-dimensional operator $J$ is a
polynomial in $J$, and therefore preserves each row-function space.
Write $g_i=\sum_{\lambda>0}g_{i,\lambda}$ for its orthogonal spectral
decomposition. For a fixed transposition, at most two of the three
block tuples change. Hence, pointwise,
\[
\left(\sum_i(g_{i,\lambda}-T_\tau g_{i,\lambda})\right)^2
\le 2\sum_i(g_{i,\lambda}-T_\tau g_{i,\lambda})^2.
\]
Using \eqref{row:transposition-energy} gives
\[
\lambda\left\|\sum_i g_{i,\lambda}\right\|^2
\le 2\lambda\sum_i\|g_{i,\lambda}\|^2.
\]
Divide by $\lambda>0$ and sum over the orthogonal eigenspaces to obtain
\eqref{row:fixed-variance}.
\end{proof}
\begin{lemma}[Random block sizes]\label{row:counts}
Let $m,\alpha_1,\alpha_2,\alpha_3$ be nonnegative integers. Give the
triples $x=(x_1,x_2,x_3)$ of nonnegative integers with
$x_1+x_2+x_3=m$ probabilities proportional to
\[
\prod_{i=1}^3 w_i(x_i),\qquad
w_i(t)=\frac1{t!(t+\alpha_i)!}.
\]
For arbitrary real functions $b_i$ of one coordinate,
\begin{equation}\label{row:count-variance}
\operatorname{Var}\Bigl(\sum_{i=1}^3b_i(x_i)\Bigr)
\le 2\sum_{i=1}^3\operatorname{Var}(b_i(x_i)).
\end{equation}
\end{lemma}
\begin{proof}
The case $m=0$ is immediate. Suppose $m>0$.
We first compare the distributions of two coordinates with adjacent
totals, using the coupling of Fu, Qin and Wang \cite[Lemma~5.2]{FQW26}.
We include the argument. Let $(Y_s,Z_s)$ have probabilities proportional to
$w_j(y)w_k(z)$ on $y+z=s$. For $s\ge1$ and $0\le y\le s-1$, the
ratio of the probability of $Y_s=y$ to that of $Y_{s-1}=y$ is a positive
constant times
\[
\frac{w_k(s-y)}{w_k(s-1-y)}
=\frac1{(s-y)(s-y+\alpha_k)},
\]
which is nondecreasing in $y$. Reweighting by a nondecreasing function
increases expectations of nondecreasing functions: for two such
functions $a,b$ and independent identically distributed $Y,Y'$, this
follows from
\[
\operatorname{Cov}(a(Y),b(Y))
=\frac12\mathbb E\bigl[(a(Y)-a(Y'))(b(Y)-b(Y'))\bigr]\ge0.
\]
Applying this observation on the common support, and then adding the
possible mass at $y=s$, proves $Y_{s-1}\le_{\mathrm{st}}Y_s$.
Interchanging the coordinates also gives
$Z_{s-1}\le_{\mathrm{st}}Z_s$, or equivalently
$Y_s\le_{\mathrm{st}}Y_{s-1}+1$.
Use the same uniform random variable in the inverse distribution
functions of $Y_{s-1}$ and $Y_s$. Writing $Q$ for these quantile
functions, the identity $Q_{Y_{s-1}+1}(u)=Q_{Y_{s-1}}(u)+1$ shows that
both stochastic inequalities hold simultaneously:
\begin{equation}\label{row:covering-coupling}
Y_{s-1}\le Y_s\le Y_{s-1}+1.
\end{equation}
Since these variables are integer-valued, setting $Z$ from its
respective total yields a coupling in which exactly one of the two
coordinates increases by one.
Now let $A$ map the direct sum of the three centered marginal function
spaces to the centered joint space by
$A(b_1,b_2,b_3)=\sum_i b_i(x_i)$.
The direct sum has squared norm $\sum_i\|b_i\|^2$.
To prove \eqref{row:count-variance}, it suffices to bound the largest
eigenvalue $\lambda$ of $A^*A$ by $2$. A corresponding nonzero
centered eigenvector satisfies
\begin{equation}\label{row:count-eigenvector}
\lambda b_i(t)
=\mathbb E\left[\sum_{j=1}^3b_j(x_j)\,\middle|\,x_i=t\right],
\qquad 0\le t\le m.
\end{equation}
Every value $0,\ldots,m$ has positive marginal probability. Therefore
\[
M=\max_{i,\,0\le t<m}|b_i(t+1)-b_i(t)|
\]
is positive: otherwise each component would be constant, and hence
zero by centering.
Conditioning on $x_i=t$ leaves the other two coordinates with total
$s=m-t$. For adjacent values $t,t+1$, couple those coordinates using
\eqref{row:covering-coupling}. Exactly one of them decreases by one,
so the change in their conditional sum of functions has absolute
value at most $M$. Subtracting \eqref{row:count-eigenvector} at the two
values thus gives
\[
|(\lambda-1)(b_i(t+1)-b_i(t))|\le M.
\]
Choose $i,t$ attaining $M$. It follows that $|\lambda-1|\le1$, and
in particular $\lambda\le2$.
\end{proof}
\begin{lemma}[Three-row variance inequality]\label{row:variance}
Fix row and column sums for binary matrices with three rows, and take
the uniform distribution on the nonempty set of all matrices with
these prescribed margins.
Let $S_i$ denote row $i$. For arbitrary real row functions $f_i$,
\begin{equation}\label{row:main-variance}
\operatorname{Var}\Bigl(\sum_{i=1}^3f_i(S_i)\Bigr)
\le 2\sum_{i=1}^3\operatorname{Var}(f_i(S_i)).
\end{equation}
\end{lemma}
\begin{proof}
Columns of sum $0$ or $3$ are deterministic; remove them and adjust
the row sums. Let $U$ index the columns of sum $1$, assigned to the
row containing their unique one. Let $W$ index the columns of sum $2$,
assigned to the row containing their unique zero. Write $U_i,W_i$
for the resulting blocks. The nondeterministic information in row
$i$ is exactly $(U_i,W_i)$.
Put $k_i=|W_i|$. The adjusted row-sum constraints have the form
\[
|U_i|=k_i+\delta_i
\]
for fixed integers $\delta_i$, since that row sum equals
$|U_i|+|W|-k_i$. Conditional on the vector $k$, the assignments on $U$
and $W$ are independent uniform ordered partitions with prescribed
block sizes. Lemma~\ref{row:fixed-blocks} therefore applies.
Counting these partitions shows that the law of $k$ has weights
proportional to
\[
\prod_{i=1}^3\frac1{k_i!(k_i+\delta_i)!},
\qquad k_i\ge0,\quad k_i+\delta_i\ge0,\quad \sum_i k_i=|W|.
\]
These conditions are sufficient for feasibility: the two sets of
nonnegative block sizes sum to $|W|$ and $|U|$, respectively. Set
\[
l_i=\max(0,-\delta_i),\qquad
x_i=k_i-l_i,\qquad \alpha_i=|\delta_i|,\qquad
m=|W|-\sum_i l_i.
\]
Nonemptiness implies $m\ge0$. The support becomes all nonnegative
triples of total $m$, and the weights become
$\prod_i[x_i!(x_i+\alpha_i)!]^{-1}$.
Thus Lemma~\ref{row:counts} applies to functions of the individual
counts.
Conditional on $k$, the marginal blocks $U_i$ and $W_i$ are independent
uniform subsets of their respective sizes. In particular
$\mathbb E[f_i(S_i)\mid k]$ depends only on $k_i$, or equivalently on
$x_i$. Applying conditional variance, followed by
Lemmas~\ref{row:fixed-blocks} and~\ref{row:counts}, gives
\begin{align*}
\operatorname{Var}\Bigl(\sum_i f_i(S_i)\Bigr)
&=\mathbb E\operatorname{Var}\Bigl(\sum_i f_i(S_i)\,\Big|\,k\Bigr)
+\operatorname{Var}\Bigl(\sum_i\mathbb E[f_i(S_i)\mid k]\Bigr)\\
&\le 2\sum_i\mathbb E\operatorname{Var}(f_i(S_i)\mid k)
+2\sum_i\operatorname{Var}(\mathbb E[f_i(S_i)\mid k])\\
&=2\sum_i\operatorname{Var}(f_i(S_i)),
\end{align*}
as required.
\end{proof}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//rows.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//setup.tex ====
\section{Pair resamplings}
\label{sec:setup}
All function spaces below are real. On $\Omega_d$, use the inner
product $\langle f,g\rangle=\mathbb E_{\pi_d}[fg]$ and its norm.
For self-adjoint operators, $A\succeq B$ means
$\langle f,(A-B)f\rangle\ge0$ for every $f$.
When restricting to a cell of a partition, inner products and
expectations use its conditional uniform probability measure.
For an unordered vertex pair $a=\{i,j\}$, record
\begin{enumerate}
\item every edge with neither endpoint in $a$;
\item whether the edge $ij$ is present;
\item for each $w\notin a$, the number of its neighbors in $a$.
\end{enumerate}
The resulting cells are the \emph{$a$-fibers}. Fix an ordering of the
two endpoints of every pair. In one $a$-fiber, call an outside vertex
a \emph{singleton} if it has exactly one neighbor in $a$.
If there are $N$ such vertices, the degree of the first endpoint
specifies the number $q$ assigned to it. Vertices with zero or two
neighbors in $a$ have no choice. Hence the fiber is in bijection
with all $q$-subsets of its $N$ singleton vertices, uniformly.
Every such reassignment preserves all degrees and simplicity;
there are no further constraints on the subset.
Uniform resampling of this subset is the undirected Curveball
trade of~\cite{CBS18}.
Let $E_a$ be conditional expectation on the partition into
$a$-fibers, and put
\begin{equation}\label{eq:pair-operators}
h_a=I-E_a,\qquad H=\sum_{a\in\binom V2}h_a.
\end{equation}
This is the partition-based heat-bath construction of
Dyer, Greenhill, and Ullrich~\cite[Definition~1.1]{DGU14}.
Thus $E_a$ and $h_a$ are orthogonal projections. In particular,
$H$ is positive semidefinite and kills constants. We shall prove
\begin{equation}\label{eq:H-target}
H^2\succeq H.
\end{equation}
The next sections establish the local inequalities needed for this
bound. Section~\ref{mix:section} identifies the kernel and compares $H$
with the switch chain.
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//setup.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//slice.tex ====
\section{Controlling the equality projections}
\label{sl:section}
We now bound the summed errors in Proposition~\ref{dis:interaction}.
On each pair fiber, equal-assignment indicators are quadratic functions
of the subset coordinates. Their span therefore uses only the
degree-one and degree-two parts of the Johnson slice decomposition;
see Filmus~\cite[Lemmas~18 and~24]{Filmus16}. We verify the required
identities directly. After the slice comparison, we return to the graph
space and sum the disjoint-pair inequalities.
\begin{lemma}[Equality-indicator projections on a slice]
\label{sl:comparison}
Let $N\ge0$ and $0\le q\le N$ be integers. Give
\[
\mathcal X_{N,q}
=\left\{x\in\{0,1\}^N:\ \sum_{i=1}^N x_i=q\right\}
\]
the uniform measure. Let $\tau_{ij}$ interchange coordinates $i,j$, and
put
\[
G=\frac12\sum_{i<j}(I-\tau_{ij}).
\]
For each pair $i<j$, let $Q_{ij}$ be orthogonal projection onto the centered
function
\[
z_{ij}=\mathbf 1_{\{x_i=x_j\}}
-\mathbb P(x_i=x_j),
\]
with the convention $Q_{ij}=0$ when $z_{ij}=0$. Then
\begin{equation}
S:=\sum_{i<j}Q_{ij}\preceq G.
\label{sl:operator-comparison}
\end{equation}
\end{lemma}
\begin{proof}
Each $(I-\tau_{ij})/2$ is an orthogonal projection, so $G$ is positive
semidefinite. If all the $z_{ij}$ vanish, the assertion follows immediately.
This covers $N\le2$ and $q\in\{0,N\}$. In the remaining cases $N\ge3$ and
$1\le q\le N-1$. Writing $r=N-q$, we have
\begin{equation}
\begin{aligned}
p&:=\mathbb P(x_i=x_j)
=\frac{q(q-1)+r(r-1)}{N(N-1)},\\
1-p&=\frac{2qr}{N(N-1)},\qquad
\|z_{ij}\|^2=p(1-p)>0.
\end{aligned}
\label{sl:p}
\end{equation}
All norms of functions in this proof use the uniform measure on the slice.
Let $M=\binom N2$ and give the pair coefficient space $\mathbb R^M$ its
usual Euclidean inner product. Define
\[
Bc=\sum_{i<j}c_{ij}\frac{z_{ij}}{\sqrt{p(1-p)}}.
\]
Then $S=BB^*$. We analyze its Gram matrix $K=B^*B$ using the orthogonal
decomposition
\begin{align*}
\mathcal C_0&=\{c:\ c_{ij}\text{ is constant}\},\\
\mathcal C_1&=\left\{c:\ c_{ij}=u_i+u_j,\quad\sum_i u_i=0\right\},\\
\mathcal C_2&=\left\{c:\ \sum_{j\ne i}c_{ij}=0\text{ for every }i\right\}.
\end{align*}
Here and below $c_{ji}=c_{ij}$. To verify the decomposition, the map
$u\mapsto(u_i+u_j)_{i<j}$ is injective for $N\ge3$: its kernel vanishes on
every triangle, and hence on every vertex. Its image is
$\mathcal C_0\oplus\mathcal C_1$, and its orthogonal complement is precisely
$\mathcal C_2$. Thus the dimensions are $1$, $N-1$, and $M-N$, respectively.
In particular $\mathcal C_2=\{0\}$ when $N=3$.
The number of equal coordinate pairs is fixed on the slice:
\[
\sum_{i<j}\mathbf 1_{\{x_i=x_j\}}=\binom q2+\binom r2.
\]
It follows that $B$ kills $\mathcal C_0$. Permutation invariance shows that
the entries of $K$ depend only on the intersection size of their indexing
pairs. Moreover, for a fixed pair $ij$, the sums of coefficients over
\emph{other} pairs meeting $ij$, and over pairs disjoint from $ij$, are
\[
\begin{array}{c|cc}
&\text{intersection of size one}&\text{disjoint}\\ \hline
c\in\mathcal C_1&(N-4)c_{ij}&-(N-3)c_{ij}\\
c\in\mathcal C_2&-2c_{ij}&c_{ij}.
\end{array}
\]
Indeed, the first column is the sum of the two row sums minus $2c_{ij}$;
the row sums are $(N-2)u_i$ on $\mathcal C_1$ and zero on $\mathcal C_2$.
The second column follows because both spaces have zero total coefficient
sum. For $N=3$ there are no disjoint pairs, and the displayed expression
on $\mathcal C_1$ is zero as required. Consequently $K$ acts by a scalar
$\mu_1$ on $\mathcal C_1$ and, when present, by a scalar $\mu_2$ on
$\mathcal C_2$.
We first compute $\mu_1$. The number of coordinates other than $i$ equal
to $x_i$ is
\[
\sum_{j\ne i}\mathbf 1_{\{x_i=x_j\}}
=(r-1)+(2q-N)x_i.
\]
For $\sum_i u_i=0$ this gives
\begin{equation}
\sum_{i<j}(u_i+u_j)z_{ij}
=(2q-N)\sum_i u_i x_i.
\label{sl:linear-image}
\end{equation}
The one- and two-coordinate probabilities of a uniform $q$-subset imply
\[
\operatorname{Var}\!\left(\sum_i u_i x_i\right)
=\frac{qr}{N(N-1)}\sum_i u_i^2,
\qquad
\sum_{i<j}(u_i+u_j)^2=(N-2)\sum_i u_i^2.
\]
Using these identities and \eqref{sl:p} in
$\|Bc\|^2=\mu_1\|c\|^2$ yields
\begin{equation}
\mu_1=\frac{(2q-N)^2}{2(N-2)p}\le\frac N2.
\label{sl:mu-one}
\end{equation}
For the inequality, the difference of the relevant numerators is
\[
N(N-2)p-(2q-N)^2
=\frac{2N}{N-1}\bigl(qr-(N-1)\bigr)\ge0,
\]
since $q,r\ge1$ and $q+r=N$.
The diagonal entries of $K$ are all one, so $\operatorname{tr}K=M$.
Since $K$ is positive semidefinite, for $N\ge4$ we obtain
\begin{equation}
(M-N)\mu_2\le M,
\qquad
0\le\mu_2\le\frac{N-1}{N-3}\le N-1.
\label{sl:mu-two}
\end{equation}
This argument is used only when $\mathcal C_2$ is present.
To compare with $G$, set $\mathcal U_i=B\mathcal C_i$ for $i=1,2$.
These images are orthogonal, since
$\langle Bc,Bd\rangle=\langle c,Kd\rangle$. On $\mathcal U_i$ the operator
$S=BB^*$ acts by $\mu_i$; an image may of course be zero. Direct summation
of the transpositions gives
\begin{align}
Gx_i&=\frac{Nx_i-q}{2},\label{sl:G-linear}\\
G(x_ix_j)&=(N-1)x_ix_j-\frac{q-1}{2}(x_i+x_j).
\label{sl:G-quadratic}
\end{align}
For the second identity, only swaps involving exactly one of $i,j$
contribute. Their sum is
\[
(N-2)x_ix_j-\frac12(x_i+x_j)\sum_{k\notin\{i,j\}}x_k
=(N-1)x_ix_j-\frac{q-1}{2}(x_i+x_j),
\]
using $x_i^2=x_i$ and $\sum_kx_k=q$.
By \eqref{sl:linear-image} and \eqref{sl:G-linear}, $G$ acts on
$\mathcal U_1$ by $N/2$. For $c\in\mathcal C_2$, the expansion
\[
z_{ij}=1-p-x_i-x_j+2x_ix_j
\]
shows that $Bc$ is proportional to $\sum_{i<j}c_{ij}x_ix_j$: the constant
and linear terms vanish by the row-zero conditions. Those same conditions
cancel the linear terms in \eqref{sl:G-quadratic}, so $G$ acts on
$\mathcal U_2$ by $N-1$. Equations \eqref{sl:mu-one} and
\eqref{sl:mu-two} therefore give $S\preceq G$ on
$\mathcal U_1\oplus\mathcal U_2$. This space is invariant under the
self-adjoint $G$, hence so is its orthogonal complement. On that complement
$S=0$, because $B\mathcal C_0=0$ and the three coefficient spaces exhaust
$\mathbb R^M$; meanwhile $G\succeq0$. This proves
\eqref{sl:operator-comparison} on the whole slice.
For clarity, the possible zero images introduce no additional cases:
when $q=1$ or $q=N-1$, \eqref{sl:mu-one} gives $\mu_1=N/2$, and the trace
identity gives $\mu_2=0$ if $N\ge4$; when $q=N/2$, $\mu_1=0$.
For $N=3$ the second image is absent. At $N=4,q=2$, the trace identity gives
$\mu_2=3=N-1$, so the estimate includes this boundary case with equality.
\end{proof}
\begin{corollary}[Summed equality-indicator energy]
\label{sl:global}
For every vertex pair $a$ and every function $f$ on the graph space,
\begin{equation}
\sum_{b:\,b\cap a=\varnothing}\|R_{a,b}f\|^2
\le
\sum_{b:\,b\cap a=\varnothing}\|g_{a,b}f\|^2.
\label{sl:graph-comparison}
\end{equation}
\end{corollary}
\begin{proof}
Work first in one $a$-fiber, whose assignments form a uniform $q$-subset
slice of its $N$ singleton vertices. If both vertices of $b$ are singleton
labels $k,l$, the involution $T_{a,b}$ acts on this slice exactly as
$\tau_{kl}$: it interchanges their assignments when they differ and acts
trivially when they agree. Thus $g_{a,b}=(I-\tau_{kl})/2$, while
$R_{a,b}=Q_{kl}$ in the notation of Lemma~\ref{sl:comparison}.
If either vertex of $b$ is not a singleton, the cross matrix cannot have
both column sums equal to one, and both $g_{a,b}$ and $R_{a,b}$ vanish
on the fiber. Since an orthogonal projection $Q$ satisfies
$\|Qf\|^2=\langle f,Qf\rangle$, the two conditional sums in
\eqref{sl:graph-comparison} are $\langle f,Sf\rangle$ and
$\langle f,Gf\rangle$. Lemma~\ref{sl:comparison} compares them.
Both operators preserve the complete $a$-fibers, so averaging these
conditional inequalities proves the corollary.
\end{proof}
\begin{corollary}\label{dis:nonnegative}
The ordered sum
\begin{equation}\label{dis:D}
D=\sum_{\substack{a,b\in\binom V2\\a\cap b=\varnothing}}h_a h_b
\end{equation}
is self-adjoint and positive semidefinite.
\end{corollary}
\begin{proof}
The two orders of every disjoint pair occur in the sum, proving
self-adjointness. Grouping them and applying
Proposition~\ref{dis:interaction} gives
\begin{align*}
\langle f,Df\rangle
&\ge\sum_{\{a,b\}:\,a\cap b=\varnothing}
\bigl(2\|g_{a,b}f\|^2
-\|R_{a,b}f\|^2-\|R_{b,a}f\|^2\bigr)\\
&=\sum_{a\in\binom V2}
\left(\sum_{b:\,a\cap b=\varnothing}\|g_{a,b}f\|^2
-\sum_{b:\,a\cap b=\varnothing}\|R_{a,b}f\|^2\right)
\ge0.
\end{align*}
The first sum is over unordered pairs of disjoint vertex pairs;
the equality uses $g_{a,b}=g_{b,a}$. The last inequality is
Corollary~\ref{sl:global}, applied separately for each $a$.
\end{proof}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//slice.tex ====
==== BEGIN Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//triples.tex ====
\section{Resamplings on a vertex triple}\label{tri:section}
We now transfer the three-row inequality to graph resamplings whose
indexing pairs share a vertex. The internal edges of the three vertices
must be included in the matrix encoding; Table~\ref{tri:encoding}
records the four possible internal edge counts.
For $T\in\binom V3$, define
\[
H_T=\sum_{a\in\binom T2}h_a.
\]
The three-row inequality yields the following local spectral bound.
\begin{proposition}\label{tri:gap}
For every vertex triple $T$, one has $H_T^2\succeq H_T$.
\end{proposition}
\begin{proof}
Partition $\Omega_d$ by recording the graph on $V\setminus T$ and,
for each $w\notin T$, its number of neighbors in $T$.
Every pair resampling indexed by a pair in $T$ preserves these data.
Work in one nonempty cell, with its conditional uniform measure.
The degree sum in $T$ determines the total number $e\in\{0,1,2,3\}$
of edges inside $T$.
Use a binary matrix with rows indexed by $i\in T$ and columns indexed
by $w\notin T$, whose entry at $(i,w)$ is the indicator of the edge
$iw$. Its column sums are fixed. To encode the internal graph as
well, let $s_i$ denote the degree of $i$ within $T$, and augment the
matrix as follows.
\begin{table}[ht]
\centering
\begin{tabular}{c|l|c|c}
$e$ & Internal graph & Extra column & Row sum at $i$\\ \hline
$0$ & Empty & None & $d_i$\\
$1$ & A single edge & $s_i$ (sum $2$) & $d_i$\\
$2$ & A path & $s_i-1$ (sum $1$) & $d_i-1$\\
$3$ & A triangle & None & $d_i-2$
\end{tabular}
\caption{Encoding the internal edges of a triple in a three-row matrix.
The extra column, when present, is a distinct labeled column.}
\label{tri:encoding}
\end{table}
For $e=1$, the extra column marks the endpoints of the sole edge;
for $e=2$, it marks the center of the path. Thus the internal graph is
uniquely recovered from the extra column, or is deterministic when
$e=0,3$. Conversely, every binary matrix with the prescribed row and
column sums recovers a valid graph in this cell. The row sums give
the required degrees in $T$, while the external column sums and the
fixed graph on $V\setminus T$ give all other degrees. This is a
bijection onto the entire fixed-margin matrix space, so its
conditional measure is uniform.
We next identify the conditional operators exactly. Fix $i\in T$
and write $\{j,k\}=T\setminus\{i\}$. Within this cell,
\begin{equation}\label{tri:conditional-row}
E_{\{j,k\}}f=\mathbb E[f\mid S_i],
\end{equation}
where $S_i$ is augmented row $i$.
Indeed, the external entries of this row determine $s_i$ from $d_i$,
and hence determine its extra entry whenever present. Fixing the
row therefore means precisely fixing the external neighbors of $i$.
Together with the cell data, these neighbors determine all the
$\{j,k\}$-fiber data:
\begin{itemize}
\item the graph away from $\{j,k\}$ is the fixed graph on
$V\setminus T$, together with the specified external edges at $i$;
\item the indicator of $jk$ is $e-s_i$;
\item the number of neighbors in $\{j,k\}$ of each $w\notin T$ is
its recorded number of neighbors in $T$ minus the indicator of $iw$;
\item the number of neighbors in $\{j,k\}$ of $i$ itself is $s_i$.
\end{itemize}
Conversely, the pair-fiber data fix all external edges at $i$, and
therefore fix $S_i$. The fiber is contained in the cell because the
cell data are preserved by the pair resampling. Thus the two
conditionings coincide on the full pair fiber, proving
\eqref{tri:conditional-row}. In particular, when $s_i=1$, the choice
between $ij$ and $ik$ remains free whenever the other constraints
permit it; conditioning on the augmented row does not freeze that
internal choice.
Let $P_i f=\mathbb E[f\mid S_i]$. For a function $f$ centered in the
cell, the functions $P_i f$ are centered row functions. Put
$b=\sum_i\|P_i f\|^2$. Orthogonality of $P_i$,
Lemma~\ref{row:variance}, and Cauchy--Schwarz yield
\[
b=\left\langle f,\sum_i P_i f\right\rangle
\le\|f\|\left\|\sum_i P_i f\right\|
\le\|f\|\sqrt{2b}.
\]
It follows that $b\le2\|f\|^2$, including when $b=0$.
By \eqref{tri:conditional-row},
\[
\langle f,H_Tf\rangle
=3\|f\|^2-\sum_i\|P_i f\|^2\ge\|f\|^2.
\]
Thus the self-adjoint operator $H_T$ kills constants and has all its
other eigenvalues at least $1$ in this cell. Squaring its eigenvalues
proves $H_T^2\succeq H_T$ there; the conclusion is also immediate for
a singleton cell. Finally, all the operators preserve the cells, so
the cellwise inequalities give the claimed inequality on $\Omega_d$.
\end{proof}
==== END Polynomial-Mixing-of-the-Switch-Chain-for-Every-Graphical-Degree-Sequence//triples.tex ====