OctoInformBeta

OpenAI preprint, October 2026 ยท Appendix A. Uniform smoothing of matching averages

Theorem A.1 [Uniform smoothing]: For three positive cells and large even NN, decay above an edge-product cutoff and polynomial dependence on intercell counts

Uniform smoothing of matching table averages.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Prescribing the numbers of matching edges within and between the cells of a partition of the vertices defines a conditional average of a function on perfect matchings. Uniform smoothing concerns the contribution from functions orthogonal to products of a bounded number of edge indicators.

Put ๐”น={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\} and C={0,1,2}C=\{0,1,2\}, with the colors indexed in this order. For an integer hโ‰ฅ0h\ge0, the paired vertex set and its size are Vh={iโˆˆโ„•:i<h}ร—๐”น,N=2h.V_h=\{i\in\mathbb N:i<h\}\times\mathbb B,\qquad N=2h.(1)โœฆ A matching involution on a finite set VV is a permutation MM satisfying M2=idM^2=\mathrm{id} and M(v)โ‰ vM(v)\ne v for every vโˆˆVv\in V; write โ„ณ(V)\mathcal M(V) for the set of these involutions and use โ„ณh=โ„ณ(Vh)\mathcal M_h=\mathcal M(V_h) on the vertex set in (1).โœฆ The Euclidean matching function space E(V)=โ„โ„ณ(V)E(V)=\mathbb R^{\mathcal M(V)} has inner product โŸจf,gโŸฉ=โˆ‘Mโˆˆโ„ณ(V)f(M)g(M)\langle f,g\rangle=\sum_{M\in\mathcal M(V)}f(M)g(M).โœฆ The uniform norm โˆฅgโˆฅu,X\|g\|_{u,X} of a real function gg on a nonempty finite set XX is the norm given by (2); โˆฅโ‹…โˆฅuโ†’u\|\cdot\|_{u\to u} denotes the induced operator norm. โˆฅgโˆฅu,X2=1|X|โˆ‘xโˆˆXg(x)2.\|g\|_{u,X}^2=\frac{1}{|X|}\sum_{x\in X}g(x)^2.(2)

The histogram s(z)s(z) of a coloring z:Vโ†’Cz:V\to C is the vector of its cell sizes.โœฆ The colorings with prescribed histogram ss form the set s(z)a=|{vโˆˆV:z(v)=a}|,๐’žs(V)={z:Vโ†’C:s(z)=s}.s(z)_a=|\{v\in V:z(v)=a\}|,\qquad \mathcal C_s(V)=\{z:V\to C:s(z)=s\}.(3) The unordered color pair type ฮธ(a,b)\theta(a,b) of colors a,bโˆˆCa,b\in C is the label abab with the smaller color written first.โœฆ Its six types are ordered 00,01,02,11,12,2200,01,02,11,12,22; the distinct color pairs are 01,02,1201,02,12, in that order. The matching color table t(M,z)t(M,z) of a matching Mโˆˆโ„ณ(V)M\in\mathcal M(V) and a coloring z:Vโ†’Cz:V\to C is the table of unoriented edge counts, with diagonal endpoint counts twice the internal-edge counts: tab(M,z)=12|{vโˆˆV:ฮธ(z(v),z(Mv))=ab}|.t_{ab}(M,z)=\frac12 |\{v\in V:\theta(z(v),z(Mv))=ab\}|.(4)โœฆ

For any finite set JJ, the paired vertex coloring correspondence sends a coloring z:Jร—๐”นโ†’Cz:J\times\mathbb B\to C to the ordered-pair coloring kz(i)=(z(i,false),z(i,true))k_z(i)=(z(i,\mathrm{false}),z(i,\mathrm{true})).โœฆ The reference color table ฯ„(z)\tau(z) counts these pairs by their unordered types: ฯ„ab(z)=|{iโˆˆJ:ฮธ(kz(i))=ab}|.\tau_{ab}(z)=|\{i\in J:\theta(k_z(i))=ab\}|.(5)โœฆ

The edge incidence coordinate xuvx_{uv} for vertices u,vโˆˆVu,v\in V is the real function on โ„ณ(V)\mathcal M(V) that indicates whether the matching pairs uu with vv.โœฆ For a nonnegative integer dd and a family x=(xe)eโˆˆAx=(x_e)_{e\in A} of real functions on a common set XX, the degree-bounded span Ld(x)L_d(x) is the linear span of products of at most dd members, including the empty product 11.โœฆ The matching polynomial space Pd(V)P_d(V) on a finite vertex set VV is the real linear span of products of at most dd edge incidence coordinates, including the empty product 11: xuv(M)=๐Ÿ{M(u)=v},Pd(V)=Ld((xuv)(u,v)โˆˆV2),Ld(x)=span⁡โ„{โˆj=1kxej:0โ‰คkโ‰คd,ejโˆˆA}.\begin{aligned} x_{uv}(M)&=\mathbf 1_{\{M(u)=v\}},\qquad P_d(V)=L_d((x_{uv})_{(u,v)\in V^2}),\\ L_d(x)&=\operatorname{span}_{\mathbb R} \left\{\prod_{j=1}^{k}x_{e_j}:0\le k\le d,\ e_j\in A\right\}. \end{aligned}(6) The orthogonal polynomial projection ฮ d:E(V)โ†’Pd(V)\Pi_d:E(V)\to P_d(V) is the orthogonal projection onto the subspace in (6).โœฆ

The incidence matrix IRI_R of a relation RR between finite sets XX and YY has entry 11 when R(x,y)R(x,y) holds and 00 otherwise.โœฆ The normalized incidence average CR,aC_{R,a} of a relation RR between finite sets XX and YY, with real normalizing factor aa, is the operator from real functions on XX to real functions on YY given by (CR,ag)(y)=1aโˆ‘xโˆˆXIR(y,x)g(x).(C_{R,a}g)(y)=\frac{1}{a}\sum_{x\in X}I_R(y,x)g(x).(7)โœฆ The fiber average FRF_R of a relation RR between finite sets XX and YY is the operator from real functions on XX to real functions on YY that uses each fiber cardinality as the normalizing factor in (7)โœฆ; the uniform average Av⁡B\operatorname{Av}_B over a subset BโІXB\subseteq X is the uniform averaging functional on real functions on XX: (FRg)(y)=(CR,|{xโˆˆX:R(x,y)}|g)(y),Av⁡B(g)=1|B|โˆ‘xโˆˆBg(x).(F_Rg)(y)=\bigl(C_{R,|\{x\in X:R(x,y)\}|}g\bigr)(y),\qquad \operatorname{Av}_B(g)=\frac{1}{|B|}\sum_{x\in B}g(x).(8) A zero denominator gives value zero in (7) and (8).

A table tt of six nonnegative integer counts is admissible for a coloring zz when the matching fiber Bt(z)B_t(z) below is nonempty. The conditional table operator TtT_t associated with a table tt of six nonnegative integer counts sends a real function on โ„ณ(V)\mathcal M(V) to its uniform average over the matching fiber Bt(z)B_t(z) at each coloring z:Vโ†’Cz:V\to C: Bt(z)={Mโˆˆโ„ณ(V):t(M,z)=t},(Ttg)(z)=Av⁡Bt(z)(g).B_t(z)=\{M\in\mathcal M(V):t(M,z)=t\},\qquad (T_tg)(z)=\operatorname{Av}_{B_t(z)}(g).(9) For a reference coloring f0:Vhโ†’Cf_0:V_h\to C, reference table compatibility is the relation t(M,z)=ฯ„(f0)t(M,z)=\tau(f_0) between Mโˆˆโ„ณhM\in\mathcal M_h and zโˆˆ๐’žs(f0)(Vh)z\in\mathcal C_{s(f_0)}(V_h) from (3).โœฆ Its fiber average is Tฯ„(f0)T_{\tau(f_0)} in (9), with the reference table from (5) and matching tables from (4).

The Claim

Theorem 1 (Uniform smoothing and polynomial table averages). Fix an integer Kโ‰ฅ0K\ge0. There are integers dโ‰ฅ1d\ge1 and h0โ‰ฅ0h_0\ge0 with the following property. Let hโ‰ฅh0h\ge h_0, let f0:Vhโ†’Cf_0:V_h\to C be a reference coloring with s(f0)a>0s(f_0)_a>0 for each aโˆˆCa\in C, and let fโˆˆE(Vh)f\in E(V_h). Then 1|๐’žs(f0)(Vh)|โˆ‘zโˆˆ๐’žs(f0)(Vh)(Tฯ„(f0)(fโˆ’ฮ df)(z))2โ‰ค1N2K1|โ„ณh|โˆ‘Mโˆˆโ„ณhf(M)2.\begin{aligned} &\frac{1}{|\mathcal C_{s(f_0)}(V_h)|} \sum_{z\in\mathcal C_{s(f_0)}(V_h)} \bigl(T_{\tau(f_0)}(f-\Pi_df)(z)\bigr)^2\\ &\qquad\le \frac{1}{N^{2K}}\, \frac{1}{|\mathcal M_h|}\sum_{M\in\mathcal M_h}f(M)^2. \end{aligned}(10)โœฆ Let JJ be a finite set, let dโ‰ฅ0d\ge0 be an integer, let z:Jร—๐”นโ†’Cz:J\times\mathbb B\to C be a coloring, and let fโˆˆPd(Jร—๐”น)f\in P_d(J\times\mathbb B). There is a polynomial Qโˆˆโ„[X01,X02,X12]Q\in\mathbb R[X_{01},X_{02},X_{12}] of total degree at most dd satisfying (11) for every table tt admissible for zz. (Ttf)(z)=Q(t01,t02,t12).(T_tf)(z)=Q(t_{01},t_{02},t_{12}).(11)โœฆ

In the paper, with II denoting the identity operator, the result reads: for every fixed number โ„“โ‰ฅ1\ell\ge1 of cells and real K>0K>0 there are integers dโ‰ฅ1d\ge1 and N0N_0 such that, for every even Nโ‰ฅN0N\ge N_0, every positive integer cell-size vector summing to NN, and every admissible table tt, the uniform operator norm satisfies โˆฅTt(Iโˆ’ฮ d)โˆฅuโ†’uโ‰คNโˆ’K\|T_t(I-\Pi_d)\|_{u\to u}\le N^{-K}, and, for each fixed partition ZZ and function ff, all values (Ttฮ df)(Z)(T_t\Pi_df)(Z) over admissible tables are represented by one polynomial of total degree at most dd in the intercell counts.

What Is Checked

The smoothing estimate (10) is stated over Euclidean matching functions and reference table fibers with three positive cell sizes, while the polynomial representation (11) is stated over edge-product spans on Jร—๐”นJ\times\mathbb B for arbitrary finite JJ.