Exponential PSD rank of positively shifted matching matrices

Proof. Appending scalar blocks \rho to the row factors and 1 to the column factors of A_n(0) gives a factorization of A_n(\rho). Consequently

Fix \rho=1/2 and apply Theorem 1.1. For all sufficiently large even n,

Edmonds’s description of P_n uses nonnegativity and odd-cut inequalities, within the affine space of degree equations \sum_{e\ni v}x_e=1 [3]. Thus T_n(0) is a slack matrix of this description. Every row inequality is tight at some perfect matching. Any redundant row is therefore a nonnegative combination of facet slack rows, so including it does not change PSD rank. The cone-factorization theorem identifies this rank with the minimum size of a semidefinite lift [5, Theorem 2.4 and Corollary 2.6].

For completeness, an arbitrary lift can be restricted to the smallest face of the PSD cone containing its feasible section. This face is a PSD cone of size at most r, and the section meets its relative interior, supplying the properness needed for factorization. An affine image can be made linear on the affine slice without increasing size: the slice cannot contain zero, since its intersection with the cone would then have a bounded affine image only if that image were a point. A linear functional equal to one on the slice therefore absorbs the translation. Taking c_0=c/2 proves the corollary.□

Proof. The uniform law of m and the restrictions (2.1) are equivariant under permutations of the k vertices. Since the symmetric group is transitive on X, the marginal law of a, obtained by first sampling m and then a\sim\pi_y^m, is uniform. This proves (2.4).

Fix b and y, and write T=T_y. Equip the function spaces on X and \mathcal M with the inner products for uniform probability, and put K=T^*T. This is a positive semidefinite self-adjoint operator. The marginal identity gives K1=1. We will show that \tr(K^2)=o(k), while every nonconstant eigenspace has dimension at least k/2. Together these estimates force the largest eigenvalue on the orthogonal complement of the constants to tend to zero.

The two-sample kernel. Sample m uniformly, and then sample a,a' independently from \pi_y^m conditional on m. Let J(a,a') be their joint probability, and let N=|X|. The density of this joint law relative to two independent uniform elements of X is D(a,a')=N^2J(a,a'). Indeed, for scalar functions B_1,B_2,

Consequently the ordinary matrix entries of K are D(a,a')/N, and symmetry gives

The joint law is permutation-invariant, so D(a,a') depends only on |a\cap a'|. Conditional on m, the two subsets choose independent g-subsets of the h internal pairs. If the second choice replaces exactly j pairs of the first, their intersection has size s+2(g-j)=w-2j. The probability of this event is

For two independent uniform elements of X, the probability of the same intersection size is

Both laws are uniform within each intersection class. The density there is therefore P_j/Q_j, and it vanishes on the remaining classes. The identities w=2g+s and k-w=2(h-g)+(d-s) ensure that every displayed Q_j is positive. Equation (2.7) becomes

A trace estimate. Since k=2h+d, w=k/2+O(1), and g=h/2+O_d(1), the central binomial estimates give

uniformly in b and y. Moreover, \binom w{2j}\ge\binom{2g}{2j} and \binom{k-w}{2j}\ge\binom{2(h-g)}{2j}. For integers 0\le j\le u, the identity

and the bounds \binom{2v}v\asymp4^v/\sqrt{v+1} imply

with an absolute constant C, including at the endpoints j=0,u. Applying this bound with u=g and u=h-g shows that the sum in (2.8) is at most

By (2.3), g_*=h/2+O_d(1), so this is O_d(\log(h+2)). Thus

From trace to contraction. We now use permutation symmetry to ensure that every nonconstant eigenvalue contributes many times to the trace. This is the multiplicity principle used, in a different setting, in [6, Lemma 3.2]; here an elementary argument suffices.

We claim that, for even k\ge6, every nonzero permutation-invariant subspace V\subseteq\R^X orthogonal to the constants has dimension at least k/2. Choose k/2 disjoint transpositions of the vertices. Their actions on V are commuting orthogonal involutions, so they admit simultaneous diagonalization with sign patterns in \{1,-1\}^{k/2}. If a nonzero simultaneous eigenspace has a pattern with j negative signs, where 0<j<k/2, permutations of the vertex pairs give \binom{k/2}j distinct patterns. Their eigenspaces are linearly independent, whence \dim V\ge\binom{k/2}j\ge k/2.

Otherwise every occurring pattern is constant, and the product of any two of the chosen transpositions acts as the identity on V. Invariance of V under all permutations implies the same for every product of two disjoint transpositions. Given five distinct labels a,b,c,e,f, the identity

then shows that every three-cycle acts as the identity. Thus the alternating group fixes V pointwise. It is transitive on X: a permutation taking one w-subset to another can have its parity corrected by a transposition inside the latter subset or its complement. Such a transposition exists for the present values of k and w. Every function on X invariant under the alternating group is therefore constant, contrary to the choice of V. This proves the claim.

The permutation invariance of the kernel means that K commutes with every vertex permutation. Each full eigenspace of its restriction to the orthogonal complement of the constants is therefore an invariant subspace of the kind just considered. Writing \mu for the largest eigenvalue on that complement, positive semidefiniteness and (2.11) imply

For B_0=B-\E_aB(a), it follows that

All estimates were uniform in b and y, so a single choice of \theta_d(k) proves (2.5). Summing that inequality over the entries of a matrix proves (2.6), with exactly the same constant.□

Proof. We first record the two-matrix estimate that gives the decomposition. For positive semidefinite A,B, let P be the spectral projection of A-B onto its nonnegative eigenspaces, and let Q=I-P. This is the same spectral projection used in binary quantum discrimination [8]; here we need a bound on squared Frobenius norms of the compressed matrices. In the block decomposition associated with P and Q, write A=(A_{uv})_{u,v=1}^2 and B=(B_{uv})_{u,v=1}^2. Since P commutes with A-B, we have A_{12}=B_{12}, A_{11}\succeq B_{11}, and B_{22}\succeq A_{22}. Thus

Here we used the nonnegativity of the trace of a product of two positive semidefinite matrices.

We now induct on L. The assertion for L=1 holds with P_1=I. For L\ge2, apply the preceding construction to A=A_1 and B=\sum_{j=2}^L A_j, and put P_1=P. Apply the induction hypothesis to the compressions QA_jQ, 2\le j\le L, on the range of Q. Extend the resulting projections by zero on the range of P, obtaining P_2,\ldots,P_L on the original space.

The terms on the left of (3.1) involving either P_1 or A_1 have sum at most

The first inequality uses nonnegative pairwise trace products in the first sum and the orthogonal block decomposition of QA_1Q in the second. To bound the overlaps introduced by compression, observe that for distinct j,j'\ge2,

This is the squared triangle inequality applied to Q=I-P. Moreover,

Combining these estimates with the induction hypothesis bounds the left side of (3.1) by

The full ordered overlap sum is 2\tr(A_1B)+\sum_{j\ne j',\,j,j'\ge2}\tr(A_jA_{j'}). Since C_{L-1}\ge1, the preceding bound is at most 2C_{L-1} times this sum. Taking C_L=2C_{L-1} completes the induction.□

Proof. For a matrix-valued function Z on X_i, use the notation

Applying (4.2) to each entry and summing gives

This inequality holds in every finite matrix dimension, with the same \theta.

Partial averages and the potential. Use the abbreviations m_{\le i}=(m_1,\ldots,m_i) and x_{>i}=(x_{i+1},\ldots,x_t), and likewise for y. At stage i we construct functions

depending also on m_{\le i}, such that

All matrices at stage i have a common row dimension R_i and r columns. Their Fourier coefficients refer only to the processed variables y_{\le i}. Define

Thus U_q^{(i)} has rL^i columns and is a function of x_{>i}. The potential is

where all listed variables are independent and uniform. At stage zero take R_0=r and H_{\varnothing}^{(0)}=F^{1/2}. Then C_{\varnothing}^{(0)}=F, so \Phi_0\le\E_x(\tr F(x))^2\le B^2. We will prove \Phi_{i+1}\le2\Phi_i while preserving (4.10).

Realizing one more average. Fix m_{\le i}, a branch q\in\Lambda^i, and x_{>i+1}. For the new coordinate abbreviate X_{i+1},Y_{i+1},m_{i+1} by X,Y,m, and write its input as x and its character variable as y. The old concatenation is now a matrix function U(x)=U_q^{(i)}(x;x_{>i+1}). Put

It has size rL^i by rL^i, and

The fixed data determine the entire function x\mapsto U(x) before the new averaging parameter m is chosen.

For a fixed m, form a matrix-valued function H' with R_{i+1}=L|X|R_i rows. We give different values of y disjoint row blocks by indexing those blocks with (y',x)\in Y\times X. This extra label will eliminate products between different y-values from the Fourier overlap calculation below. The block at (y',x) is

Consequently,

This stack performs the new average. We next split its space of row coordinates in a way that controls its Fourier coefficients.

For z\in\Lambda, concatenate the Fourier coefficients of H' at (p,z), using only the old weights:

The (y',x) row block of V_z is L^{-1}\chi_z(y')\sqrt{\pi_{y'}^m(x)}U(x). Multiplying the stacked matrices therefore gives the identity

In particular, \tr(A_zA_{z'})=\normF{V_z^{\mathsf T}V_{z'}}^2.

The overlap estimate. For z=z', Jensen’s inequality and (4.1) applied to (4.14) give

For z\ne z', let \mu=\E_xZ(x). Character orthogonality permits subtracting \mu from every summand in (4.14). Jensen’s inequality and (4.9) now give

Together with (4.12), these estimates say that

The new frequency Gram matrices thus have small total overlap in expectation. We can now use Lemma 3.1 to assign them to separate branches, charging the misplaced compressions to this overlap.

Splitting the stack and updating the weights. For each m, apply Lemma 3.1 to (A_z)_{z\in\Lambda}, obtaining projections (P_s)_{s\in\Lambda}. Define

Since \sum_sP_s=I and P_s^2=P_s=P_s^{\mathsf T}, we have \sum_s(H_{(q,s)}^{(i+1)})^{\mathsf T}H_{(q,s)}^{(i+1)} =H'^{\mathsf T}H'. Summing over q proves (4.10) at the new stage.

These projections may depend on m_{\le i+1} and x_{>i+1}, but they do not depend on any processed variable y_{\le i+1}. Hence they commute with taking the Fourier coefficients in these variables. We retain all R_{i+1} rows of every projected matrix, even when the ranks of the projections vary with the remaining inputs. This gives a common coordinate system for every branch at every value of those inputs. Since all sets are finite, the choices of projections for all histories and remaining inputs can be made simultaneously, using no future averaging parameters.

The new distance satisfies \operatorname{dist}((q,s),(p,z)) =\operatorname{dist}(q,p)+\mathbf1_{\{s\ne z\}}. The Gram matrix with the new weights is therefore

Cauchy–Schwarz for this sum of L matrices, followed by Lemma 3.1, gives

For the terms with s=z we used \normF{P_zA_zP_z}\le\normF{A_z}. There are L diagonal terms and L(L-1) ordered off-diagonal terms in (4.15). Taking expectation in (4.16) yields

This estimate was proved for every fixing of m_{\le i} and x_{>i+1}. Under the product probability law, the new m is independent of these variables. Although earlier projections can make Z(x) an arbitrary function of the current input x, it is independent of this new m, as required when applying (4.9). Thus we may sum over q and average over the fixed data to obtain \Phi_{i+1}\le2\Phi_i. At i=t, this proves (4.5) and (4.7), with R=R_t.

From the Gram potential to Fourier mass. Choose m with \sum_q\normF{C_q^m}^2\le2^tB^2. Each U_q^m has rL^t columns, so \rank(C_q^m)\le rL^t, regardless of its row dimension. For a positive semidefinite matrix C, \tr C\le\sqrt{\rank C}\,\normF{C}. Applying this inequality and then Cauchy–Schwarz over the L^t branches gives

This is (4.8).□

Proof. Write t=2l, split the vertices into two sets of size l, and take the union of d independent uniform perfect matchings between the two sides. Equivalently, choose d independent uniform permutations of [l].

It suffices to check vertex sets of size w\leq l. Fix such a nonempty set W, containing a vertices on the first side and b on the second, so that a+b=w. Always |\delta_H(W)|\geq d|a-b|. Thus a failure of (5.2) is possible only when |a-b|<.1w, in which case

If the cut has fewer than \beta dw edges, fewer than .05da of the da images of the first-side vertices can lie outside the second-side subset: indeed their number is at most \beta dw\leq (.01/.45)da<.05da.

There are at most \exp(.21da) choices for these exceptional images, where an image is specified by its domain vertex and permutation label. Here we used

For any prescribed set of nonexceptional images, sampling without replacement within each permutation bounds the probability that they all lie in the second-side subset by (b/l) to their number. Independence between permutations therefore gives

The exponent .21+.95\log(.55w/l) is negative. Using da\geq45w and \binom{2l}{w}\leq(2el/w)^w, a union bound over all sets of size w is consequently at most

The last inequality uses w/l\leq1 and \log(2e)+45(.21+.95\log(.55))<-8; all logarithms here are natural. Since \sum_{w\geq1}e^{-8w}<1, some choice of the permutations satisfies (5.2). A nontrivial connected component would have an empty cut, so the expansion inequality also gives connectivity.□

Proof. We specify \mathcal D on characters. First map any set of incidences to the edges having an odd number of incidences in that set. A character index p selects the incidences (i,j) for which j<d and p_{i,j}=1; denote their image by E(p)\subseteq E(H). This incidence map is linear over \mathbb F_2, so

where \triangle denotes symmetric difference.

If incidence signs agreed across every edge, \chi_p would be the product of the edge signs on E(p). Multiplying the vertex parity identities over a set S would prescribe the sign (-1)^{\sum_{i\in S}b_i} for the product on \delta_H(S): the signs of edges internal to S occur twice and cancel. Complementary sides of a cut prescribe opposite signs because the total prescribed parity is odd. When E(p) is a cut and p has low block degree, expansion selects a unique small side and hence a value for the functional.

Choosing the values on characters. Suppose that |p|_{\mathrm{blk}}\leq2D and that E(p) is a cut of H. Since |E(p)|\leq2Dd, expansion gives a side S(p) of this cut with

This side is unique: connectivity implies that two vertex sets with the same cut are equal or complementary. Define

Extending linearly defines \mathcal D on every real function on Y. The trivial character has S(0)=\varnothing, so \mathcal D(1)=1.

Positivity on low-degree squares. Let \mathcal I_D=\{p\in\Lambda^t:|p|_{\mathrm{blk}}\leq D\}, and consider the matrix

The cut sets of H form a vector subspace of \mathbb F_2^{E(H)}. Partition \mathcal I_D according to the coset of this subspace containing E(p). Entries between different classes are zero. Within a class every entry is a sign, and every diagonal entry is one.

To show that such a block is positive semidefinite, take any three indices p_1,p_2,p_3 in it. Each pair sum has block degree at most 2D, and so has a small cut side S_{ab}=S(p_a+p_b). Linearity of both the incidence map and the cut map gives

The set inside the cut has size at most 3t/5<t, by (5.9). Connectivity forces it to be empty. Therefore

Fixing a reference index p_0 in the class and setting \sigma_p=M_{p,p_0}, we obtain M_{p,p'}=\sigma_p\sigma_{p'}. Each block is thus a rank-one positive semidefinite matrix. If g=\sum_{p\in\mathcal I_D}\widehat g(p)\chi_p, it follows that

Values on disagreements. We next show that \mathcal D assigns value one to the product of the two bit signs on every edge. For a fixed edge e=uv, let T\subseteq\{u,v\} be the endpoints where the incidence of e is in the last position. On Y_i the parity constraint gives

Using this identity at the vertices in T, we can write

Before these replacements, the two selected incidences belong to the same edge and give the empty edge set under the incidence map. Replacing a last incidence by the other d-1 incidences toggles the full star at that vertex. Its image under the incidence map is \delta_H(\{i\}). Hence E(p)=\delta_H(T), including when u and v have parallel edges. For sufficiently large t, we have 2\leq2D and |T|\leq2\leq t/5, so T is the small side used in (5.10). The two signs cancel, giving

Since \mathbf1_{\{y_{u,e}\ne y_{v,e}\}} =(1-(-1)^{y_{u,e}+y_{v,e}})/2, every disagreement indicator has functional value zero. This proves \mathcal D(f_\epsilon)=-\epsilon.

Norm bound. Finally, all L^t character values in (5.10) have absolute value at most one. For any real function h, uniform orthonormal Fourier expansion gives \widehat h(p)=\E_{y\in Y}h(y)\chi_p(y), and therefore |\widehat h(p)|\leq\norm{h}_\infty. Thus

completing the proof.□

Proof. Compress to the span of the images of all column factors. This preserves their pairings with the row factors and reduces the size to some r\ge1. The average column factor is positive definite on this span. Hence the compact convex hull of the column factors contains a positive definite matrix J maximizing the determinant. The one-sided derivative of \log\det in the direction G_m-J is nonpositive, giving

Replace the column factors by J^{-1/2}G_mJ^{-1/2} and the row factors by J^{1/2}F_aJ^{1/2}. These congruences preserve PSD and trace pairings. The new column traces have the required bound. The new row trace is \tr(F_aJ), a convex combination of entries of the original row, and is at most B.□

Proof of Theorem 1.1. Use the constants d=100, \beta=1/100, and \tau=1/1000 of Section 5, and put L=2^{d-1}. Let C_L be the constant in Lemma 3.1. First choose \lambda>1 so that

Next fix an even integer k large enough for the local construction and for

Lemma 2.1 permits this choice. These constants are fixed independently of n and \rho.

Fix 0<\rho<1 and set \epsilon=1-\rho. For a large even n, let t be the largest even integer satisfying kt\le n. Then

Take a d-regular bipartite multigraph H on t vertices as in Lemma 5.1, and give its vertices charges b_i\in\{0,1\}, with exactly one charge equal to one. Order the d incidences at each vertex. Write Y_i for the parity-b_i incidence assignments, identified with the Boolean group on their first d-1 bits.

Realizing the restrictions by matchings. Partition kt vertices of K_n into cells C_1,\ldots,C_t of size k. The remaining vertices have even cardinality and will be paired in a fixed way. In cell i, choose the unique weight w_i\in\{k/2,k/2+1\} of parity b_i, and let X_i be the w_i-subsets of C_i. For a=(a_1,\ldots,a_t)\in\prod_iX_i, use the odd-cut row

It is odd because |U(a)|\equiv\sum_i b_i\equiv1\pmod2.

In each cell independently, sample the local column data m_i of Section 2: d ordered distinct terminals and a pairing of the other vertices. For every auxiliary edge e=uv, match the terminal at its incidence in C_u to the terminal at its incidence in C_v. Together with the internal pairings and the fixed remainder pairing, this gives a perfect matching M(m). Parallel edges in H use distinct terminals, so they cause no conflict. Distinct local data need not give distinct matchings; we simply use the factor of the matching they specify.

For y=(y_1,\ldots,y_t)\in\prod_iY_i, apply the local laws \pi_{y_i}^{m_i} independently. An internal pair has equal cut bits and contributes no crossing. The matched remainder is outside U(a). An intercell edge crosses exactly when its two terminal bits disagree, as illustrated in Figure 1. Thus every cut in the support of the product restriction satisfies

A factorization and its Fourier approximation. Suppose that A_n(\rho) has a PSD factorization of size at most 2^t. Its entries are positive and at most n. Lemma 6.1 gives factors of size r\le2^t with

Put F(a)=F_{U(a)}. For any fixed local column data m, let \overline F_m(y) be the product-restricted average of F. Equation (6.4) gives the exact identity

Apply Theorem 4.1 with the local channels above, the trace bound B=n, and Equation (6.2). It gives a choice of m and rectangular matrix functions H_q, indexed by q\in\Lambda^t, such that

Here \Lambda is the character group on d-1 free bits, and \dist counts differing blocks. Fix these data and set G=G_{M(m)}. By Equations (6.5) and (6.6),

Let D=\lfloor\tau t\rfloor. In branch q, retain only the Fourier coefficients at distance at most D from q, writing

The sum of squared norms of the discarded matrices at any y is at most

The first inequality is Cauchy–Schwarz over at most L^t characters in each branch. The second uses \normop G\le\tr G\le r, Equation (6.7), and the fact that an integer distance greater than D is greater than \tau t. The last line uses r\le2^t and Equation (6.1).

The full stack in Equation (6.8) has norm at most \sqrt n. Expanding the difference of the squared norms of that stack and its truncation, and then using Equation (6.9), gives

The separating functional. In branch q, multiplication by the real character \chi_q does not change any square. It translates a retained frequency p to p+q, whose block degree is \dist(p,q)\le D. This character translation is the elementary support-shifting principle used in Fourier sums of squares [4]. Consequently f_* is a sum of squares of real functions of block degree at most D, including after multiplication by the constant matrix G^{1/2}.

Proposition 5.2 therefore supplies a functional \mathcal D with

On the other hand, its norm bound and Equation (6.10) give

by Equation (6.3), since k is fixed. For sufficiently large n, this is smaller than \epsilon, a contradiction.

We have excluded every factorization of size at most 2^t. For all sufficiently large n, Equation (6.3) also gives t\ge n/(2k). Thus

Taking c=1/(2k) proves the theorem. Only the final comparison with \epsilon=1-\rho makes the threshold depend on \rho.□

Proof. Write h=N/2. For a fixed matching, the number of partitions giving it table t is

The first formula assigns cell types to the h edges and chooses which endpoint occupies which cell for each intercell edge. Permutation transitivity shows that the table probability is p_t=D_t/|\mathcal Z|, whether the matching or the partition is fixed. Thus the density kernel of T_t, relative to the uniform measures, is the table indicator divided by p_t.

Let J(M,M') count partitions giving table t to both matchings. The density kernel of \mathcal A=T_t^*T_t is consequently

where M,M' are independent and uniform.

We first bound this kernel using the alternating cycles of M\cup M'. Define

The array \gamma is symmetric, has total sum one, and has row sums \pi. For a probability vector or array write H(p)=-\sum_jp_j\log p_j, with 0\log0=0. The factorial formulas imply

To check the remainder uniformly, including zero table entries, put R_0=0 and R_j=\log(j!)-j\log j+j for j\ge1. Integral comparison gives 0\le R_j\le1+\log(j+1), and direct substitution gives

There are \ell(\ell+1)/2 unordered table entries, proving the stated lower bound. In the leading term, splitting each unordered off-diagonal frequency into two ordered frequencies accounts for the power of two in D_t.

Retain doubled edges in M\cup M', so that its components are alternating cycles, including cycles of length two. Orient each cycle and write c=c(M,M') for their number. The matrix W_{uv}=\gamma_{uv}/\pi_u is nonnegative and stochastic. Give a vertex coloring by 1,\ldots,\ell the weight obtained by multiplying W_{uv} over the oriented edges, where u,v are the tail and head colors.

Every coloring counted by J(M,M') has weight

Indeed, each vertex occurs once as a tail, so the denominator is \prod_u\pi_u^{s_u}. The two matchings together contribute 2t_{uv} edges of each unordered type. Symmetry of \gamma makes their orientations irrelevant, and the numerator is \prod_{u\le v}\gamma_{uv}^{2t_{uv}}, with zero exponents omitted. These expressions give (A.6); no counted coloring uses a zero entry of \gamma.

For a cycle of length a, the sum of weights over all its colorings is \tr(W^a)\le\ell. Summing over all vertex colorings therefore bounds the total weight of the colorings counted by J by \ell^c. Equations (A.4)–(A.6) yield

It remains to average the cycle factor. Set b=\ell^2. The number b^c counts colorings that are constant on every edge of both matchings. Fix M, and suppose its h edges have color multiplicities j_1,\ldots,j_b, summing to h. Averaging the number of such colorings over M' gives the contribution

where (-1)!!=1. For the inequality, partition a 2h-element set into blocks of sizes 2j_i: the numerator counts only those h-element subsets taking j_i elements from each block. There are at most (h+1)^b possible multiplicity vectors. Hence \E\ell^{2c}\le(h+1)^{\ell^2}. Squaring (A.7) and using (A.4) proves (A.3).□

Proof. Fix a set of d vertices, and let G\cong S_{N-d} permute the other vertices. A G-orbit of matchings is determined by the internal matching F on the fixed vertices: a permutation can first align the outside partners of all unmatched fixed vertices and then align the remaining outside edges. The orbit indicator is

On expansion, a nonzero monomial uses only disjoint edges among those d vertices, and therefore at most \lfloor d/2\rfloor edge indicators. All G-invariant functions consequently belong to \mathcal P_d.

If a Young diagram has first row of length at least N-d, the branching rule gives a G-fixed vector in its irreducible representation: remove corner boxes until only a row of size N-d remains. Such a representation cannot occur in \mathcal P_d^\perp, since any such copy would provide a nonzero G-fixed vector there.

A first column of length at least N-d similarly gives a vector transforming by the sign character of G. No nonzero matching function has this transformation law when N>2d. In fact, every matching then contains an edge entirely outside the fixed vertices; transposing its endpoints belongs to G, fixes that matching, and reverses the sign of the function. The function must vanish at every matching. Thus a diagram occurring in \mathcal P_d^\perp has both first row and first column shorter than N-d.

Let \lambda be any remaining diagram. The product of its first row and first column lengths is at least N. Transpose if necessary so that its first row has length b\ge\sqrt N; transposition preserves the number of standard tableaux. Retain that row and a Young subdiagram of exactly d boxes below it. Such a subdiagram exists because N-b\ge d.

For large N, we have b\ge2d. Put 1,\ldots,d into the first d positions of the top row. Choose any d of the remaining b labels d+1,\ldots,b+d for the lower boxes, fill those boxes in a fixed standard order, and put the unused labels increasingly into the rest of the top row. Each lower box is in one of the first d columns, so the resulting tableau is standard. The \binom bd choices give distinct tableaux of this subdiagram. Each extends to \lambda by adding the remaining boxes along a fixed corner-addition chain with successively larger labels. The dimension f^\lambda therefore satisfies

as required.□

Proof of Theorem A.1. Complexification does not change operator norms. The operator \mathcal A=T_t^*T_t commutes with vertex permutations, since T_t intertwines their actions on matchings and partitions. The projection Q=I-\Pi_d also commutes with permutations, because \mathcal P_d is invariant. The compression B=Q\mathcal A Q, acting on \mathcal P_d^\perp, is therefore positive semidefinite and equivariant. Moreover,

The first inequality is contraction of the Hilbert–Schmidt norm under orthogonal compression and does not require Q and \mathcal A to commute.

If B\ne0, its largest-eigenvalue eigenspace is invariant and contains an irreducible constituent. Lemma A.3 and the fourth-moment bound give

The same inequality holds if B=0. Choose d so that d/2>b_\ell+4K. For all sufficiently large N, this proves (A.2), uniformly in the sizes and the table.

To prove the polynomial assertion, fix a partition and a generating product of edge indicators. Repeated indicators may be removed, and a product containing two distinct incident edges vanishes. Otherwise the specified edges form a partial matching. Let m_{uv} be its type counts and let

be the number of its endpoints in cell u. The probability that a matching with table t contains these specified edges is

Indeed, apply a uniform cell-preserving vertex permutation to any one matching with table t. This is uniform over all such matchings by transitivity. The denominator counts injections of the specified endpoint lists, while the numerator chooses distinct edges of each type and the two orientations of each internal edge. The denominator is positive because a_u\le s_u. If t_{uv}<m_{uv} for any type, its falling factorial is zero, as required.

The numerator of (A.8) has total degree equal to the number of specified edges. Equation (A.1) expresses every t_{uu} as an affine function of the intercell counts. Thus the containment probability is a polynomial of the required degree in those counts. By linearity this holds for \Pi_df; its expansion in edge products is fixed independently of t, so the resulting polynomial works simultaneously for all admissible tables.□

Proof. Apply Theorem A.1 with \ell=3, intercell counts t_{12}=x, t_{13}=y, t_{23}=z, and internal counts (a-x-y)/2, (b-x-z)/2, (c-y-z)/2.□