==== 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 $21$, 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 t0.
\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