OctoInformBeta

OpenAI preprint, September 2026 · §4. The extremal contradiction

Coordinate images, compatibility and the extremal objective: Two families PP, QQ of pairs in X×XX \times X: admissibility, the uncovered points, the sum M+dM + d and the new families ℛ\mathcal R, 𝒞\mathcal C

Compatible pairs of families and the extremal objective.

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, the arc relation of a digraph on XX in which loops are allowed. The points of X×XX \times X form a square array, the point (i,j)(i, j) in row ii and column jj, and a family of pairs in X×XX \times X is a set of points of the array. This item defines when PP and QQ are compatible and when admissible, the number of points that neither family reaches, the objective built from that number and the sizes of PP and QQ, and two new families formed from them.

Coordinate Images and Conflicts

The left image of a family SS of pairs in X×XX \times X is the family F1SF_1 S of the pairs obtained from a pair of SS by advancing its first coordinate along an arc, and its right image is the family F2SF_2 S obtained in the same way by advancing the second coordinate: F1S={(i,j):(p,j)∈S and p→i for some p∈X},F_1 S = \{(i, j) : (p, j) \in S \text{ and } p \to i \text{ for some } p \in X\},(1)✦ F2S={(i,j):(i,s)∈S and s→j for some s∈X}.F_2 S = \{(i, j) : (i, s) \in S \text{ and } s \to j \text{ for some } s \in X\}.(2)✦ We write F12=F1∘F1F_1^2 = F_1 \circ F_1 and F22=F2∘F2F_2^2 = F_2 \circ F_2.

A point of X×XX \times X is covered by PP when it lies in F1PF_1 P, and by QQ when it lies in F2QF_2 Q. A pair (p,j)(p, j) in X×XX \times X conflicts with a pair (i,s)(i, s) when p→ip \to i and s→js \to j.✦

The Claim

Definition 1. Let →\to be a relation on a finite set XX, and let PP and QQ be families of pairs in X×XX \times X. The families PP and QQ are compatible, or conflict-free, when no pair of PP conflicts with a pair of QQ: there are no (p,j)∈P and (i,s)∈Q with p→i and s→j.\text{there are no } (p, j) \in P \text{ and } (i, s) \in Q \text{ with } p \to i \text{ and } s \to j.(3)✦

The diagonal of X×XX \times X is the family Δ={(v,v):v∈X},\Delta = \{(v, v) : v \in X\},(4)✦ and PP and QQ are admissible when they are compatible and both contain the diagonal: P and Q compatible,Δ⊆P,Δ⊆Q.P \text{ and } Q \text{ compatible}, \qquad \Delta \subseteq P, \qquad \Delta \subseteq Q.(5)✦

For i,j∈Xi, j \in X, the column of PP at jj and the row of QQ at ii are the subsets of XX col⁡jP={p∈X:(p,j)∈P},\operatorname{col}_j P = \{p \in X : (p, j) \in P\},(6)✦ row⁡iQ={s∈X:(i,s)∈Q}.\operatorname{row}_i Q = \{s \in X : (i, s) \in Q\}.(7)✦

The uncovered points of PP and QQ are the points of X×XX \times X covered by neither family, U=(X×X)\(F1P∪F2Q),U = (X \times X) \setminus (F_1 P \cup F_2 Q),(8)✦ and d=|U|d = |U| is their number.✦ The objective of PP and QQ is the natural number M+d,where M=|P|+|Q|.M + d, \qquad \text{where } M = |P| + |Q|.(9)✦

From QQ and from PP two new families are formed, the left candidate family ℛ\mathcal R and the right candidate family 𝒞\mathcal C: ℛ=(X×X)\F22Q,\mathcal R = (X \times X) \setminus F_2^2 Q,(10)✦ 𝒞=(X×X)\F12P.\mathcal C = (X \times X) \setminus F_1^2 P.(11)✦

What Is Checked

The definitions (3) to (11) are stated over an arbitrary relation →\to on a finite set XX and two families PP and QQ of pairs in X×XX \times X, through the images (1) and (2) and the conflict of two pairs.

About these constructions the library proves one identity: when PP and QQ are compatible, d+|F1P|+|F2Q|=|X|2.d + |F_1 P| + |F_2 Q| = |X|^2.(12)✦