OctoInformBeta

OpenAI preprint, September 2026 Β· Β§3. Pruning two families of pairs

Kernel restriction and the matching bound: Under locally maximal ranks, kernel vectors of BB and N𝖳N^{\mathsf T} have zero product on conflicts; the bound holds when Ξ±\alpha and Ξ²\beta are maximum

Kernel vectors on conflicts and the bound |Z|+|H||Z|+|H| on matchings.

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

Let β†’\to be a relation on a finite set XX, written with arcs xβ†’yx \to y, and let β„›\mathcal R and π’ž\mathcal C be families of pairs in XΓ—XX \times X. A pair (p,j)(p, j) of β„›\mathcal R and a pair (i,s)(i, s) of π’ž\mathcal C conflict when pβ†’ip \to i and sβ†’js \to j.✦

The set ZZ is the set of the pairs (i,j)(i, j), and HH the set of the pairs (p,s)(p, s), for which some (p,j)βˆˆβ„›(p, j) \in \mathcal R and (i,s)βˆˆπ’ž(i, s) \in \mathcal C conflict. A pair (p,j)(p, j) covers a pair (i,j)(i, j) from the left when pβ†’ip \to i✦, and a pair (i,s)(i, s) covers a pair (i,j)(i, j) from the right when sβ†’js \to j.✦

When real numbers are placed on the arcs of β†’\to and four matrices are built from them, how do vectors in the kernels of these matrices sit on the two pairs of a conflict? And how large is a matching of the bipartite graph whose edges are the conflicts and the covers, measured against |Z|+|H||Z| + |H|?

Coefficients and the Four Maps

Real coefficients aa, one number axya_{xy} for each pair of points xx, yy of XX, are supported on β†’\to when axy=0a_{xy} = 0 whenever xβ†’ΜΈyx \not\to y.✦

For real coefficients aa and bb, the real matrices L:ℝℛ→ℝZL : \mathbb R^{\mathcal R} \to \mathbb R^{Z}, N:ℝZβ†’β„π’žN : \mathbb R^{Z} \to \mathbb R^{\mathcal C}, B:ℝℛ→ℝHB : \mathbb R^{\mathcal R} \to \mathbb R^{H} and A:ℝHβ†’β„π’žA : \mathbb R^{H} \to \mathbb R^{\mathcal C} act on vectors uβˆˆβ„β„›u \in \mathbb R^{\mathcal R}, wβˆˆβ„Zw \in \mathbb R^{Z} and xβˆˆβ„Hx \in \mathbb R^{H} by (Lu)ij=βˆ‘p:(p,j)βˆˆβ„›apiupj,(Bu)ps=βˆ‘j:(p,j)βˆˆβ„›bsjupj,(Lu)_{ij} = \sum_{p \,:\, (p, j) \in \mathcal R} a_{pi}\, u_{pj}, \qquad (Bu)_{ps} = \sum_{j \,:\, (p, j) \in \mathcal R} b_{sj}\, u_{pj},(1) (Nw)is=βˆ‘j:(i,j)∈Zbsjwij,(Ax)is=βˆ‘p:(p,s)∈Hapixps,(Nw)_{is} = \sum_{j \,:\, (i, j) \in Z} b_{sj}\, w_{ij}, \qquad (Ax)_{is} = \sum_{p \,:\, (p, s) \in H} a_{pi}\, x_{ps},(2) for (i,j)∈Z(i, j) \in Z, (p,s)∈H(p, s) \in H and (i,s)βˆˆπ’ž(i, s) \in \mathcal C.

Fibers and Locally Maximal Ranks

For a family PP of pairs in XΓ—XX \times X and a point pp of XX, the fiber of PP at pp is the set Pp={j:(p,j)∈P}P_p = \{j : (p, j) \in P\}✦, and the restriction of a vector uβˆˆβ„Pu \in \mathbb R^{P} to it is the vector u|pβˆˆβ„Ppu|_p \in \mathbb R^{P_p} with entries upju_{pj}.✦

For points pp and ii of XX and real coefficients bb, the fiber matrix Dp,iD^{p,i} is the real matrix with rows indexed by π’ži\mathcal C_i and columns by β„›p\mathcal R_p whose entry in row ss and column jj is bsjb_{sj}.✦

A real matrix DD with rows indexed by a set II and columns by a set JJ is supported on a set TβŠ†IΓ—JT \subseteq I \times J of positions when Dsj=0D_{sj} = 0 for every (s,j)βˆ‰T(s, j) \notin T.✦

Real coefficients bb have locally maximal ranks on β„›\mathcal R and π’ž\mathcal C when, for every arc pβ†’ip \to i, every real matrix DD with rows indexed by π’ži\mathcal C_i and columns by β„›p\mathcal R_p that is supported on the local support {(s,j):sβ†’j}\{(s, j) : s \to j\} of the arc satisfies rank⁡D≀rank⁡Dp,i.\operatorname{rank} D \le \operatorname{rank} D^{p,i}.(3)✦

The Augmented Graph

The augmented bipartite graph Ξ“\Gamma has left side β„›βŠ”Z\mathcal R \sqcup Z✦ and right side π’žβŠ”Z\mathcal C \sqcup Z✦, with two disjoint copies of ZZ. A pair of β„›\mathcal R is joined to a pair of π’ž\mathcal C when the two conflict, a pair of β„›\mathcal R to a point of ZZ on the right when it covers the point from the left, and a point of ZZ on the left to a pair of π’ž\mathcal C when the pair covers the point from the right; no two points of ZZ are joined.✦

The edges of Ξ“\Gamma between β„›\mathcal R and ZZ form the cover graph Ξ“β„›\Gamma_{\mathcal R} with sides ZZ and β„›\mathcal R: its edges are the positions of LL in (1) whose entry apia_{pi} sits on an arc.✦ The edges between ZZ and π’ž\mathcal C form the cover graph Ξ“π’ž\Gamma_{\mathcal C} with sides ZZ and π’ž\mathcal C: its edges are the positions of N𝖳N^{\mathsf T}, from (2), whose entry bsjb_{sj} sits on an arc.✦

For a matching MM of Ξ“\Gamma, its part Ξ±\alpha is the set of its edges in Ξ“β„›\Gamma_{\mathcal R}✦ and its part Ξ²\beta the set of its edges in Ξ“π’ž\Gamma_{\mathcal C}.✦

The Claim

Theorem 1. Let β†’\to be a relation on a finite set XX and let β„›\mathcal R and π’ž\mathcal C be families of pairs in XΓ—XX \times X.

(a) Let bb be real coefficients supported on β†’\to, let pβ†’ip \to i be an arc, and let u∈ker⁡Bu \in \ker B and v∈ker⁡N𝖳v \in \ker N^{\mathsf T}. Then Dp,iu|p=0D^{p,i}\, u|_p = 0(4)✦ and (Dp,i)𝖳v|i=0.(D^{p,i})^{\mathsf T}\, v|_i = 0.(5)✦

(b) Let bb moreover have locally maximal ranks on β„›\mathcal R and π’ž\mathcal C. If (p,j)βˆˆβ„›(p, j) \in \mathcal R and (i,s)βˆˆπ’ž(i, s) \in \mathcal C conflict, then every u∈ker⁡Bu \in \ker B and every v∈ker⁡N𝖳v \in \ker N^{\mathsf T} satisfy upjvis=0.u_{pj}\, v_{is} = 0.(6)✦

(c) Under the hypotheses of (b), if (p,j)βˆˆβ„›(p, j) \in \mathcal R and (i,s)βˆˆπ’ž(i, s) \in \mathcal C conflict and some v∈ker⁡N𝖳v \in \ker N^{\mathsf T} has vis=1v_{is} = 1, then every u∈ker⁡Bu \in \ker B satisfies upj=0.u_{pj} = 0.(7)✦

(d) Under the hypotheses of (b), let (pe,je)βˆˆβ„›(p_e, j_e) \in \mathcal R and (ie,se)βˆˆπ’ž(i_e, s_e) \in \mathcal C conflict for e=1,…,ke = 1, \dots, k, and let ve∈ker⁡N𝖳v^e \in \ker N^{\mathsf T} and ueβˆˆβ„β„›u^e \in \mathbb R^{\mathcal R} satisfy viesee=1v^e_{i_e s_e} = 1 and upfjfe=Ξ΄efu^e_{p_f j_f} = \delta_{ef} for all ee and ff. Then Bu1,…,Buk are linearly independent in ℝH.Bu^1, \dots, Bu^k \text{ are linearly independent in } \mathbb R^{H}.(8)✦

(e) If, in (d), aa is also supported on β†’\to and Lue=0Lu^e = 0 for every ee, then k≀dim⁡ker⁡A.k \le \dim \ker A.(9)✦

(f) Let Ξ±\alpha be a maximum matching of Ξ“β„›\Gamma_{\mathcal R} and Ξ²\beta a maximum matching of Ξ“π’ž\Gamma_{\mathcal C}. Let (p1,j1),…,(pk,jk)(p_1, j_1), \dots, (p_k, j_k) be distinct pairs of β„›\mathcal R unmatched by Ξ±\alpha and (i1,s1),…,(ik,sk)(i_1, s_1), \dots, (i_k, s_k) distinct pairs of π’ž\mathcal C unmatched by Ξ²\beta, with (pe,je)(p_e, j_e) and (ie,se)(i_e, s_e) in conflict for every ee. Then k+|Ξ±|+|Ξ²|≀|Z|+|H|.k + |\alpha| + |\beta| \le |Z| + |H|.(10)✦

(g) Let MM be a matching of Ξ“\Gamma whose parts Ξ±\alpha and Ξ²\beta are maximum matchings of Ξ“β„›\Gamma_{\mathcal R} and Ξ“π’ž\Gamma_{\mathcal C}. Then |M|≀|Z|+|H|.|M| \le |Z| + |H|.(11)✦

What Is Checked

The claim is stated over a relation β†’\to on a finite set XX, families β„›\mathcal R and π’ž\mathcal C of pairs in XΓ—XX \times X with their conflicts, their covers and the sets ZZ and HH, real coefficients supported on β†’\to with the maps LL, NN, BB and AA, the fiber matrices Dp,iD^{p,i}, the restrictions to fibers and the condition of locally maximal ranks, and the augmented graph Ξ“\Gamma with its cover graphs Ξ“β„›\Gamma_{\mathcal R} and Ξ“π’ž\Gamma_{\mathcal C} and their matchings and maximum matchings.