==========================================================================
POLYNOMIAL MIXING OF THE SWITCH CHAIN
for every graphical degree sequence
==========================================================================
An accessible exposition for a curious high school reader.
September 2026.
--------------------------------------------------------------------------
BEFORE YOU READ: what is this about, in one paragraph?
--------------------------------------------------------------------------
You have a bunch of people at a party. Each person knows a certain
number of other people there. But there are usually MANY different
"who-knows-whom" networks that give every person exactly the same
number of friends. A natural question: pick one such network truly at
random, uniformly over all the possibilities. How would you do it?
This paper settles the modern form of that question: there is a simple
"tweak one connection at a time" algorithm that produces a random
network in polynomial time -- even though the number of networks might
be astronomically large -- and moreover the tweaking really does
converge to uniform, exactly and in expected polynomial time.
That single sentence hides a long and beautiful mathematical story.
This paper proves the *simple undirected form of the Kannan-Tetali-
Vempala conjecture*: the switch chain on simple undirected graphs mixes
in polynomial time for EVERY degree sequence that can actually occur.
It also gives an EXACT uniform sampler. What you are reading now is a
guided tour that keeps every ingredient of the original proof but
explains each step in plain language, so a diligent high schooler can
follow along.
--------------------------------------------------------------------------
HOW TO READ THIS
--------------------------------------------------------------------------
The paper is structured so that you can stop at any section and still
have learned something real. Section 1 fixes vocabulary and states the
main theorem. Sections 2-8 are the "engine room": they prove a single
operator inequality H^2 >= H. Section 9 converts that into a mixing
time. Section 10 upgrades nearby-uniform to exactly uniform.
Three simple objects recur throughout:
* a SWITCH: pick two disjoint edges uv, xy; replace with ux, vy
(if those edges are absent). Degrees are preserved.
* a PAIR RESAMPLING (of vertices a={i,j}): shuffle all outside
vertices that have exactly one neighbor in {i,j}; decide which of
them are adjacent to i versus to j. Degrees are preserved.
* the OPERATOR H: sum over all vertex pairs of "how far f is from
being an average over the pair-resampling fiber". H measures how
much a test function f on graphs sees the pair resampling.
The main engine inequality H^2 >= H is proved in two pieces:
(a) triple of pairs inside a 3-vertex set (Sections 4-5)
(b) pairs that share no vertex (Sections 6-7)
Then Section 8 assembles the two pieces and shows the kernel of H is
constants, which is what gives a spectral gap.
You do NOT need to understand every technical lemma to follow the arc
of the argument. But if you do follow the arc, you will end up knowing
what a spectral gap is, why mixing time has anything to do with
eigenvalues, and how to correct the small bias of a Markov chain to
make sampling exactly uniform. Those are three of the deepest
everyday ideas in modern probability, and they are all on show here.
--------------------------------------------------------------------------
SECTION 1. VOCABULARY AND THE MAIN THEOREM
--------------------------------------------------------------------------
A GRAPH on a vertex set V = {1, 2, ..., n} is a set E of two-element
subsets of V. Think of V as people and E as friendships. A graph is
SIMPLE if no person is friends with themself and no two people are
recorded as friends twice; that is exactly the "two-element subsets"
condition. Throughout this paper all graphs are simple.
The DEGREE of a vertex v, written deg(v), is the number of edges at v,
i.e. the number of friends v has. The DEGREE SEQUENCE of a graph is the
list d = (d_1, ..., d_n) of the degrees, in the order of the labels.
A degree sequence d is GRAPHICAL if at least one simple graph has
degree vector exactly d.
Given a graphical degree vector d, let
Omega_d = { G : G is a simple graph on V = {1,...,n} with deg = d }
be the set of realizations. This set is nonempty by assumption. Let
pi_d = the uniform probability measure on Omega_d
so each realization receives probability 1/|Omega_d|. The central
question of this paper:
Given d, how do you generate a graph that is EXACTLY uniform on
Omega_d, using only a random number generator -- and how fast can
you do it?
Naively you cannot even list Omega_d: there are 2^C(n,2) possible simple
graphs on n vertices, so brute force is hopeless. The classical idea is
to walk around Omega_d with a Markov chain that has pi_d as stationary
distribution, and hope that after not too many steps the walk is close
to uniform regardless of where it started. "Close" needs a number.
--------------------------------------------------------------------------
1.1 The switch chain
--------------------------------------------------------------------------
A SWITCH removes two disjoint edges and inserts a different perfect
matching on their four vertices, IF the two new edges are absent so
that simplicity is preserved. Picture this concretely. Four distinct
vertices u, v, x, y. Suppose edges uv and xy are present, but ux and
vy are absent. The switch deletes uv and xy, and adds ux and vy:
{ uv, xy } --> { ux, vy }.
Every vertex degree is unchanged: u lost v as a friend but gained x,
v lost u but gained y, x lost y but gained u, y lost x but gained v.
That is the whole point -- switches preserve the degree sequence.
Two distinct perfect matchings of the complete graph on four vertices
are exactly the six ways to pair up {u,v,x,y} as two disjoint edges:
{uv,xy}, {ux,vy}, {uy,vx}
and the "swap" reading of the same three pairings, so six ordered
(F,F') pairs total. The switch chain picks one of these at every step.
Precise discrete-time convention (this matters for the mixing constant):
At each step,
* with probability 1/2 the chain stays put (a lazy step);
* otherwise it picks a uniformly random four-element set S of V,
picks a uniformly random one of the six ordered pairs (F, F') of
distinct perfect matchings on S, and:
- if every edge of F is present and every edge of F' is absent,
replaces F by F' (a valid switch);
- otherwise stays put (a rejected proposal).
Let P_d denote the resulting transition kernel. Since every valid
proposal is matched by a reverse proposal with the same probability,
pi_d is stationary for P_d -- in fact REVERSIBLE, meaning that the
detailed balance identity pi_d(G) P_d(G,G') = pi_d(G') P_d(G',G)
holds for every pair (G, G'). Reversibility is a technical convenience
used later when we relate eigenvalues to total variation.
--------------------------------------------------------------------------
1.2 Mixing time and total variation
--------------------------------------------------------------------------
For probability measures mu, nu on a finite set Omega, the TOTAL
VARIATION distance is
||mu - nu||_TV = (1/2) * sum_{G in Omega} |mu(G) - nu(G)|.
It is exactly the largest possible discrepancy you can create with a
single yes/no question about the state: if a gambler bets on any subset
A of Omega, the difference |mu(A) - nu(A)| is at most ||mu - nu||_TV,
and some choice of A achieves this bound. TV distance 1/4 is the
standard, forgiving threshold for "very close": nobody could
statistically distinguish two laws that are 1/4 apart in total
variation using the output of a single test.
The MIXING TIME (at threshold 1/4) of P_d is
t_mix(d) = min{ t in {0,1,2,...} :
max_{G in Omega_d} ||P_d^t(G,.) - pi_d||_TV <= 1/4 }.
So t_mix(d) is the number of steps you must run the chain so that no
matter which graph you started from, the distribution is within TV 1/4
of the uniform law. The smaller t_mix the better; if t_mix is
polynomial in n for every graphical d, we say the switch chain mixes
rapidly --- and rapidly in the strongest sense: uniformly over all
graphical degree sequences.
--------------------------------------------------------------------------
1.3 Main theorem
--------------------------------------------------------------------------
THEOREM 1 (Main theorem). For every integer n >= 4 and every graphical
degree vector d = (d_1, ..., d_n),
t_mix(d) <= 2 n^8.
Moreover, if |Omega_d| > 1 (so the chain is nontrivial), the spectral
gap of P_d is at least [ 24 n^2 * C(n,4) ]^{-1}, where C(n,4) denotes
the binomial coefficient "n choose 4".
COROLLARY 2 (Exact uniform sampling). There is a uniform randomized
algorithm that, given any finite graphical labeled degree vector
d = (d_1, ..., d_n), uses only unbiased random bits, terminates almost
surely, and outputs a graph chosen EXACTLY uniformly from Omega_d. Its
expected bit-running-time is bounded by a fixed polynomial in the
binary encoding length of d (which is roughly n log n bits).
The time bound in Corollary 2 is a bound on the EXPECTED running time.
Some executions may take much longer, and this is unavoidable: the
algorithm occasionally has to enumerate Omega_d on a rare branch. See
Section 10.
Remarks on the shape of the bound.
* The exponent 8 in the mixing time is not the main point. What
matters is that for every graphical d, at fixed threshold 1/4, the
mixing time is bounded by a polynomial in n. Improving the
constant is possible and irrelevant to the result.
* The spectral gap bound is 1 / [24 n^2 C(n,4)], roughly 1/n^6.
Since t_mix is roughly (gap^{-1}) * log(1/pi_min) and pi_min ~
2^{-n^2}, this matches the theorem's 2 n^8 up to logarithmic
factors. Nothing exotic is hiding in the constants.
--------------------------------------------------------------------------
1.4 History: what did we already know?
--------------------------------------------------------------------------
Approximate uniform generation of graphs with prescribed degrees is a
classic algorithmic problem, with applications in statistics,
network science, and combinatorics. The switch chain (a.k.a. the
degree-preserving network randomization or the swap chain) was
proposed as a practical algorithm long before anyone could analyse it.
The Kannan-Tetali-Vempala 1999 paper launched the switch-chain
program, analysed regular bipartite sequences, and raised the
possibility of broad applicability. Cooper-Dyer-Greenhill 2007 (with
a 2012 corrigendum) proved rapid mixing for regular sequences. Feder-
Guetz-Mihail-Saberi (2006) handled early irregular families. Greenhill
(2015) and Greenhill-Sfragara (2018) proved rapid mixing under certain
degree-sparsity restrictions. Amanatidis-Kleer (2020) gave the strong-
stability route. Jerrum-Sinclair (1990) and Jerrum-McKay-Sinclair
(1992) introduced the notion of stability of degree sequences that
becomes the algorithmic toolkit. Erdos-Greenhill-Mezei-Miklos-Soltesz-
Soukup (2022) unified all "P-stable" families. Erdős-Miklós-Soukup
(2025) and Erdős-Lippner-Nevo-Soukup (2025) developed further rapidly
mixing families via geometric methods.
The modern form of the Kannan-Tetali-Vempala conjecture predicted rapid
mixing for EVERY realizable degree specification, in each of three
parallel models: bipartite graphs, directed graphs, and simple
undirected graphs. Fu-Qin-Wang (2026) proved the bipartite form.
Theorem 1 here proves the simple undirected form. The three
conjectures are genuinely distinct, though the techniques overlap
heavily.
Along the way, an "undirected Curveball" resampling was studied by
Verhelst (2008), Strona et al. (2014, 2016), and Carstens-Berger-Strona
(2018). Carstens-Berger-Strona already observed that the trades on
disjoint vertex pairs can be DEPENDENT; the current paper is the first
to quantify that dependence tightly enough to prove polynomial mixing
for all graphical d.
The exact sampling approach used in Section 10 is a rare-branch
correction due to Gobel-Liu-Manurangsi-Pappik (2024), combined with
exact tabulation of the residual law. A similar tabulation appears in
the recent contingency-table sampler of OpenAI (2026).
--------------------------------------------------------------------------
SECTION 2. PAIR RESAMPLINGS AND THE OPERATOR H
--------------------------------------------------------------------------
The mixing time result will be proved not by analysing the switch chain
directly, but by analysing a related family of "macro moves" called
pair resamplings. A pair resampling is coarser than a switch -- one
move at once rearranges many edges -- and that coarse structure makes
it tractable. Once we have a spectral gap for the pair resamplings,
a short comparison turns it into a gap for the switch chain itself.
Notation. All function spaces are REAL. On Omega_d use the inner
product and norm
<f, g> = E_{pi_d}[fg], ||f||^2 = <f, f>.
For self-adjoint operators, the shorthand A >= B means
<f, (A - B) f> >= 0 for every real f.
Call this the quadratic-form order. It is only partial: A >= B and
B >= A are both true iff A = B. The engine inequality H^2 >= H is
understood in this order.
--------------------------------------------------------------------------
2.1 Pair-fibers
--------------------------------------------------------------------------
Fix an unordered vertex pair a = {i, j}. To describe what a pair
resampling of a is allowed to do, we split the data of a graph into
two groups: the data that will be HELD FIXED and the data that will be
RESAMPLED.
The data held fixed by a resampling of a = {i, j} are:
(F1) every edge with neither endpoint in {i, j};
(F2) whether the edge ij is present;
(F3) for each outside vertex w not equal to i, j: the total number
of edges from w to {i, j}. (This total is 0, 1, or 2.)
The result of fixing all this data is called an a-FIBER. Every graph
G in Omega_d belongs to exactly one a-fiber; the a-fiber is the
equivalence class of G under all resamplings of a.
Inside an a-fiber, some freedom remains: an outside vertex w that has
EXACTLY ONE neighbor in {i, j} -- call it a SINGLETON of this fiber --
can be "assigned" either to i or to j. An outside vertex with zero
neighbors in {i, j}, or with both possible edges present, has no
choice inside the fiber and contributes no freedom. But the degree of
i is fixed, so the number of singletons assigned to i is pinned down
by the data (F1)-(F3). If there are N singletons in the fiber and
q of them must be assigned to i, the resampling of a simply samples a
uniform q-subset of the N singletons to be adjacent to i; the remaining
N - q go to j. Every such choice gives a valid graph in Omega_d --
simplicity and degrees are preserved -- and every graph in the fiber
arises exactly once.
Call this motion the PAIR TRADE on a fiber. It is the "undirected
Curveball trade" of Carstens-Berger-Strona (2018). Uniform q-subsets
are the only thing happening on a fiber; this clean structure is what
will let us compare things later.
--------------------------------------------------------------------------
2.2 The projection E_a and the residual h_a
--------------------------------------------------------------------------
Because a-fibers partition Omega_d, we may define
E_a f (G) = the average of f over the a-fiber containing G.
In words, E_a "smears out" f over the fiber. It is a projection:
E_a E_a = E_a, E_a is self-adjoint w.r.t. pi_d,
E_a >= 0, and E_a 1 = 1 (constants fixed).
The RESIDUAL is the complementary projection
h_a = I - E_a.
The function h_a f vanishes exactly on the fiber of G whenever f is
already a-fiber-constant, and otherwise measures how far f deviates
from its fiber average. Both E_a and h_a are ORTHOGONAL projections:
E_a^2 = E_a, E_a^* = E_a, h_a^2 = h_a, h_a^* = h_a,
with h_a killing constants and h_a f orthogonal to E_a-fiber-functions.
This construction is the partition-based heat-bath of Dyer-Greenhill-
Ullrich (2014). It eliminates any need for "conditional distributions"
or "transition matrices" in the analysis: we work entirely with
orthogonal projections built out of fibers.
--------------------------------------------------------------------------
2.3 The sum operator H
--------------------------------------------------------------------------
Sum the residuals over every vertex pair:
H = sum_{a in C(V,2)} h_a.
Two useful facts.
* H is positive semidefinite. Being a sum of orthogonal projections
h_a >= 0, H >= 0. So <f, Hf> >= 0 always.
* H kills constants. Each h_a does, so H 1 = 0, and
<1, H 1> = 0 confirms the constants sit in the kernel.
The engine inequality is
(ENGINE) H^2 >= H.
In eigenvalue terms (writing H for a symmetric operator on the finite-
dimensional space of all real functions on Omega_d, orthogonal
decomposition relative to pi_d): on the 1-dimensional space of
constants, H acts by 0, so both H and H^2 act by 0 there and the
inequality is trivially true. On the orthogonal complement (the
"centered" functions), ENGINE says that every eigenvalue lambda of H
restricted to centered functions satisfies
lambda^2 >= lambda, i.e. lambda >= 1 (or lambda = 0).
Equivalently, H has a SPECTRAL GAP of at least 1 on the centered
subspace: H >= the projection onto the centered subspace.
Once ENGINE is proved, Section 9 will use it to bound the mixing time
of P_d. Section 8 will additionally verify that the only functions
killed by H are constants, which upgrades "gap >= 1 on centered
functions" to a genuinely non-degenerate gap.
Why this form of H is tractable. H is a sum of ~ n^2 projections.
Its square is a sum of ~ n^4 ordered pairs h_a h_b; what matters about
each pair is whether it COMMUTES with the other. The partition of
pairs into "intersecting" and "disjoint" is natural. Two pairs a, b
sharing a vertex do NOT commute: each resamples the shared vertex's
neighborhood, and the two choices clash. Pairs with a and b disjoint
also do NOT commute: they both touch the four edges between the two
pairs (Carstens-Berger-Strona noticed this "dependence of undirected
trades" in 2018). So the engine inequality is not a triviality that
falls out of a commuting family of operators. Each family needs its
own estimate.
--------------------------------------------------------------------------
2.4 Plan of attack, section by section
--------------------------------------------------------------------------
Split the sum over ordered pairs (a, b) of vertex pairs into two
groups:
(TRIPLES) a and b share a vertex, so a union b is a vertex TRIPLE
T. On a fixed triple T, there are three vertex pairs,
and every ordered pair of distinct pairs has union T.
Contribution: sum over triples T of H_T^2, where
H_T = sum_{a in C(T,2)} h_a is the projection to a single
triple. Sections 3-4 prove H_T^2 >= H_T.
(DISJOINT) a and b do not share a vertex. Contribution:
D = sum_{a, b disjoint} h_a h_b. Sections 5-7 prove D
is positive semidefinite.
If both pieces hold, then
H^2 = sum_T H_T^2 - (n - 3) H + D
>= sum_T H_T - (n - 3) H + 0
= (n - 2) H - (n - 3) H = H,
where the combinatorial identity H^2 = sum_T H_T^2 - (n - 3) H + D is
a regrouping of the ordered double sum (see Section 8). This is
exactly ENGINE, and it is the core of the paper.
Sections 3-4 handle the triple terms with a variance inequality for a
3-row binary matrix. Sections 5-7 handle the disjoint terms, first by
identifying a rank-one correlation between the two resamplings, then
bounding that correlation with a slice inequality. Sections 8-10 wrap
everything up.
--------------------------------------------------------------------------
SECTION 3. THE THREE-ROW VARIANCE INEQUALITY
--------------------------------------------------------------------------
The estimate proved in this section has nothing to do with graphs. It
concerns 3-row binary matrices with prescribed row and column sums, and
it says that the variance of a sum of three "row functions" is at most
twice the sum of their variances. The factor 2 is the crucial detail
of the whole paper. A sloppier constant (say 3) would still give
polynomial mixing; a constant that GREW with n would not. So the tight
factor 2 is earned.
The result is equivalent to a conditional-projection inequality proved
by Fu-Qin-Wang (2026, Theorem 5.1) in the bipartite setting. Their
proof goes through a swap chain and a variance argument; the version
below uses "transpositions and spectral decomposition", which is more
elementary. Both proofs share the same count-coupling step (their
Lemmas 5.2-5.4).
The variance argument via transpositions is inspired by the symmetric-
group heat-flow method of Carlen-Lieb-Loss (2006). Section 3 below is
self-contained; only the count-coupling step explicitly carries the
Fu-Qin-Wang attribution.
--------------------------------------------------------------------------
3.1 Two-row warm-up: what does the inequality say?
--------------------------------------------------------------------------
Before the technicalities, look at the simplest case. Fix a 2-row
binary matrix M with prescribed row sums and column sums. Each column
of M is one of three types: (1,0), (0,1), or (1,1). Write U_1 for
the set of "1,0" columns, U_2 for "0,1" columns, W for "(1,1)" columns.
The column-sum constraint pins down |U_1|, |U_2|, and |W| exactly.
Now choose M UNIFORMLY from all 2-row matrices with those margins.
That means: choose a uniform ordered partition (U_1, U_2) of a fixed
set of "single-one" columns, and put all the "(1,1)" columns in W.
Each row function f_i (M) depends only on row i of M, i.e. on the
choice of U_i and W.
The variance identity you probably know is
Var(X + Y) = Var(X) + Var(Y) + 2 Cov(X, Y).
If X and Y were independent, the cross term would vanish and we would
have Var(X + Y) = Var(X) + Var(Y). Here X and Y are NOT independent:
the choice of U_1 and U_2 is complementary. Sometimes the negative
cross term can be as bad as -Var(X) - Var(Y), in which case the
variance of X + Y can be ZERO even when X, Y vary independently --
think of X = -Y. The whole content of the 3-row inequality is that
when there are THREE rows instead of two, you still have enough
freedom in the third coordinate that the variance cannot collapse:
Var(X_1 + X_2 + X_3) <= 2 ( Var(X_1) + Var(X_2) + Var(X_3) ).
The factor 2 is necessary: with only 2 rows, you can make the variance
of a sum arbitrarily much smaller than the sum of variances, and there
is no analogous bound. With 3 rows, the third coordinate acts as an
independent "outlet", and the factor-2 bound is possible. Fu-Qin-Wang
proved the bipartite version of this in 2026, and it is the technical
heart of both their paper and ours.
--------------------------------------------------------------------------
3.2 The fixed-block case
--------------------------------------------------------------------------
Formally: let U and W be finite labelled sets. Let (U_1, U_2, U_3) be
a uniform ordered partition of U with prescribed block sizes; let
(W_1, W_2, W_3) be a uniform ordered partition of W with prescribed
block sizes; assume the two partitions are independent. For three
dimensionless real functions g_1, g_2, g_3, where g_i depends only on
the pair (U_i, W_i), we claim
LEMMA 3.1 (fixed block sizes).
Var(g_1 + g_2 + g_3) <= 2 ( Var(g_1) + Var(g_2) + Var(g_3) ).
Note that g_i is a function of row i only; "block sizes fixed" means
|U_i| and |W_i| are constants, not random.
Proof sketch for the curious. The idea is to find a self-adjoint
operator J on functions of (U_1,U_2,U_3;W_1,W_2,W_3) whose kernel is
the constants, and whose quadratic form is the sum of squared
"differences" over all transpositions of labels. Specifically,
J = sum_{tau} (I - T_tau)
where tau ranges over transpositions of 2 labels within U or within W,
and T_tau acts by permuting those labels. Each T_tau is a self-adjoint
involution; the contribution of transposition tau to <f, Jf> is exactly
(1/2) E(f - T_tau f)^2. The permutations of U, W generated by these
transpositions act transitively on the ordered partitions with given
sizes; so J kills exactly the constants.
Two facts follow from this. First, for any function g_i of row i, the
space of such functions is invariant under J: a transposition within U
changes g_i only when it swaps labels between U_i and another block, and
the resulting block is determined by U_i and the two labels -- not by
which other block contains the "outside" label. Same for W. So if g_i
has spectral decomposition sum_lambda g_{i,lambda} (eigenfunctions of J),
each g_{i,lambda} is again a function of row i.
Second, apply J to the sum g_1 + g_2 + g_3. For a single transposition
tau, at most two of the three g_i change (because a transposition
swaps exactly 2 labels, so it moves labels into and out of exactly 2 of
the 3 U-blocks -- same for W-blocks). The elementary inequality
(x + y + z)^2 <= 3 (x^2 + y^2 + z^2)
would give a factor 3, but we can do better: since only two of the three
terms are nonzero at each transposition, we get
(x + y + z)^2 <= 2 (x^2 + y^2 + z^2)
with the factor 2. Sum over transpositions and evaluate <(g_1+g_2+g_3),
J(g_1+g_2+g_3)> using the spectral decomposition: it equals
sum_lambda lambda * ||g_1,lambda + g_2,lambda + g_3,lambda||^2, and
by the transposition bound this is at most
2 * sum_lambda lambda * (||g_1,lambda||^2 + ||g_2,lambda||^2 + ||g_3,lambda||^2)
= 2 * sum_i <g_i, J g_i> = 2 * sum_i Var(g_i).
The left side is Var(g_1 + g_2 + g_3) after subtracting the means; the
divisibility by lambda at each eigenvalue (and lambda > 0 on centered
functions) closes the argument.
End of proof sketch. Full details: the invariant-coordinate
observation (transposition of a U-label swaps in/out of exactly 2
U-blocks) and the transitivity of the permutation action are the only
places specific facts about U, W are used. Empty blocks and singleton
label sets cause no trouble: a one-state space has no nonzero centered
functions, so both sides of the inequality are zero there.
--------------------------------------------------------------------------
3.3 The random-block-count case
--------------------------------------------------------------------------
The block sizes are fixed above. But in the graph application, the
block sizes themselves are random: which columns of the matrix are
"(1,1)" columns depends on the graph.
Formally: fix nonnegative integers m, alpha_1, alpha_2, alpha_3. Let
x = (x_1, x_2, x_3) be a random nonnegative integer triple with
x_1 + x_2 + x_3 = m, distributed with probability proportional to
w_1(x_1) w_2(x_2) w_3(x_3),
w_i(t) = 1 / ( t! (t + alpha_i)! ).
For any three real functions b_1, b_2, b_3 of one integer coordinate,
LEMMA 3.2 (random block counts).
Var(b_1(x_1) + b_2(x_2) + b_3(x_3))
<= 2 ( Var(b_1(x_1)) + Var(b_2(x_2)) + Var(b_3(x_3)) ).
The proof needs a small tool: a STOCHASTIC COMPARISON for the
distributions of x_i at adjacent totals. Fu-Qin-Wang's Lemma 5.2 (see
also Lemma 5.4 of their paper) shows that the distribution of x_i is
monotone as the total m grows: it is stochastically increasing, in the
sense that P(x_i >= t) is non-decreasing in m. Their proof: the ratio
of the probabilities at t and at t-1 has the form 1/[(s-t)(s-t+alpha)]
for an index s, which is non-decreasing in t; reweighting any measure by
a non-decreasing function increases the expectation of any non-decreasing
test function (a covariance identity that follows from the 2-point
positivity of the covariance kernel).
The key consequence is a COUPLING: if we fix the total m and consider
the two distributions of x_i at totals m and m-1, we can couple them on
a common probability space so that exactly one of the coordinates
increases by one (or zero, depending on which coordinate they come
from). Specifically, Fu-Qin-Wang's Lemma 5.2 constructs a coupling
with
x_i^{(m-1)} <= x_i^{(m)} <= x_i^{(m-1)} + 1
(for the appropriate choice of two coordinates).
Precise statement: at a fixed total, the pair (x_j, x_k) with
x_j + x_k = s, for two of the three indices, has a joint law
proportional to w_j(y) w_k(z) on y + z = s. As s grows by one, the
marginal of x_j is stochastically non-decreasing, and the marginal of
x_k is stochastically non-increasing, but the SUPPORT allows only
shifts of 0 or 1 in x_j. A coupling via quantile functions (the
inverse-cumulative-distribution trick, which is a completely
elementary construction) makes the "0 or 1" jump deterministic. This
is the content of Fu-Qin-Wang's Lemma 5.2 and the count-coupling
observation of Carlen-Lieb-Loss (their Section 2).
Given the coupling, the proof of Lemma 3.2 is short. Let A be the
linear map
A(b_1, b_2, b_3) = b_1(x_1) + b_2(x_2) + b_3(x_3).
The squared norm of (b_1, b_2, b_3) on the direct-sum space is
sum_i ||b_i||^2; the squared norm of the sum is what we want to bound.
Equivalently: bound the LARGEST EIGENVALUE lambda of A^* A by 2. A
corresponding eigenvector gives a system (one equation per coordinate):
lambda * b_i(t) = E[ b_1(x_1) + b_2(x_2) + b_3(x_3) | x_i = t ].
Conditioning on x_i = t leaves the other two coordinates with total
s = m - t. For adjacent values t and t+1, couple the other two
coordinates via the coupling above: one of them decreases by one
(deterministically), so the conditional expectation of
b_1(x_1) + b_2(x_2) + b_3(x_3), as a function of the (i-th excluded)
coordinates, changes by at most the maximum adjacent increment
M = max over i, t of | b_i(t+1) - b_i(t) |.
Subtract the eigen-equation at t and at t+1:
| (lambda - 1) (b_i(t+1) - b_i(t)) | <= M.
Choose i, t attaining M; divide by M > 0 (M is positive because
otherwise every b_i is constant and hence zero after centering, which
contradicts lambda being the largest eigenvalue of A^*A restricted to
centered functions):
|lambda - 1| <= 1.
So lambda <= 2. That is Lemma 3.2.
--------------------------------------------------------------------------
3.4 Combining: the three-row variance inequality
--------------------------------------------------------------------------
Now put the two pieces together. Fix row sums r_1, r_2, r_3 and column
sums c_1, ..., c_N for a 3-row binary matrix with N columns. Let M
be a uniform random binary matrix with those prescribed margins, and
let S_i denote the i-th row of M. For arbitrary real functions f_1,
f_2, f_3:
LEMMA 3.3 (three-row variance inequality).
Var(f_1(S_1) + f_2(S_2) + f_3(S_3))
<= 2 ( Var(f_1(S_1)) + Var(f_2(S_2)) + Var(f_3(S_3)) ).
Here is how the two previous lemmas combine. A column of sum 0 or 3
is deterministic: it either contributes nothing to any row, or a "1"
to every row. Remove all such columns and adjust the row sums; they
contribute a constant to f_i(S_i), so they do not affect any variance.
Remaining columns have sum 1 or 2. Color each remaining column by its
type: a "1-column" has exactly one 1, and this distinguishes one of the
three rows; a "2-column" has exactly one 0, and this distinguishes one
of the three rows. Let U_i be the set of "1-columns" whose unique 1
is in row i, and let W_i be the set of "2-columns" whose unique 0 is
in row i. The nondeterministic part of row i is exactly (U_i, W_i): the
set of "1-columns" assigned to i, plus the set of "2-columns" assigned
to i (i.e. columns that are 0 at row i and 1 at the other two rows).
Let k_i = |W_i|. Row-sum constraint at i gives the number of "1-
columns" at row i:
|U_i| = k_i + delta_i,
where delta_i is a sum of small integers fixed by the row sum of M.
So conditional on the vector k = (k_1, k_2, k_3), the two partitions
(U_1, U_2, U_3) and (W_1, W_2, W_3) are independent uniform ordered
partitions with prescribed block sizes. Lemma 3.1 applies.
Now the distribution of k itself. Counting the partitions shows:
P(k is proportional to prod_i 1/( k_i! * (k_i + delta_i)! ) ),
with k_i >= 0, k_i + delta_i >= 0, k_1 + k_2 + k_3 = |W|.
This is exactly the shape of Lemma 3.2 with
l_i = max(0, -delta_i), x_i = k_i - l_i,
alpha_i = |delta_i|, m = |W| - sum_i l_i,
after which the support is all nonnegative triples of sum m and the
weights are prod_i 1/( x_i! (x_i + alpha_i)! ). Lemma 3.2 applies.
The final combination is the law of total variance:
Var(f_1(S_1) + f_2(S_2) + f_3(S_3))
= E[ Var(f_1 + f_2 + f_3 | k) ]
+ Var( E[f_1 + f_2 + f_3 | k] ).
Apply Lemma 3.1 (fixed block sizes) to the first term, giving at most
2 E[ sum_i Var(f_i | k) ]. Then note that E[f_i(S_i) | k] depends only
on k_i (as |U_i| = k_i + delta_i), so the second term is a sum of three
functions b_i(x_i) and Lemma 3.2 gives at most 2 sum_i Var(b_i(x_i)).
Adding, and using the identity
Var(f_i(S_i)) = E[ Var(f_i | k) ] + Var( E[f_i | k] ),
we get Var(sum f_i) <= 2 sum_i Var(f_i) as claimed.
End of Section 3.
--------------------------------------------------------------------------
SECTION 4. TRIPLE RESAMPLINGS: H_T^2 >= H_T
--------------------------------------------------------------------------
Now we use Section 3 to handle the "intersecting pairs" piece of
ENGINE. Fix a vertex triple T = {i, j, k} of size 3. There are three
vertex pairs inside T:
{i,j}, {j,k}, {i,k}.
Every pair {x,y} inside T corresponds to a projection h_{ {x,y} }. Sum
them:
H_T = h_{ {i,j} } + h_{ {j,k} } + h_{ {i,k} }.
This is exactly the sum of three residuals over the three vertex pairs
of T. The goal of this section is
PROPOSITION 4.1. H_T^2 >= H_T.
Since the three h_a are projections (h_a^2 = h_a, self-adjoint), H_T
is self-adjoint and positive semidefinite. H_T kills constants, since
each h_a does. To prove H_T^2 >= H_T we must show every eigenvalue of
H_T on centered functions is either 0 or >= 1.
The key idea: on each "cell" of a natural partition, H_T is CONJUGATE
(via a bijection of the state space) to the variance operator of a 3-
row binary matrix with fixed margins. Once you are in that domain,
Lemma 3.3 (three-row variance) does the whole job.
--------------------------------------------------------------------------
4.1 The cell partition
--------------------------------------------------------------------------
Partition Omega_d by recording:
(C1) the graph induced on V \ T, i.e. all edges with neither endpoint
in T;
(C2) for each outside vertex w not in T, the number of edges from w
to T. This number is an integer in {0, 1, 2, 3}.
This is a "T-cell". A pair resampling of {i,j} (for i, j in T) preserves
this cell: it changes only which of i or j receives each singleton-w
neighbor w (from the perspective of {i,j}-fibers), and cells (C1)-(C2)
record counts that do not distinguish i from j inside the pair.
Fix a nonempty cell. Its conditional uniform measure makes the graphs
in the cell into a "finite probability space of fixed-margin binary
matrices". The next subsection proves this precisely and identifies
H_T with a variance of row functions.
Within a cell, let e = number of edges of G that lie inside T. Since
d is fixed by the cell (degrees of all vertices fixed), e is fixed by
the cell (sum of degrees in T = 2e + sum over outside contributions to
T). So e is a constant of the cell, in {0, 1, 2, 3}.
--------------------------------------------------------------------------
4.2 The matrix encoding
--------------------------------------------------------------------------
We build a binary matrix with rows indexed by T (three rows) and columns
indexed by V \ T (n-3 columns) plus, if e is 1 or 2, ONE extra column
(indexed, say, by the symbol *). The entries are:
* for w in V \ T and i in T: M[i, w] = 1 if edge iw is present,
else 0. This is exactly what "the number of edges from w to T"
records (its column sum);
* the extra column, when present, encodes the internal edges of T:
- e = 0: no extra column. Row sums are d_i (each i has all its
degree coming from V \ T alone).
- e = 3: no extra column. Row sums are d_i - 2 (each i has two
of its degree inside T).
- e = 1: the sole edge is, say, ij. Extra column is s = (s_i, s_j,
s_k) = (1, 1, 0). Row sums are d_i - 1 for all i.
- e = 2: the two edges form a path, centered at some vertex, say
i, with edges i-j and i-k. The extra column entries are
(s_i - 1, s_j - 1, s_k - 1) = (1, 0, 0), sum 1.
The original paper uses a table. Reproduced in plain text:
e | internal graph | extra column | row sums at i in T
---+--------------------+----------------+---------------------
0 | empty | none | d_i
1 | single edge | s_i, sum 2 | d_i
2 | path | s_i - 1, sum 1| d_i - 1
3 | triangle | none | d_i - 2
Explanation of the "extra column" column:
e = 1: the extra column has a single 1 at row i and a single 1 at
row j (the endpoints of the edge), so the "extra column sum" is 2.
Encoding: entries (1,1,0) on (i,j,k). Each vertex of T loses 1 to
the internal edge, so its internal-external degree is d_i - 1 from
the outside; the external column sums are exactly that.
e = 2: a path has a center (say vertex i, with two edges i-j, i-k).
The extra column has a single 1 at the center i (sum 1). Each
vertex contributes 1 or 2 to the internal sum, so the outside degree
corrected by s_i - 1 = 1 for center, 0 for endpoints, works out to
d_i - 1.
e = 0: no extra column; internal degrees all 0; row sum = d_i.
e = 3: no extra column; internal degrees all 2; row sum = d_i - 2.
The crucial observation: this encoding is a BIJECTION from cell graphs to
binary matrices with the prescribed row sums and column sums (columns
include the extra column iff e = 1 or e = 2). Two directions:
-> (graph to matrix): read off edges from T to outside; record the
extra column from the internal graph.
<- (matrix to graph): the outside edges come from the entries in
V \ T columns; the internal edges come from the extra column (or
are deterministic when e = 0, 3).
Every cell graph arises exactly once, and every fixed-margin matrix
gives a valid cell graph. Since the cell measure is uniform on graphs,
it is uniform on matrices.
Question: is the conditional measure really UNIFORM on this matrix
space? Yes: the definition of a cell fixes the total number of edges
from each vertex, i.e. the row sums of the matrix; the definition of
the column sums is by construction; and within a cell every completion
to a valid graph has the same number of "underlying" edge-configurations
because the graph space is simply the product of outside-edges and
internal-edges, and the internal edges are encoded exactly by the
extra column. So each fixed-margin matrix has equal probability 1/(#of
matrices). Uniform.
--------------------------------------------------------------------------
4.3 The three projections on a cell
--------------------------------------------------------------------------
Now identify what h_{ {j,k} }, h_{ {i,k} }, h_{ {i,j} } do, inside this
cell, in matrix terms.
Fix i in T, let {j,k} = T \ {i}. Consider h_{ {j,k} }, i.e. E_{ {j,k} }
projected on {j,k}-fibers.
Claim: within the cell, E_{ {j,k} } f = E[ f | S_i ], where S_i is
(augmented) row i of the matrix.
Reason:
* External entries of row i determine the singleton assignment of
each w in V \ T to i: w is adjacent to i in the {j,k}-fiber iff
the entry M[i, w] is 1.
* Whether M[i, *] is 1 (the extra column) is determined by the e
and the internal structure, hence by the cell data -- the specific
internal degree s_i is encoded in the extra column and is pinned by
cell data + degree.
* So the {j,k}-fiber is determined by: the cell data (fixed), plus
the external neighbors of i (row i of the matrix in the V \ T
columns).
* Conversely, fixing the {j,k}-fiber fixes the external neighbors of
i (those vertices w that are in the fiber with i as neighbor are
exactly the ones with M[i,w]=1). So the projection onto {j,k}-
fibers equals conditioning on row i.
Nothing else about the fiber is left free: the "outside graph" is
determined by cell data; the internal graph (edge jk, or path / triangle
involving i) is determined by extra column, which is determined by
row i's augmented entries and by the cell constants.
Hence h_{ {j,k} } acts within the cell as the PROJECTION onto the
complement of row-i-functions. Since E_{ {j,k} } = E[.|S_i], the
residual h_{ {j,k} } = I - E[.|S_i], giving
<f, h_{ {j,k} } f> = ||f||^2 - ||E[f | S_i]||^2.
In matrix language: h_{ {j,k} } measures how far f is from being a
function of row i alone.
Similarly, h_{ {i,k} } is "conditional on row j", h_{ {i,j} } is
"conditional on row k". So
H_T f = sum_i (f - E[f | S_i]) = 3f - sum_i E[f | S_i],
where sum is over the three rows.
--------------------------------------------------------------------------
4.4 The variance inequality
--------------------------------------------------------------------------
Let f be a function on the cell, centered in the sense E[f] = 0
relative to the uniform cell measure. (Constants play no role in H_T;
we subtract the cell mean.)
Define P_i f = E[f | S_i], the projection onto row-i-functions (as an
operator on the cell's function space). These are orthogonal
projections commuting with nothing much, but each is a genuine
projection: P_i is averaging over the i-fiber, so P_i^2 = P_i and P_i
is self-adjoint. Also each P_i f is a row-i function, hence a function
of S_i.
We need to compute <f, H_T f> = sum_i <f, (I - P_i) f>. For each i:
<f, (I - P_i) f> = ||f||^2 - <f, P_i f>
= ||f||^2 - ||P_i f||^2 (P_i^2 = P_i)
= ||f||^2 - <P_i f, P_i f>.
Sum over i:
<f, H_T f> = 3 ||f||^2 - sum_i ||P_i f||^2.
Lemma 3.3 (three-row variance) applies to a sum of three row functions
of a common fixed-margin matrix. The quantity we want to bound is
b = sum_i ||P_i f||^2,
where each P_i f is a function of the single row S_i of our matrix.
Rewrite b as an inner product. Since each P_i is a projection fixing
row-i functions, <f, P_i f> = <P_i f, P_i f> = ||P_i f||^2. So
b = sum_i <f, P_i f> = <f, (sum_i P_i) f>,
and Cauchy-Schwarz gives
b <= ||f|| * || sum_i P_i f ||.
Now sum_i P_i f is a sum of three row functions. Since f is centered
in the cell and each P_i is a projection fixing constants, E[P_i f] = 0.
So Var(sum_i P_i f) = ||sum_i P_i f||^2. Apply Lemma 3.3:
|| sum_i P_i f ||^2 = Var( sum_i P_i f )
<= 2 sum_i Var( P_i f )
= 2 sum_i ||P_i f||^2
= 2 b.
So b <= ||f|| * sqrt(2b). If b = 0 the conclusion b <= 2||f||^2 is
trivial; otherwise divide by sqrt(b) to get sqrt(b) <= sqrt(2) ||f||,
i.e. b <= 2 ||f||^2 either way.
Therefore
<f, H_T f> = 3 ||f||^2 - b >= 3 ||f||^2 - 2||f||^2 = ||f||^2.
Since f was arbitrary, H_T >= I on centered functions. To convert
that to H_T^2 >= H_T: on centered functions every eigenvalue lambda of
the self-adjoint operator H_T is at least 1, hence lambda^2 >= lambda.
That is exactly H_T^2 >= H_T on the same subspace. So the argument is:
1. H_T is self-adjoint and positive semidefinite (sum of projections).
2. H_T kills constants (each h_a does).
3. On the orthogonal complement of constants, H_T >= I (just shown).
4. So on the orthogonal complement of constants, every eigenvalue
lambda of H_T satisfies lambda >= 1, hence lambda^2 >= lambda.
5. On constants, both H_T and H_T^2 act by 0.
Combining: H_T^2 >= H_T on the whole space.
That is Proposition 4.1. QED.
--------------------------------------------------------------------------
4.5 From cells to the whole space
--------------------------------------------------------------------------
There is one last technical point. Proposition 4.1 is proved cell by
cell (each cell has its own uniform measure and its own model as a 3-
row matrix). Does the cellwise inequality on H_T^2 >= H_T imply the
global inequality on H_T^2 >= H_T?
Yes, because H_T PRESERVES CELLS. Each cell is a "block diagonal"
subspace for H_T: the operator h_a maps cell-constant functions to
cell-constant functions and does not mix cells. So H_T = sum over
cells of "H_T restricted to cell". The quadratic form <f, H_T^2 f> is
a sum over cells of the cellwise <f_cell, H_T^2|_{cell} f_cell>. Same
for <f, H_T f>. The cellwise inequality implies the global one.
(There is one harmless corner case: a cell might be a SINGLE graph.
That is, its conditional measure puts all mass on one point. Then the
cell's function space is 1-dimensional, f is constant on the cell, and
H_T acts by 0, both on H_T and H_T^2. Trivially H_T^2 >= H_T.)
So Proposition 4.1 holds on Omega_d for every triple T. This finishes
the first half of the engine inequality.
End of Section 4.
--------------------------------------------------------------------------
SECTION 5. DISJOINT-PAIR INTERACTION
--------------------------------------------------------------------------
We turn to the second half of ENGINE: disjoint vertex pairs. Here the
story gets genuinely subtle. Two pairs a = {i, j} and b = {k, l} that
share no vertex can BOTH rearrange the four edges between them, and
those two rearrangements interfere: they modify the SAME four edges.
Carstens-Berger-Strona (2018) already observed this "dependence of
undirected trades" and used it as a reason to avoid the analysis. We
cannot avoid it. What we can do is CONTROL it precisely: on each a-
fiber the two resamplings overlap in at most a rank-one subspace, and
that rank-one subspace is bounded by a new projection which in turn is
dominated by the "available" switch energy (proved in Section 6).
The clean local statement is Proposition 5.1 below. Sections 5.1-5.6
prove it. Section 7 sums it over all disjoint pairs.
--------------------------------------------------------------------------
5.1 The cross-switch T_{a,b} and the operator g_{a,b}
--------------------------------------------------------------------------
Fix disjoint vertex pairs a = {i, j} and b = {k, l}. Consider the
2-by-2 CROSS MATRIX between a and b:
M(G) = ( M[i,k], M[i,l] ; M[j,k], M[j,l] ) (2 rows, 2 cols)
whose entry in position (x, y) is 1 iff xy is an edge of G. There are
16 possible 2-by-2 binary matrices; the SET of achievable ones depends
on the rest of G, but every entry records an actual edge-or-not.
Define the involutive map T_{a,b} on Omega_d:
If M(G) has every row sum and every column sum equal to 1
(i.e., M is one of the two "permutation matrices"),
T_{a,b}(G) = G' whose cross entries are the OTHER permutation
matrix on the same support (equivalently: swap the two entries
of each row), with every other edge of G unchanged.
Otherwise,
T_{a,b}(G) = G (the identity).
So T_{a,b} toggles the four cross edges when the cross matrix is a
permutation matrix. Each of the four vertices i, j, k, l loses exactly
one cross edge and gains exactly one. Zero sum. Degree-preserving,
simple-graph-preserving. Also T_{a,b} is an involution: T_{a,b}^2 = I.
And T_{a,b} is an isometry of pi_d.
Define the ANTISYMMETRIC projection
g_{a,b} = (I - T_{a,b}) / 2.
This is an orthogonal projection (over reals, T_{a,b} is self-adjoint).
It kills everything fixed by T_{a,b} and projects onto the antisymmetric
part. Also g_{a,b} = g_{b,a}.
Two useful facts follow from the definition of T_{a,b}:
* T_{a,b} preserves the a-fiber and the b-fiber of G. A cross-toggle
only swaps which neighbor is adjacent to which vertex WITHIN the
pair {i, j} or WITHIN the pair {k, l}; the total number of edges
from each outside vertex w into {i, j} (respectively into {k, l})
is unchanged. So T_{a,b} maps each a-fiber to itself and each
b-fiber to itself.
* T_{a,b} commutes with E_a and E_b. Both E_a and E_b average over
fiber data that T_{a,b} preserves, so applying T_{a,b} before or
after averaging gives the same result. Consequently g_{a,b}
commutes with E_a and E_b too, and therefore kills both A = functions
of X (the a-fiber data) and B = functions of Y (the b-fiber data).
So ran(g_{a,b}) fits inside J = (A+B)^perp.
Let's not be too abstract; concrete is better. Here is the setup.
--------------------------------------------------------------------------
5.2 The cell decomposition
--------------------------------------------------------------------------
Fix disjoint vertex pairs a = {i,j} and b = {k,l}. Let
O = V \ (a union b) (the other n - 4 vertices).
Partition Omega_d by recording:
(D1) the graph induced on O;
(D2) whether edge ij is present;
(D3) whether edge kl is present;
(D4) for each w in O, the number of edges from w into a (0, 1, or 2);
(D5) for each w in O, the number of edges from w into b (0, 1, or 2).
Each such "cell" is a set of graphs with a common value of (D1)-(D5).
Both pair resamplings of a and of b preserve every cell.
Two key counts within a cell that will not vary:
A_0 = { w in O : w has exactly 1 neighbor in a } (the a-singletons)
B_0 = { w in O : w has exactly 1 neighbor in b } (the b-singletons)
and the degree-sum identity
d_i + d_j + d_k + d_l
= 2 s + 2 [ij present] + 2 [kl present]
+ sum_{w in O} (neighbors_a(w) + neighbors_b(w))
where s = number of edges between a and b. Every term on the right
except s is fixed by cell data, so s is fixed by the cell. Important:
s determines which cases we are in.
Fix a nonempty cell. Call its conditional uniform measure the CELL
WEIGHT.
--------------------------------------------------------------------------
5.3 The (M, U, W) encoding
--------------------------------------------------------------------------
Inside a cell, the data not yet fixed by cell alone are exactly:
M = (edges between a and b), a 2-by-2 binary matrix:
M[ik], M[il]; M[jk], M[jl].
U = the subset of A_0 whose unique neighbor inside a is i;
equivalently U = {w in A_0 : i-w is an edge}.
W = the subset of B_0 whose unique neighbor inside b is k;
equivalently W = {w in B_0 : k-w is an edge}.
The graph is fully determined by (M, U, W) plus the cell data. Indeed:
* every edge in O is fixed by (D1);
* the edges ij, kl come from (D2)-(D3);
* every edge from w in O to a comes from w's count (D4) plus its
indicator "w in U";
* every edge from w in O to b comes from w's count (D5) plus its
indicator "w in W";
* every edge from a to b comes from M.
Conversely, any (M, U, W) with the right sizes gives a valid cell graph.
Size constraints. Let
r = M[ik] + M[il] (row sum at i, count of b-neighbors of i)
c = M[ik] + M[jk] (col sum at k, count of a-neighbors of k)
are the row-i sum and column-k sum of M. Then the degree constraints at
i and k give
|U| = q_0 - r, |W| = q_1 - c,
where q_0, q_1 are fixed nonnegative integers (functions of the cell).
Symmetric constraints hold at j and l: |A_0| - |U| = q_0' - (s - r)
and |B_0| - |W| = q_1' - (s - c) for two more cell-constants q_0', q_1'.
Consequence: conditional on M, the pair (U, W) is distributed as
U = uniform random q_0 - r-subset of A_0,
W = uniform random q_1 - c-subset of B_0,
U independent of W.
And marginal in M: M is uniform over the binary 2-by-2 matrices of
total s that are feasible with the cell sizes.
Uniform over the cell. This encoding is a bijection, and every (M,U,W)
satisfying the size constraints corresponds to exactly one graph. So
the cell measure is uniform on this set.
Two-fiber data. The a-fiber at a graph in this cell contains ALL graphs
with the SAME (c, W) and the SAME cell data, varying only M subject to
c fixed (so r varies) and varying U. Similarly the b-fiber data is
Y = (r, U), varying M subject to r fixed and varying W. So:
X = (c, W) = the a-fiber label
Y = (r, U) = the b-fiber label
E_a f = E[ f | X ], E_b f = E[ f | Y ].
Note two facts:
(i) T_{a,b} preserves X and Y: it swaps the two entries of each
row of M, so c and r are unchanged; U and W are unchanged.
Hence T_{a,b} acts on (A + B)^perp, and ran(g_{a,b}) fits in J.
(ii) The full graph data is (X, Y): from X = (c, W) we know c and W,
from Y = (r, U) we know r and U. Given (c, r) and the cell (so s
is known), the matrix M is uniquely determined UNLESS
s = 2 and (r, c) = (1, 1); see the table below.
--------------------------------------------------------------------------
5.4 The case table for s
--------------------------------------------------------------------------
The total number of cross-edges s runs from 0 to 4. Here is the
behaviour of each case.
s = 0 or s = 4.
M is all zeros or all ones. Then r and c are forced: 0 in the
first case, 2 in the second. So X = (0, W) and Y = (0, U), and
U, W are independent uniform subsets of fixed sizes. Hence X, Y
are INDEPENDENT. Also T_{a,b} is the identity (no permutation
matrix is ever reached), so g_{a,b} = 0.
s = 1 or s = 3.
M has a single 1 (s = 1) or a single 0 (s = 3). In both cases
(r, c) determines M uniquely: for s = 1, it specifies the
position of the unique 1; for s = 3, the unique 0. So given
the cell and (r, c), M is determined. The sizes |U| = q_0 - r
and |W| = q_1 - c are then fixed. Since the subset restrictions
on U and W are independent and each is a uniform fixed-size
subset, X, Y are again INDEPENDENT.
s = 2, center absent.
The "center" is (r, c) = (1, 1). For s = 2 the six possible
matrices are:
c=0 c=1 c=2
r=0 -- [0 0;1 1] --
r=1 [0 1;0 1] [1 0;0 1] [1 0;1 0]
[0 1;1 0]
r=2 -- [1 1;0 0] --
If the center is infeasible (no (1,1) matrix is compatible with
cell sizes), the support is confined to a single row OR column
of the table: either no r differs from 1, or no c differs from
1. Suppose it's a single row, say r = 1. Then Y = (1, U)
with r fixed; X = (c, W) with c varying but W uniform of size
q_1 - c independent of c. By the same calculation as s = 1,
X and Y are INDEPENDENT.
s = 2, center present but P(r != 1) = 0 or P(c != 1) = 0.
Same as above: one coordinate is deterministic, so X and Y
share no randomness, and are INDEPENDENT.
s = 2, center present and BOTH D_r and D_c have positive probability.
Here is the ONLY case where X and Y are correlated. Write
D_r = {r != 1}, D_c = {c != 1}; both are nonempty, and in the
table D_r and D_c are disjoint events (they occupy different
cells). The center obeys the two matrices being exchanged by
T_{a,b}. Sub-case 5.5 handles this.
Declaration for all INDEPENDENT cases. When X, Y are independent,
E_a E_b = E_b E_a = the projection onto constants (in the cell).
Consequently h_a h_b = projection onto J, and for any f:
2 <h_a f, h_b f> = 2 ||proj_J f||^2 >= 2 ||g_{a,b} f||^2,
because ran(g_{a,b}) fits in J. This is STRONGER than the bound
we need. So Proposition 5.1 trivially holds in every case EXCEPT the
last one.
--------------------------------------------------------------------------
5.5 The rank-one correlated case (s = 2, center present)
--------------------------------------------------------------------------
We now attack the ONLY case where X and Y are genuinely dependent. Set
p_r = P(r != 1) = P(D_r),
p_c = P(c != 1) = P(D_c),
both in (0, 1) by hypothesis. Note D_r and D_c are DISJOINT events:
in the s = 2 table, cells with r != 1 and cells with c != 1 never
overlap. So p_r + p_c = 1 - P(center) < 1.
Define
u = ( 1_{D_c} - p_c ) / sqrt(p_c (1 - p_c)) [ in A ]
v = ( 1_{D_r} - p_r ) / sqrt(p_r (1 - p_r)) [ in B ]
Since D_r and D_c are disjoint and both have probability in (0,1):
<u, v> = -rho,
rho = sqrt( p_c p_r / ((1 - p_c) (1 - p_r)) ) in (0, 1).
(Proof: <1_{D_c}, 1_{D_r}> = 0, <1_{D_c}, 1> = p_c, etc., then
normalize.)
Conditional expectation identities. Given X = (c, W), the event D_c
is determined by c. When c != 1 (so D_c holds), the table forces
r = 1 (so D_r fails). When c = 1, r is allowed to be 0, 1, or 2.
A symmetric statement holds for E_b given Y = (r, U). Working these
out gives
E_a v = -rho u, E_b u = -rho v,
E_a u = u, E_b v = v.
Orthogonal decomposition. Since u in A centered, v in B centered,
their span is a 2-dim piece of A + B. Set
A' = A intersect span(1, u)^perp (A centered, perp u)
B' = B intersect span(1, v)^perp (B centered, perp v)
J = (A + B)^perp
Then (all summands orthogonal, and all invariant under E_a, E_b):
function space = span(1) (+) A' (+) B' (+) span(u, v) (+) J.
Action of E_a, E_b piecewise:
piece | E_a(f) | E_b(f)
-----------+-----------------+-----------------
span(1) | f | f
A' | f | 0
B' | 0 | f
span(u,v) | (x - rho y) u | (y - rho x) v
J | 0 | 0
(Here f = x u + y v on the plane piece.) Derived from E_a u = u,
E_a v = -rho u, E_b u = -rho v, E_b v = v, and independence on A', B', J.
Consequently the residual h_a = I - E_a puts each piece where:
piece | h_a f | h_b f
-----------+----------------------------+---------------------------
span(1) | 0 | 0
A' | 0 | f
B' | f | 0
span(u,v) | y (v + rho u) | x (u + rho v)
J | f | f
And cross terms between different pieces vanish in <h_a f, h_b f>
either because one factor is zero, or because the pieces are
orthogonal. So
<h_a f, h_b f> = xy rho (1 - rho^2) + ||proj_J f||^2.
[A short computation: <y(v + rho u), x(u + rho v)> = xy rho(1 - rho^2),
using <u, v> = -rho and ||u|| = ||v|| = 1.]
Two immediate consequences.
(a) ran(g_{a,b}) is inside J, so ||proj_J f||^2 >= ||g_{a,b} f||^2.
(b) The plane contribution can be negative. Bound it from below.
The second-line bound. Note:
(i) ||v + rho u||^2 = 1 + rho^2 + 2 rho <v, u> = 1 - rho^2.
(ii) ||u + rho v||^2 = 1 - rho^2.
(iii) <f_uv, v + rho u> = y (1 - rho^2), and
proj_{span(v + rho u)} f = y (v + rho u) = h_a f_uv.
The projection of f onto the line through v + rho u has squared length
<f, v + rho u>^2 / ||v + rho u||^2 = y^2 (1 - rho^2).
And the projection of f onto the line through u + rho v has squared
length x^2 (1 - rho^2). Add:
- (y^2 + x^2)(1 - rho^2) = - ||h_a f_uv||^2 - ||h_b f_uv||^2.
Now use the elementary inequality 2 xy rho >= -(x^2 + y^2) rho >=
-(x^2 + y^2) (both valid because 0 < rho < 1 and 2|xy| <= x^2 + y^2):
2 <h_a f_uv, h_b f_uv> = 2 xy rho (1 - rho^2)
>= -(x^2 + y^2)(1 - rho^2)
= - ||h_a f_uv||^2 - ||h_b f_uv||^2.
That is the plane inequality.
--------------------------------------------------------------------------
5.6 The error lines belong to the slice projections
--------------------------------------------------------------------------
Now the punchline. We need to bound ||h_a f_uv||^2 = y^2 (1 - rho^2) by
||R_{a,b} f||^2, where R_{a,b} is the projection defined in the
introduction. Recall:
z_{kl}^F (G) = 1_{ x_k = x_l } - P( x_k = x_l | F ), on a-fiber F,
R_{a,b} = orthogonal projection onto span(z_{kl}^F), summed over
all a-fibers F; zero if z_{kl}^F = 0.
Here x_k, x_l in {0,1} are the "assignment variables" of k and l to
the two endpoints of a. Specifically, on an a-fiber F,
x_k = 1 iff edge i-k is present (i is the "first endpoint" of a),
x_l = 1 iff edge i-l is present.
Note that on a-fibers with c != 1 (i.e., c = 0 or c = 2), one of k, l
is NOT a singleton into a. Then x_k, x_l are determined and z_{kl}^F = 0.
CLAIM: v - E_a v is proportional to z_{kl}^F on each a-fiber F.
Reason. Both v and E_a v are in the b-fiber algebra B, and v depends on
G only through r = row sum of M at i. So v - E_a v depends on G only
through r - E[r | X] = r - E[r | c, W].
On an a-fiber with c != 1: the s = 2 table forces r = 1, so r is
deterministic given X, and v - E_a v = 0 = z_{kl}^F (consistent).
On an a-fiber with c = 1: both k and l are singleton into a (each has
exactly 1 neighbor in a). Then r = x_k + x_l, so
So r = x_k + x_l. For x_k, x_l in {0,1}:
r = 1 iff x_k != x_l,
r = 0 iff x_k = x_l = 0,
r = 2 iff x_k = x_l = 1.
Hence D_r = {r != 1} equals {x_k = x_l} on this fiber.
Let q be the fiber-level probability that x_k = x_l. The centered
function z_{kl}^F = 1_{x_k = x_l} - q. Then
v = ( 1_{x_k = x_l} - p_r ) / sqrt(p_r(1-p_r)),
E[v | X] = ( q - p_r ) / sqrt(p_r(1-p_r)),
v - E[v | X] = ( 1_{x_k = x_l} - q ) / sqrt(p_r(1-p_r))
= z_{kl}^F / sqrt(p_r(1-p_r)).
So v - E_a v = z_{kl}^F / sqrt(p_r(1-p_r)) on every a-fiber, up to a
positive scalar depending only on the fiber.
Therefore v - E_a v ∈ ran(R_{a,b}). By symmetry, u - E_b u ∈ ran(R_{b,a}).
Consequence via orthogonal projection. In any subspace,
span(w) ⊂ ran(P) implies ||P f|| >= ||proj_{span(w)} f||. Apply to
w = v - E_a v = v + rho u (since E_a v = -rho u):
||R_{a,b} f||^2 >= || proj_{span(v + rho u)} f ||^2
= y^2 (1 - rho^2)
= ||h_a f_uv||^2.
Similarly ||R_{b,a} f||^2 >= ||h_b f_uv||^2 = x^2 (1 - rho^2).
Combine with the plane inequality:
2 <h_a f_uv, h_b f_uv>
>= -(x^2 + y^2)(1 - rho^2)
= -||h_a f_uv||^2 - ||h_b f_uv||^2
>= -||R_{a,b} f||^2 - ||R_{b,a} f||^2.
And add the J piece 2||proj_J f||^2 >= 2||g_{a,b} f||^2. So
2 <h_a f, h_b f> >= 2 ||g_{a,b} f||^2 - ||R_{a,b} f||^2
- ||R_{b,a} f||^2.
This is exactly Proposition 5.1.
--------------------------------------------------------------------------
5.7 Proposition 5.1 (restated and proved on the cell) and lifting
--------------------------------------------------------------------------
PROPOSITION 5.1 (Disjoint-pair interaction).
For every pair of disjoint vertex pairs a, b, and every real function f
on Omega_d:
2 <h_a f, h_b f> >= 2 ||g_{a,b} f||^2
- ||R_{a,b} f||^2
- ||R_{b,a} f||^2.
Proof. Fix a cell. If the cell is a singleton (probability 1 on one
graph) the cell contribution is trivially satisfied: h_a h_b f = 0
there and both sides are zero. Otherwise:
* Cases s ∈ {0, 1, 3, 4}: X, Y independent, so
2 <h_a f, h_b f> = 2 ||proj_J f||^2 >= 2 ||g_{a,b} f||^2 (stronger
than needed since the two error terms are >= 0).
* Cases s = 2 with center absent or one coordinate deterministic:
same independence argument, same conclusion.
* Case s = 2 with center present and both probabilities positive:
preceding calculation, giving exactly the stated inequality.
Sum over cells (all involved operators preserve cells), done. End.
All that remains to prove (Proposition 5.1 to be summed in Section 7)
is controlling the two error terms via a slice inequality, which is
the content of Section 6.
--------------------------------------------------------------------------
SECTION 6. THE SLICE INEQUALITY
--------------------------------------------------------------------------
This section proves the technical core that controls the two error terms
in Proposition 5.1. It has nothing to do with graphs: it is a statement
about the uniform measure on the q-subsets of an N-element set.
--------------------------------------------------------------------------
6.1 Statement
--------------------------------------------------------------------------
Fix integers N >= 0 and 0 <= q <= N. Consider the SLICE
X_{N,q} = { x in {0,1}^N : sum_{i=1}^N x_i = q }
with its uniform measure. Let tau_{ij} interchange coordinates i and j,
and set
G = (1/2) * sum_{i < j} ( I - tau_{ij} ).
G is positive semidefinite (sum of projections).
For each pair i < j, let Q_{ij} be the ORTHOGONAL PROJECTION onto the
centered function
z_{ij}(x) = 1_{ x_i = x_j } - P( x_i = x_j ),
using the convention Q_{ij} = 0 if z_{ij} = 0. On X_{N,q},
P( x_i = x_j ) = p = ( q(q-1) + r(r-1) ) / ( N(N-1) ), r := N - q.
LEMMA 6.1 (slice inequality).
S := sum_{i<j} Q_{ij} <= G.
Intuition. Both S and G are built out of the pair-comparisons "are
coordinates i and j the same?". G is the natural "transposition
energy" of the symmetric group acting on the slice: it measures how
far f is from being permutation-invariant. S is a coarser object: it
projects onto the specific quadratic functions (equal-or-not indicators)
centered. The lemma says the coarser object is dominated by the finer.
The proof is a computation. It uses the SLICE DECOMPOSITION of
functions on X_{N,q}, sometimes called the Johnson scheme:
any f on X_{N,q} = ( constant in degree 0 )
+ ( linear in x in degree 1 )
+ ( quadratic in x in degree 2 )
+ ... ( higher degrees )
See Filmus (2016, Lemmas 18 and 24) for a gentle treatment. The key
observation is that the centered indicators z_{ij} are QUADRATIC in x:
we have z_{ij}(x) = 1 - p - x_i - x_j + 2 x_i x_j, which is quadratic
with linear and constant terms. So S lies entirely within degrees 1
and 2 (not degree 0 since z_{ij} is centered, and not degree >=3 since
S only uses quadratics). That is why this lemma can be proved by
linear algebra.
--------------------------------------------------------------------------
6.2 Coefficient-space decomposition
--------------------------------------------------------------------------
Index pairs i < j by M = C(N,2) coordinates. Consider the embedding
B: R^M -> L^2( X_{N,q} ), Bc := sum_{i<j} c_{ij} * z_{ij} / s,
s := sqrt( p(1-p) ).
Then S = B B^* by definition (each Q_{ij} is projection onto z_{ij}/||z_{ij}||,
and ||z_{ij}|| = s). The Gram matrix is K = B^* B, and we study
its eigenvalues.
The coefficient space R^M decomposes ORTHOGONALLY as
R^M = C_0 (+) C_1 (+) C_2,
where
C_0 = { c_{ij} constants }
C_1 = { c_{ij} = u_i + u_j, sum_i u_i = 0 } (vertex potentials)
C_2 = { sum_{j != i} c_{ij} = 0 for every i } (row-zero)
Dimensions: |C_0| = 1 (dim for constants), |C_1| = N - 1, |C_2| = M - N.
Why orthogonal? The map u -> (u_i + u_j) is injective for N >= 3
(its kernel vanishes on every triangle thus on every vertex). Its image
is C_0 + C_1. The orthogonal complement is C_2, because the row-sum
conditions are the adjoints of the map u -> (u_i + u_j) plus the total
sum condition.
Two basic identities. On X_{N,q}:
sum_{i<j} 1_{ x_i = x_j } = C(q,2) + C(r,2) (constant on X_{N,q}).
So B kills C_0. Also, for any c in C_1 with c_{ij} = u_i + u_j:
sum_{i<j} (u_i + u_j) z_{ij} = ( 2q - N ) sum_i u_i x_i (a)
(direct expansion using sum_i x_i = q). Similarly, for any c in C_2,
the constant and linear terms of z_{ij} vanish when we sum (relevant
later when computing the action of G on B(C_2)).
--------------------------------------------------------------------------
6.3 Eigenvalues of K
--------------------------------------------------------------------------
By permutation invariance of the slice, K is a linear combination of
three "rank" operators (identity, meet-one, disjoint). So K acts by a
scalar on each C_i:
K|C_0 = 0 (B kills C_0),
K|C_1 = mu_1, K|C_2 = mu_2.
Compute mu_1. Take c in C_1, so c_{ij} = u_i + u_j with sum u_i = 0.
Using (a) and the two identities
Var( sum_i u_i x_i ) = (qr / (N(N-1))) sum_i u_i^2,
sum_{i<j} (u_i + u_j)^2 = (N - 2) sum_i u_i^2,
plug into ||Bc||^2 = mu_1 ||c||^2 and solve:
mu_1 = ( 2q - N )^2 / ( 2 (N - 2) p ) <= N / 2.
The inequality uses q, r >= 1 and q + r = N:
N(N-2) p - (2q - N)^2 = ( 2N / (N-1) )( qr - (N-1) ) >= 0.
Compute mu_2. K has diagonal all ones, so trace K = M = C(N,2). Since
K is positive semidefinite with K|C_1 contributing mu_1 and dim C_1 =
N - 1, dim C_2 = M - N:
(M - N) mu_2 <= M, hence 0 <= mu_2 <= (N - 1) / (N - 3) <= N - 1.
(For N <= 3, C_2 is empty, no bound needed.)
So S = B B^* acts as
on B(C_1): S acts as mu_1 <= N/2,
on B(C_2): S acts as mu_2 <= N - 1,
on B(C_0): S acts as 0 (empty).
--------------------------------------------------------------------------
6.4 Action of G on the images
--------------------------------------------------------------------------
Now compute what G does on the images U_1 = B(C_1), U_2 = B(C_2).
Recall G = (1/2) sum_{i<j} (I - tau_{ij}). Direct summation:
G x_i = ( N x_i - q ) / 2, (linear)
G (x_i x_j) = (N-1) x_i x_j
- (q-1)/2 ( x_i + x_j ). (quadratic)
Identity 1: on U_1. Since z_{ij} is a quadratic plus linear plus
constant and we are in the case where the constant sum is fixed, we can
use B applied to (a). Combined with the linear identity above:
G (linear part) = (N/2) * (linear part),
since the constant -q/2 is killed by sum_i u_i = 0. So G acts on U_1 as
N/2.
Identity 2: on U_2. For c in C_2, the linear term of sum_{i<j} c_{ij} z_{ij}
vanishes (row sums are zero). Only the quadratic part survives. Using
the quadratic identity above:
G (quadratic part) = (N-1) * (quadratic part),
so G acts on U_2 as N - 1.
Also, the operator G is self-adjoint and preserves U_1 + U_2
(given the above). So it also preserves the orthogonal complement.
--------------------------------------------------------------------------
6.5 Putting it together
--------------------------------------------------------------------------
On U_1: mu_1 <= N/2 (the action of G), so S <= G there.
On U_2: mu_2 <= N - 1 (the action of G), so S <= G there.
On (U_1 + U_2)^perp: B is zero (since C_0 + C_1 + C_2 is everything),
so S = 0 there, while G >= 0. Hence S <= G there too.
Therefore S <= G globally. Lemma 6.1 proved.
--------------------------------------------------------------------------
6.6 Lifting to the graph space
--------------------------------------------------------------------------
COROLLARY 6.2 (summed equality-indicator energy). For every vertex
pair a and every function f on Omega_d,
sum_{b : b intersect a = empty} ||R_{a,b} f||^2
<=
sum_{b : b intersect a = empty} ||g_{a,b} f||^2.
Proof. Work in ONE a-fiber F. Its assignments form a uniform q-subset
slice of the N singleton vertices of F. Label these N vertices; the
b's with b ∩ a = ∅ correspond to pairs {k, l} of these N labels. On F:
g_{a,b} = (I - tau_{kl}) / 2 (the pair-trade involution)
R_{a,b} = Q_{kl} (projection onto z_{kl}^F centered)
Check the first identity: two graphs in the a-fiber differing by a
cross-toggle T_{a,b} differ in exactly which of the two endpoints of
a is adjacent to k (or to l). So T_{a,b} acts as the transposition of
the k, l coordinates on the q-subset slice. That is exactly tau_{kl}.
Apply Lemma 6.1 on this fiber:
sum_{k<l} ||Q_{kl} f||^2 <= sum_{k<l} <f, (I - tau_{kl})/2 f>.
Lift to the whole a-fiber: the "sum over k < l" is exactly the "sum over
b disjoint from a", and each <f, (I - tau_{kl})/2 f> is exactly
||g_{a,b} f||^2 in the CROSS-switch sense. Summing over a-fibers (which
are preserved by all these operators) gives the corollary.
--------------------------------------------------------------------------
SECTION 7. ASSEMBLY: H^2 >= H AND THE KERNEL IS CONSTANTS
--------------------------------------------------------------------------
We assemble the local estimates into the global engine inequality, and
verify that H's kernel is exactly the constants (which upgrades "gap on
centered functions" into a non-degenerate gap on the switch chain).
--------------------------------------------------------------------------
7.1 The regrouping identity
--------------------------------------------------------------------------
Recall H = sum_a h_a. Compute H^2 by expanding:
H^2 = sum_{a, b ordered} h_a h_b
= sum_a h_a^2 + sum_{a != b} h_a h_b
= H + sum_{a != b} h_a h_b,
since h_a^2 = h_a.
Group the off-diagonal sum by unordered pairs {a, b} of distinct vertex
pairs. Each unordered pair contributes 2 h_a h_b (one in each order).
Split into pairs sharing a vertex, and disjoint pairs:
H^2 = H + 2 sum_{{a,b} share vertex} h_a h_b + D,
D = sum_{a <_lex b, a ∩ b = ∅} 2 h_a h_b = sum_{a, b disjoint} h_a h_b.
Now regroup the shared-vertex terms. Pairs {a, b} that share a vertex
satisfy a ∪ b = T for a unique triple T; conversely, for each triple T
there are 3 such unordered pairs (the 3 ways to choose 2 pairs from
the triple's 3 vertex pairs). And
H_T^2 = (sum_{a in C(T,2)} h_a)^2 = H_T + 2 sum_{{a,b} in T} h_a h_b.
So sum_T H_T^2 = sum_T H_T + 2 sum_{{a,b} share vertex} h_a h_b.
Also sum_T H_T = (n-2) H because each vertex pair belongs to exactly
(n-2) triples. Substitute:
H^2 = sum_T H_T^2 - (n-3) H + D.
(Check: RHS = [sum_T H_T + 2 sum_{shared}] - (n-3) H + D = (n-2) H - (n-3) H + 2 sum_{shared} + D = H + 2 sum_{shared} + D = LHS. Good.)
This is the "exact identity" used in Section 8 to prove H^2 >= H.
--------------------------------------------------------------------------
7.2 D is positive semidefinite
--------------------------------------------------------------------------
PROPOSITION 7.1. The operator D = sum_{a, b disjoint} h_a h_b is
self-adjoint and positive semidefinite.
Proof. Self-adjointness: D is a sum of h_a h_b; with a, b disjoint,
the term for (b, a) is also in the sum, so D = D^*.
Positive semidefiniteness: take any real f. Compute:
<f, Df> = sum_{a, b disjoint} <h_a f, h_b f>
Pair terms for unordered {a, b} (disjoint). The unordered pair {a, b}
contributes 2<h_a f, h_b f>. Using Proposition 5.1:
2 <h_a f, h_b f> >= 2 ||g_{a,b} f||^2
- ||R_{a,b} f||^2
- ||R_{b,a} f||^2.
Sum over unordered pairs:
<f, Df> >= sum_{{a,b} disjoint} 2 ||g_{a,b} f||^2
- sum_{{a,b} disjoint} ( ||R_{a,b} f||^2 + ||R_{b,a} f||^2 ).
Rewrite the right side as sum over a of [something]:
sum_{{a,b} disjoint} 2||g_{a,b} f||^2
= sum_a sum_{b: b ∩ a = ∅} ||g_{a,b} f||^2 (both orders of each pair)
sum_{{a,b} disjoint} (||R_{a,b} f||^2 + ||R_{b,a} f||^2)
= sum_a sum_{b: b ∩ a = ∅} ||R_{a,b} f||^2 (both orders of each pair)
So
<f, Df> >= sum_a [ sum_{b disjoint} ||g_{a,b} f||^2
- sum_{b disjoint} ||R_{a,b} f||^2 ].
By Corollary 6.2, the bracket is >= 0 for every a. Hence <f, Df> >= 0.
End.
--------------------------------------------------------------------------
7.3 The engine inequality
--------------------------------------------------------------------------
PROPOSITION 7.2 (engine inequality). H^2 >= H.
Proof. From the regrouping identity:
H^2 = sum_T H_T^2 - (n-3) H + D
>= sum_T H_T - (n-3) H + 0 [Proposition 4.1, Prop 7.1]
= (n-2) H - (n-3) H
= H. End.
So every eigenvalue of H on centered functions is either 0 or at
least 1. (If lambda >= 0 satisfies lambda^2 >= lambda, then lambda = 0
or lambda >= 1.)
--------------------------------------------------------------------------
7.4 The kernel of H is the constants
--------------------------------------------------------------------------
H f = 0 iff <f, Hf> = 0 (H is PSD), iff sum_a ||h_a f||^2 = 0, iff
h_a f = 0 for every vertex pair a. The last condition says f is
constant on every a-fiber for every a.
PROPOSITION 7.3. If f is constant on every a-fiber for every vertex
pair a, then f is constant on Omega_d.
Proof. It suffices to show that f is invariant under every valid
switch, since then CONNECTIVITY (Lemma 7.4 below) makes f constant.
Take a valid switch {uv, xy} -> {ux, vy}. The four vertices u, v, x, y
are distinct. Consider the vertex pair a = {u, y}. In this fiber:
* v has exactly one neighbor in {u, y}, namely u (v is adjacent to u
via uv, and NOT to y because u-y is either absent or fixed by
other data; either way v's assignment inside this fiber is "v goes
with u");
* x has exactly one neighbor in {u, y}, namely y (x is adjacent to y
via xy, not to u);
* all other vertices have their assignment determined by fixed data.
So v and x are both singletons in this fiber, and the fiber freedom is
precisely to exchange their assignments: put v with y and x with u.
The resulting graph is: uv is replaced by vy, and xy is replaced by ux.
That is EXACTLY our switch target graph.
So the switch is a pair-trade on a = {u, y}. Since f is constant on
this a-fiber, f takes the same value on the switch source and target.
The same argument applies to every switch. Hence f is switch-invariant.
By connectivity, f is constant. End.
LEMMA 7.4 (connectivity). Any two graphs in Omega_d are connected by a
sequence of switches.
Proof (Havel). Fix a target order of neighbors and prescribe edges one
vertex at a time, from lowest labelled vertex upward. Suppose the
vertices in {1, ..., v-1} have the correct neighbor sets in the current
graph G, and let R = {v, ..., n}. Prescribe the neighbors of v: the
d_v^R vertices of R \ {v} of highest residual degree, ties by label.
If the current neighbors of v differ, there is a missing desired
neighbor j and an undesired actual neighbor i, with
d_j^R >= d_i^R. Removing a possible edge ij subtracts the same amount
from both residual degrees, so
|N_R(j) \ {i}| >= |N_R(i) \ {j}|.
Since v ∈ (N_R(i) \ {j}) \ (N_R(j) \ {i}) (v is not adjacent to i or
j inside R \ {v}, but v IS adjacent to i, its undesired neighbor),
the set N_R(j) \ {i} must contain vertices not in N_R(i) \ {j}.
Pick k in (N_R(j) \ {i}) \ (N_R(i) \ {j}). Then:
vi, jk are edges; vj, ik are NOT edges; k is distinct from v, i, j.
So {vi, jk} -> {vj, ik} is a valid SWITCH. It fixes every other edge
of v and increases the number of v's correctly placed neighbors by 1.
Repeat until v has the prescribed neighbors. Then freeze v (its degree
and neighbors are now correct, and future switches involve only R \ {v}).
Proceed to the next vertex. The procedure terminates: each frozen
vertex is prescribed independently of the starting graph.
Consequently every realization reaches the SAME canonical graph, so
any two are connected. End.
--------------------------------------------------------------------------
SECTION 8. FROM H TO THE SWITCH CHAIN: MIXING TIME
--------------------------------------------------------------------------
We now convert the pair-resampling gap (H >= identity on centered
functions) into a mixing-time bound for the switch chain P_d.
--------------------------------------------------------------------------
8.1 Comparison with single switches
--------------------------------------------------------------------------
Let L be the UNNORMALIZED LAPLACIAN of the switch chain:
(Lf)(G) = sum_{G' switch neighbor of G} ( f(G) - f(G') ).
Each distinct neighbor appears once in the sum so <f, Lf> = sum over
unordered {G, G'} pi(G) [f(G) - f(G')]^2 = expected squared gain, which
is nonnegative.
For a vertex pair a, define J_a on each a-fiber as
J_a = sum_{1 <= k < l <= N} ( I - tau_{k,l} )
where tau_{k,l} exchanges the assignments of the k-th and l-th
singleton of the fiber, and N is the fiber's singleton count.
LEMMA 8.1 (comparison).
(i) h_a <= n^2 J_a (for every pair a);
(ii) sum_{a in C(V,2)} J_a = 2 L;
(iii) H <= 2 n^2 L.
Proof of (i). Work in one fiber, uniform on q-subsets of N singletons.
Let S_0 be a uniform q-subset and σ an independent uniform permutation
of {1,...,N}. Then σ S_0 is also uniform and independent of S_0, so
Var(f) = (1/2) E[ ( f(S_0) - f(σ S_0) )^2 ].
Fix, for each permutation σ, a decomposition into at most N
transpositions (for example from its cycle decomposition), padded
with identities to length N. Let S_j = τ_1 ... τ_j S_0 so S_N = σ S_0.
Telescoping:
f(S_0) - f(S_N) = sum_{j=0}^{N-1} [ f(S_j) - f(τ_{j+1} S_j) ].
Cauchy-Schwarz on the sum:
(sum_j (f(S_j) - f(τ_{j+1} S_j)))^2
<= N sum_j (f(S_j) - f(τ_{j+1} S_j))^2.
Conditional on σ, every S_j is uniform on q-subsets (S_0 uniform, each
τ_j preserves uniformity). So
E[ (f(S_j) - f(τ_{j+1} S_j))^2 | σ ]
= E_S[ (f(S) - f(τ_{j+1} S))^2 ].
Each j is a specific transposition type; the sum of such terms over all
C(N,2) types is at most N times the largest single-type contribution,
so
sum_j E_S[ ( f(S) - f(τ_{j+1} S) )^2 ] <= N sum_{k<l} E_S[ ( f(S) - f(τ_{k,l} S) )^2 ].
Substitute and use Var(f) = (1/2) E[f(S_0) - f(σ S_0)]^2:
Var(f) <= (1/2) * N * N sum_{k<l} E_S[ ( f(S) - f(τ_{k,l} S) )^2 ]
= N^2 sum_{k<l} (1/2) E_S[ ( f(S) - f(τ_{k,l} S) )^2 ]
= N^2 < f, J_a f >.
Since Var(f) = <f, h_a f> on this fiber (h_a is exactly fiber-variance),
and N <= n, we get <f, h_a f> <= n^2 <f, J_a f>. That is h_a <= n^2 J_a.
Proof of (ii). Each individual SWITCH {uv, xy} -> {ux, vy} is realized
by exactly two pair trades:
a = {u, y}: exchange v and x
a = {v, x}: exchange u and y
These are the ONLY realizations: a singleton transposition on a pair
a = {p, q} toggles the four edges between {p, q} and the two singleton
vertices that are exchanged. The four toggled vertices form a 4-cycle
with two natural bipartitions {p, q} and {the two exchanged singletons}.
Each partition choice determines its transposition uniquely. So both
realizations occur, and only those. Hence sum_a J_a generates the
same sum of squared differences as L, applied twice (once per unordered
switch). So sum_a J_a = 2 L.
Proof of (iii). Sum (i) over a and use (ii):
H = sum_a h_a <= sum_a n^2 J_a = n^2 * 2 L = 2 n^2 L. End.
--------------------------------------------------------------------------
8.2 The gap of P_d
--------------------------------------------------------------------------
By Corollary 7.3 and Proposition 7.2, on centered functions H >= I (up
to the 1-dim constants which H kills). So
Var_{pi_d}(f) = <f, Hf> <= 2 n^2 <f, Lf> (by Lemma 8.1(iii)).
If |Omega_d| > 1, then the spectral gap of L at pi_d is at least
1/(2 n^2).
For any distinct switch neighbors G, G', the transition probability is
P_d(G, G') = (1/2) * (1 / C(n, 4)) * (1/6) = 1 / (12 C(n,4)).
Symmetrically for the reverse transition, so pi_d is reversible, and
I - P_d = L / (12 C(n,4)).
Therefore the gap of P_d is at least
gamma_0 = 1 / (24 n^2 C(n,4)).
Also: the holding probability 1/2 guarantees nonnegative eigenvalues.
Formally, 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]; hence every eigenvalue of P_d on the
centered subspace lies in [0, 1 - gamma_0].
So for any centered function f and any t >= 0:
||P_d^t f|| <= (1 - gamma_0)^t ||f|| <= e^{-gamma_0 t} ||f||.
--------------------------------------------------------------------------
8.3 The mixing time bound
--------------------------------------------------------------------------
Let M = |Omega_d|. The TV distance from any fixed start G is:
||P_d^t(G, .) - pi_d||_TV <= (1/2) sqrt(M) * (1 - gamma_0)^t.
Proof. Let h^t(H) = P_d^t(G, H) / pi_d(H) - 1 be the density of
P_d^t(G, .) with respect to pi_d, minus 1. Then h^t = P_d^t h^0 where
h^0(H) = 1_{H = G} / pi_d(G) - 1 is the initial density.
Compute ||h^0||^2 = E_pi[ (h^0)^2 ]. Since pi_d(G) = 1/M:
h^0(G) = M - 1,
h^0(H) = -1 (for H != G),
||h^0||^2 = (1/M)(M-1)^2 + (1 - 1/M)(-1)^2 = (M-1)/M <= 1.
Wait, small correction: ||h^0||^2 <= 1/pi_d(G) = M. The exact bound:
(1/M)(M-1)^2 + (M-1)/M = (M-1)(M-1+1)/M = M - 1 <= M. Good.
So ||h^t||^2 <= (1 - gamma_0)^{2t} ||h^0||^2 <= M (1 - gamma_0)^{2t}.
And TV distance:
||P_d^t(G, .) - pi_d||_TV = (1/2) sum_H pi_d(H) |P_d^t(G, H)/pi_d(H) - 1|
= (1/2) E_pi |h^t|
<= (1/2) sqrt( E_pi |h^t|^2 ) (Cauchy-Schwarz)
= (1/2) ||h^t||
<= (1/2) sqrt(M) (1 - gamma_0)^t. Good.
Mixing time bound: pick
t = ceil( (24 n^2 C(n,4)) * ( log 2 + (1/2) log M ) ).
Then (1 - gamma_0)^t e^{gamma_0 t} <= ... hmm, we need (1-gamma)^t <= e^{-gamma t} (valid since log(1-x) <= -x), and using log 2 + (1/2) log M as our target:
(1 - gamma_0)^t <= e^{-gamma_0 t} = e^{-gamma_0 ceil(gamma_0^{-1} * target)}
<= e^{-target} = e^{-log 2 - (1/2) log M} = 1/(2 sqrt M).
So (1/2) sqrt(M) * (1 - gamma_0)^t <= 1/4. Good, t_mix <= t.
Now simplify t. Use M <= 2^{C(n,2)}, so (1/2) log M <= (1/2) C(n,2) log 2.
Also for n >= 4: 1 + C(n,2)/2 = 1 + n(n-1)/4 <= n^2.
And 24 n^2 C(n,4) <= n^6. So
t <= ceil( n^6 * n^2 * log 2 * (1 + C(n,2)/2) / n^0 * ... )
Hmm let me redo. t = ceil(24 n^2 C(n,4) * (log 2 + (1/2) log M))
<= ceil(24 n^2 C(n,4) * log 2 * (1 + C(n,2)/2))
<= ceil(n^6 * log 2 * n^2)
= ceil(n^8 log 2)
<= ceil(n^8) = n^8 <= 2 n^8.
So t_mix(d) <= 2 n^8. Theorem 1 proven.
Remarks. The chain has trivial case |Omega_d| = 1: t_mix = 0. The
bound 2 n^8 is polynomial in n for every graphical d, which is the
content of the Kannan-Tetali-Vempala conjecture in the simple-undirected
model.
--------------------------------------------------------------------------
SECTION 9. EXACT UNIFORM SAMPLING
--------------------------------------------------------------------------
Sections 1-8 give a chain that becomes CLOSE to uniform after
O(n^8) steps. "Close" is not "exactly uniform". This section
converts the nearby-uniform law into an exact uniform sampler, using a
rare-branch correction. This is the standard "exact sampling from a
rapidly mixing chain" technique due to Gobel-Liu-Manurangsi-Pappik
(2024, Section 3.1). A similar tabulation appears in the recent
contingency-table sampler of OpenAI (2026); see the references.
--------------------------------------------------------------------------
9.1 The mixture idea
--------------------------------------------------------------------------
Suppose we have a probability law p that is VERY close to uniform on
Omega_d, in the sense that p_G is at most 1/M + delta^2 for every G,
where M = |Omega_d|. If 0 < delta < 1 and M * delta <= 1, then
(1 - delta) p_G <= (1 - delta) (1/M + delta^2)
<= 1/M + (1 - delta) delta^2 - delta/M
<= 1/M (using M delta <= 1).
So the mixture pi_d - (1-delta) p is a NONNEGATIVE measure on Omega_d;
divided by its total mass delta (which equals 1 - (1-delta) = delta
since both are probability laws), it is a probability law
r = ( pi_d - (1-delta) p ) / delta.
And (1-delta) p + delta r = pi_d. So the mixture of two samplers --
"ordinary branch" runs the fast chain, "rare branch" samples from r --
produces EXACT uniform samples.
If delta is exponentially small (say 2^{-2B} where B = C(n,2)), then
the rare branch almost never fires. On the rare branch we can afford to
do exponential work (enumerate everything), because the expected work is
delta * (exponential) = polynomial.
Filling in the parameters:
p_G = P_d^t (G_0, G) for a fixed starting graph G_0 in Omega_d.
We need p to satisfy the domination bound. From the mixing time bound:
for t = ceil( gamma_0^{-1} ( B + 2D + 2 ) ) with D := 4B + 10 and
delta := 2^{-D}:
||p - pi_d||_TV <= (1/2) sqrt(M) e^{-gamma_0 t}
<= (1/2) 2^{B/2} e^{-(B+2D+2)}
<= 2^{-2D} = delta^2.
Applying total variation to a singleton event gives p_G <= 1/M + delta^2
(after a bit of bookkeeping; the paper's exact derivation is in the
original). And M delta = M / 2^{4B+10} <= 2^B / 2^{4B+10} <= 1
(uses M <= 2^B). So the domination bound holds.
The parameters, in overview:
B = C(n,2) = number of vertex pairs,
M = |Omega_d| = number of realizations (unknown a priori,
computable by exact enumeration),
q = 12 C(n,4) = reciprocal of P_d off-diagonal transition,
D = 4B + 10 (accuracy bits),
delta = 2^{-D} (rare-branch probability),
t = ceil( gamma_0^{-1} (B + 2D + 2) ) (chain length to sample p).
The algorithm.
Draw D fresh unbiased bits. If not all zero, run t steps of the chain
from G_0 and output the resulting graph.
If ALL zero, do the EXACT calculation below on the rare branch and
output a sample from r.
Because the rare branch fires with probability exactly delta = 2^{-D},
the overall output law is (1-delta) p + delta r = pi_d.
--------------------------------------------------------------------------
9.2 The exact rare branch
--------------------------------------------------------------------------
On the rare branch we need to compute r_G = (1/M - (1-delta) p_G)/delta
and sample from it. We cannot avoid enumerating Omega_d here -- that is
the price of exactness, and it is what makes the branch expensive.
Enumeration.
List all 2^B bit-strings on the vertex pairs. For each, check if the
labeled degree sequence equals d. Keep the ones that do. This gives
M and Omega_d. Cost: 2^B times poly(n) bit operations.
Tabulation of p.
Construct the integer matrix A = q P_d. Every entry of A is a
nonnegative integer, and every row sum is exactly q. (Verify: q *
(1/(12 C(n,4))) = 1 for a switch neighbor, 0 otherwise; and the
diagonal entry is q - (number of neighbors), which is a nonnegative
integer.) Starting from the point mass a^(0) at G_0 (a^(0)_G = 1 iff
G = G_0), propagate
a^(s+1) = a^(s) A (0 <= s < t).
Then p_G = a^(t)_G / q^t. Numerator bit lengths are O(t log q) =
poly(n). Cost: 2B for the number of pairs, times tM^2 = O(2^{2B} t)
for the propagation, times poly(n) per arithmetic op. Total:
2^{2B} * poly(n) bit operations.
Integer weights.
Set
w_G = 2^D q^t - M (2^D - 1) a_G^(t) (for G in Omega_d).
By the domination bound, w_G >= 0. Their sum:
sum_G w_G = 2^D q^t M - M (2^D - 1) sum a^(t) = 2^D q^t M - M(2^D-1) q^t = M q^t.
(Uses sum_G a_G^(t) = q^t, which is inherited from the row-sum-q
property.)
Draw a uniform integer in {0, 1, ..., M q^t - 1}. Find which interval
[sum_{preceding G's} w_H, sum_{<= G's} w_H] it falls in. Output that G.
The resulting output law is w_G / (M q^t) = r_G as claimed.
Total expected cost of the rare branch: (probability of rare branch) *
(cost of enumeration) = delta * 2^{2B} * poly(n) = 2^{-D} * 2^{2B} *
poly(n) = 2^{-2B-10} * poly(n) <= poly(n).
--------------------------------------------------------------------------
9.3 Correctness and cost
--------------------------------------------------------------------------
The two branches (ordinary and rare) are independent: the ordinary
branch uses fresh random bits after the initial D-bit choice; the rare
branch uses fresh random bits for its uniform integer draw. So the
output law is exactly the mixture (1-delta) p + delta r = pi_d.
Every element of the algorithm is finite: the enumeration is over a
finite set (2^B bit-strings), the integer arithmetic operates on bounded
values (bit lengths O(D + t log q + log M) = poly(n)), and the uniform
draws terminate almost surely. Rejection sampling for uniformly random
integers in {0, ..., K-1} takes fewer than 2 attempts in expectation.
So the algorithm:
* uses only unbiased random bits;
* terminates almost surely;
* outputs a graph chosen EXACTLY uniformly from Omega_d;
* has expected bit running time bounded by poly(n).
This proves Corollary 2.
The correction branch may take exponential time. The corollary
promises only EXPECTED polynomial time. A polynomial bound on every
execution is impossible: computing |Omega_d| exactly (which the branch
does) is #P-hard in general.
--------------------------------------------------------------------------
SECTION 10. FINAL REMARKS
--------------------------------------------------------------------------
What we have proved. For every graphical labeled degree vector d on
n >= 4 vertices, the simple-undirected switch chain mixes in
total-variation distance 1/4 from any start in at most 2 n^8 steps, and
there is an exactly uniform sampler for the same degree vector running
in expected polynomial bit time. This resolves the simple-undirected
form of the Kannan-Tetali-Vempala conjecture.
What is missing. The bipartite and directed forms are analogous
problems with their own techniques; Fu-Qin-Wang (2026) proved the
bipartite form. The general-host versions (prescribed degrees in
arbitrary hosts, weighted edges, etc.) are open in general. Bounds
for sampling FROM a specific distribution other than uniform remain
an active problem.
The big idea you should take away. Three moves, all simple in
hindsight:
1. Replace "one switch at a time" by "resample a whole fiber at once".
Fibers are uniform q-subsets, so the analysis reduces to classical
slice combinatorics.
2. Show one operator inequality, H^2 >= H, by splitting into "three
pairs on a triple" (a three-row variance bound) and "disjoint
pairs" (a rank-one correlation corrected by a slice inequality).
3. Compare back to the switch chain using the same fiber structure.
The gap is 1/(24 n^2 C(n,4)).
4. Upgrade to exact uniform via a rare-branch correction.
Four moves, actually. The whole paper is these four moves, developed
carefully.
If you followed this far, you know what a spectral gap is, why mixing
time depends on it, how to compare one Markov chain to another, and how
to correct a small bias to make sampling exactly uniform. Those are
four of the most useful ideas in modern probability, and they are all
here.