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 \[ \langle f,Jf\rangle =\frac12\sum_\tau\mathbb E(f-T_\tau f)^2. \tag{4}\] 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 (4) 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 (3). ◻

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 [14]. 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: \[ Y_{s-1}\le Y_s\le Y_{s-1}+1. \tag{6}\] 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 (5), it suffices to bound the largest eigenvalue \(\lambda\) of \(A^*A\) by \(2\). A corresponding nonzero centered eigenvector satisfies \[ \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. \tag{7}\] Every value \(0,\ldots,m\) has positive marginal probability. Therefore \[M=\max_{i,\,0\le t<m}|b_i(t+1)-b_i(t)|\] is positive: otherwise each component would be constant, and hence zero by centering.

Conditioning on \(x_i=t\) leaves the other two coordinates with total \(s=m-t\). For adjacent values \(t,t+1\), couple those coordinates using (6). Exactly one of them decreases by one, so the change in their conditional sum of functions has absolute value at most \(M\). Subtracting (7) at the two values thus gives \[|(\lambda-1)(b_i(t+1)-b_i(t))|\le M.\] Choose \(i,t\) attaining \(M\). It follows that \(|\lambda-1|\le1\), and in particular \(\lambda\le2\). ◻

Proof. Columns of sum \(0\) or \(3\) are deterministic; remove them and adjust the row sums. Let \(U\) index the columns of sum \(1\), assigned to the row containing their unique one. Let \(W\) index the columns of sum \(2\), assigned to the row containing their unique zero. Write \(U_i,W_i\) for the resulting blocks. The nondeterministic information in row \(i\) is exactly \((U_i,W_i)\).

Put \(k_i=|W_i|\). The adjusted row-sum constraints have the form \[|U_i|=k_i+\delta_i\] for fixed integers \(\delta_i\), since that row sum equals \(|U_i|+|W|-k_i\). Conditional on the vector \(k\), the assignments on \(U\) and \(W\) are independent uniform ordered partitions with prescribed block sizes. Lemma 3 therefore applies.

Counting these partitions shows that the law of \(k\) has weights proportional to \[\prod_{i=1}^3\frac1{k_i!(k_i+\delta_i)!}, \qquad k_i\ge0,\quad k_i+\delta_i\ge0,\quad \sum_i k_i=|W|.\] These conditions are sufficient for feasibility: the two sets of nonnegative block sizes sum to \(|W|\) and \(|U|\), respectively. Set \[l_i=\max(0,-\delta_i),\qquad x_i=k_i-l_i,\qquad \alpha_i=|\delta_i|,\qquad m=|W|-\sum_i l_i.\] Nonemptiness implies \(m\ge0\). The support becomes all nonnegative triples of total \(m\), and the weights become \(\prod_i[x_i!(x_i+\alpha_i)!]^{-1}\). Thus Lemma 4 applies to functions of the individual counts.

Conditional on \(k\), the marginal blocks \(U_i\) and \(W_i\) are independent uniform subsets of their respective sizes. In particular \(\mathbb E[f_i(S_i)\mid k]\) depends only on \(k_i\), or equivalently on \(x_i\). Applying conditional variance, followed by Lemmas 3 and 4, gives \[\begin{align*} \operatorname{Var}\Bigl(\sum_i f_i(S_i)\Bigr) &=\mathbb E\operatorname{Var}\Bigl(\sum_i f_i(S_i)\,\Big|\,k\Bigr) +\operatorname{Var}\Bigl(\sum_i\mathbb E[f_i(S_i)\mid k]\Bigr)\\ &\le 2\sum_i\mathbb E\operatorname{Var}(f_i(S_i)\mid k) +2\sum_i\operatorname{Var}(\mathbb E[f_i(S_i)\mid k])\\ &=2\sum_i\operatorname{Var}(f_i(S_i)), \end{align*}\] as required. ◻

Proof. Partition \(\Omega_d\) by recording the graph on \(V\setminus T\) and, for each \(w\notin T\), its number of neighbors in \(T\). Every pair resampling indexed by a pair in \(T\) preserves these data. Work in one nonempty cell, with its conditional uniform measure. The degree sum in \(T\) determines the total number \(e\in\{0,1,2,3\}\) of edges inside \(T\).

Use a binary matrix with rows indexed by \(i\in T\) and columns indexed by \(w\notin T\), whose entry at \((i,w)\) is the indicator of the edge \(iw\). Its column sums are fixed. To encode the internal graph as well, let \(s_i\) denote the degree of \(i\) within \(T\), and augment the matrix as follows.

For \(e=1\), the extra column marks the endpoints of the sole edge; for \(e=2\), it marks the center of the path. Thus the internal graph is uniquely recovered from the extra column, or is deterministic when \(e=0,3\). Conversely, every binary matrix with the prescribed row and column sums recovers a valid graph in this cell. The row sums give the required degrees in \(T\), while the external column sums and the fixed graph on \(V\setminus T\) give all other degrees. This is a bijection onto the entire fixed-margin matrix space, so its conditional measure is uniform.

We next identify the conditional operators exactly. Fix \(i\in T\) and write \(\{j,k\}=T\setminus\{i\}\). Within this cell, \[ E_{\{j,k\}}f=\mathbb E[f\mid S_i], \tag{9}\] where \(S_i\) is augmented row \(i\). Indeed, the external entries of this row determine \(s_i\) from \(d_i\), and hence determine its extra entry whenever present. Fixing the row therefore means precisely fixing the external neighbors of \(i\). Together with the cell data, these neighbors determine all the \(\{j,k\}\)-fiber data:

• the graph away from \(\{j,k\}\) is the fixed graph on \(V\setminus T\), together with the specified external edges at \(i\);

• the indicator of \(jk\) is \(e-s_i\);

• the number of neighbors in \(\{j,k\}\) of each \(w\notin T\) is its recorded number of neighbors in \(T\) minus the indicator of \(iw\);

• the number of neighbors in \(\{j,k\}\) of \(i\) itself is \(s_i\).

Conversely, the pair-fiber data fix all external edges at \(i\), and therefore fix \(S_i\). The fiber is contained in the cell because the cell data are preserved by the pair resampling. Thus the two conditionings coincide on the full pair fiber, proving (9). In particular, when \(s_i=1\), the choice between \(ij\) and \(ik\) remains free whenever the other constraints permit it; conditioning on the augmented row does not freeze that internal choice.

Let \(P_i f=\mathbb E[f\mid S_i]\). For a function \(f\) centered in the cell, the functions \(P_i f\) are centered row functions. Put \(b=\sum_i\|P_i f\|^2\). Orthogonality of \(P_i\), Lemma 5, and Cauchy–Schwarz yield \[b=\left\langle f,\sum_i P_i f\right\rangle \le\|f\|\left\|\sum_i P_i f\right\| \le\|f\|\sqrt{2b}.\] It follows that \(b\le2\|f\|^2\), including when \(b=0\). By (9), \[\langle f,H_Tf\rangle =3\|f\|^2-\sum_i\|P_i f\|^2\ge\|f\|^2.\] Thus the self-adjoint operator \(H_T\) kills constants and has all its other eigenvalues at least \(1\) in this cell. Squaring its eigenvalues proves \(H_T^2\succeq H_T\) there; the conclusion is also immediate for a singleton cell. Finally, all the operators preserve the cells, so the cellwise inequalities give the claimed inequality on \(\Omega_d\). ◻

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.

Proof. Each \((I-\tau_{ij})/2\) is an orthogonal projection, so \(G\) is positive semidefinite. If all the \(z_{ij}\) vanish, the assertion follows immediately. This covers \(N\le2\) and \(q\in\{0,N\}\). In the remaining cases \(N\ge3\) and \(1\le q\le N-1\). Writing \(r=N-q\), we have \[ \begin{aligned} p&:=\mathbb P(x_i=x_j) =\frac{q(q-1)+r(r-1)}{N(N-1)},\\ 1-p&=\frac{2qr}{N(N-1)},\qquad \|z_{ij}\|^2=p(1-p)>0. \end{aligned} \tag{21}\] All norms of functions in this proof use the uniform measure on the slice.

Let \(M=\binom N2\) and give the pair coefficient space \(\mathbb R^M\) its usual Euclidean inner product. Define \[Bc=\sum_{i<j}c_{ij}\frac{z_{ij}}{\sqrt{p(1-p)}}.\] Then \(S=BB^*\). We analyze its Gram matrix \(K=B^*B\) using the orthogonal decomposition \[\begin{align*} \mathcal C_0&=\{c:\ c_{ij}\text{ is constant}\},\\ \mathcal C_1&=\left\{c:\ c_{ij}=u_i+u_j,\quad\sum_i u_i=0\right\},\\ \mathcal C_2&=\left\{c:\ \sum_{j\ne i}c_{ij}=0\text{ for every }i\right\}. \end{align*}\] Here and below \(c_{ji}=c_{ij}\). To verify the decomposition, the map \(u\mapsto(u_i+u_j)_{i<j}\) is injective for \(N\ge3\): its kernel vanishes on every triangle, and hence on every vertex. Its image is \(\mathcal C_0\oplus\mathcal C_1\), and its orthogonal complement is precisely \(\mathcal C_2\). Thus the dimensions are \(1\), \(N-1\), and \(M-N\), respectively. In particular \(\mathcal C_2=\{0\}\) when \(N=3\).

The number of equal coordinate pairs is fixed on the slice: \[\sum_{i<j}\mathbf 1_{\{x_i=x_j\}}=\binom q2+\binom r2.\] It follows that \(B\) kills \(\mathcal C_0\). Permutation invariance shows that the entries of \(K\) depend only on the intersection size of their indexing pairs. Moreover, for a fixed pair \(ij\), the sums of coefficients over other pairs meeting \(ij\), and over pairs disjoint from \(ij\), are \[\begin{array}{c|cc} &\text{intersection of size one}&\text{disjoint}\\ \hline c\in\mathcal C_1&(N-4)c_{ij}&-(N-3)c_{ij}\\ c\in\mathcal C_2&-2c_{ij}&c_{ij}. \end{array}\] Indeed, the first column is the sum of the two row sums minus \(2c_{ij}\); the row sums are \((N-2)u_i\) on \(\mathcal C_1\) and zero on \(\mathcal C_2\). The second column follows because both spaces have zero total coefficient sum. For \(N=3\) there are no disjoint pairs, and the displayed expression on \(\mathcal C_1\) is zero as required. Consequently \(K\) acts by a scalar \(\mu_1\) on \(\mathcal C_1\) and, when present, by a scalar \(\mu_2\) on \(\mathcal C_2\).

We first compute \(\mu_1\). The number of coordinates other than \(i\) equal to \(x_i\) is \[\sum_{j\ne i}\mathbf 1_{\{x_i=x_j\}} =(r-1)+(2q-N)x_i.\] For \(\sum_i u_i=0\) this gives \[ \sum_{i<j}(u_i+u_j)z_{ij} =(2q-N)\sum_i u_i x_i. \tag{22}\] The one- and two-coordinate probabilities of a uniform \(q\)-subset imply \[\operatorname{Var}\!\left(\sum_i u_i x_i\right) =\frac{qr}{N(N-1)}\sum_i u_i^2, \qquad \sum_{i<j}(u_i+u_j)^2=(N-2)\sum_i u_i^2.\] Using these identities and (21) in \(\|Bc\|^2=\mu_1\|c\|^2\) yields \[ \mu_1=\frac{(2q-N)^2}{2(N-2)p}\le\frac N2. \tag{23}\] For the inequality, the difference of the relevant numerators is \[N(N-2)p-(2q-N)^2 =\frac{2N}{N-1}\bigl(qr-(N-1)\bigr)\ge0,\] since \(q,r\ge1\) and \(q+r=N\).

The diagonal entries of \(K\) are all one, so \(\operatorname{tr}K=M\). Since \(K\) is positive semidefinite, for \(N\ge4\) we obtain \[ (M-N)\mu_2\le M, \qquad 0\le\mu_2\le\frac{N-1}{N-3}\le N-1. \tag{24}\] This argument is used only when \(\mathcal C_2\) is present.

To compare with \(G\), set \(\mathcal U_i=B\mathcal C_i\) for \(i=1,2\). These images are orthogonal, since \(\langle Bc,Bd\rangle=\langle c,Kd\rangle\). On \(\mathcal U_i\) the operator \(S=BB^*\) acts by \(\mu_i\); an image may of course be zero. Direct summation of the transpositions gives \[\begin{align*} Gx_i&=\frac{Nx_i-q}{2},\tag{25}\\ G(x_ix_j)&=(N-1)x_ix_j-\frac{q-1}{2}(x_i+x_j). \tag{26}\end{align*}\] For the second identity, only swaps involving exactly one of \(i,j\) contribute. Their sum is \[(N-2)x_ix_j-\frac12(x_i+x_j)\sum_{k\notin\{i,j\}}x_k =(N-1)x_ix_j-\frac{q-1}{2}(x_i+x_j),\] using \(x_i^2=x_i\) and \(\sum_kx_k=q\).

By (22) and (25), \(G\) acts on \(\mathcal U_1\) by \(N/2\). For \(c\in\mathcal C_2\), the expansion \[z_{ij}=1-p-x_i-x_j+2x_ix_j\] shows that \(Bc\) is proportional to \(\sum_{i<j}c_{ij}x_ix_j\): the constant and linear terms vanish by the row-zero conditions. Those same conditions cancel the linear terms in (26), so \(G\) acts on \(\mathcal U_2\) by \(N-1\). Equations (23) and (24) therefore give \(S\preceq G\) on \(\mathcal U_1\oplus\mathcal U_2\). This space is invariant under the self-adjoint \(G\), hence so is its orthogonal complement. On that complement \(S=0\), because \(B\mathcal C_0=0\) and the three coefficient spaces exhaust \(\mathbb R^M\); meanwhile \(G\succeq0\). This proves (20) on the whole slice.

For clarity, the possible zero images introduce no additional cases: when \(q=1\) or \(q=N-1\), (23) gives \(\mu_1=N/2\), and the trace identity gives \(\mu_2=0\) if \(N\ge4\); when \(q=N/2\), \(\mu_1=0\). For \(N=3\) the second image is absent. At \(N=4,q=2\), the trace identity gives \(\mu_2=3=N-1\), so the estimate includes this boundary case with equality. ◻

Proof. Work first in one \(a\)-fiber, whose assignments form a uniform \(q\)-subset slice of its \(N\) singleton vertices. If both vertices of \(b\) are singleton labels \(k,l\), the involution \(T_{a,b}\) acts on this slice exactly as \(\tau_{kl}\): it interchanges their assignments when they differ and acts trivially when they agree. Thus \(g_{a,b}=(I-\tau_{kl})/2\), while \(R_{a,b}=Q_{kl}\) in the notation of Lemma 8. If either vertex of \(b\) is not a singleton, the cross matrix cannot have both column sums equal to one, and both \(g_{a,b}\) and \(R_{a,b}\) vanish on the fiber. Since an orthogonal projection \(Q\) satisfies \(\|Qf\|^2=\langle f,Qf\rangle\), the two conditional sums in (27) are \(\langle f,Sf\rangle\) and \(\langle f,Gf\rangle\). Lemma 8 compares them. Both operators preserve the complete \(a\)-fibers, so averaging these conditional inequalities proves the corollary. ◻

Proof. The two orders of every disjoint pair occur in the sum, proving self-adjointness. Grouping them and applying Proposition 7 gives \[\begin{align*} \langle f,Df\rangle &\ge\sum_{\{a,b\}:\,a\cap b=\varnothing} \bigl(2\|g_{a,b}f\|^2 -\|R_{a,b}f\|^2-\|R_{b,a}f\|^2\bigr)\\ &=\sum_{a\in\binom V2} \left(\sum_{b:\,a\cap b=\varnothing}\|g_{a,b}f\|^2 -\sum_{b:\,a\cap b=\varnothing}\|R_{a,b}f\|^2\right) \ge0. \end{align*}\] The first sum is over unordered pairs of disjoint vertex pairs; the equality uses \(g_{a,b}=g_{b,a}\). The last inequality is Corollary 9, applied separately for each \(a\). ◻

Proof of Corollary 2. 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 1. Havel’s greedy degree-realization procedure [18], with deterministic tie-breaking, constructs one graph \(G_0\in\Omega_d\) in polynomial bit time.