OctoInformBeta

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

The steps of the proof of Proposition 4.1: Under positive indegree and strict growth, a pruning of the new families of an admissible pair is an admissible pair of larger M+dM + d

The steps of the extremal argument for Proposition 4.1.

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 XX be the finite vertex set of a digraph, with u→wu \to w for an arc. The proof of Proposition 4.1 is an extremal argument about two families PP and QQ of pairs in X×XX \times X; this page states its steps.

Lay X×XX \times X out as a square array, the pair (p,j)(p, j) in row pp and column jj. The left image F1SF_1 S of a family SS of pairs is the family of the pairs reached from a pair of SS by one move along an arc within its column✦, and the right image F2SF_2 S is the same within its row: F1S={(i,j):(p,j)∈S and p→i for some p},F2S={(i,j):(i,s)∈S and s→j for some s},\begin{aligned} F_1 S &= \{(i, j) : (p, j) \in S \text{ and } p \to i \text{ for some } p\},\\ F_2 S &= \{(i, j) : (i, s) \in S \text{ and } s \to j \text{ for some } s\}, \end{aligned}(1)✦ with F12=F1∘F1F_1^2 = F_1 \circ F_1 and F22=F2∘F2F_2^2 = F_2 \circ F_2. The column of a family PP at a vertex jj is the set col⁡jP={p∈X:(p,j)∈P}\operatorname{col}_j P = \{p \in X : (p, j) \in P\}✦, and the row of a family QQ at a vertex ii is the set row⁡iQ={s∈X:(i,s)∈Q}\operatorname{row}_i Q = \{s \in X : (i, s) \in Q\}✦.

Conditions on the Digraph

The image of a set SS of vertices is the set F(S)={y:x→y for some x∈S},F(S) = \{y : x \to y \text{ for some } x \in S\},(2)✦ which may meet SS; we write F2=F∘FF^2 = F \circ F. A set SS of vertices is proper when S≠XS \neq X.

A digraph on XX is oriented when it has no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u✦, and has positive indegree when every vertex has an in-neighbor✦. A digraph on XX has strict growth when every nonempty proper set SS of vertices satisfies |S|+|F2(S)|<2|F(S)|.|S| + |F^2(S)| < 2\,|F(S)|.(3)✦

Admissible Pairs and the Objective

A pair (p,j)(p, j) conflicts with a pair (i,s)(i, s) when p→ip \to i and s→js \to j.✦ Two families ℛ\mathcal R and 𝒞\mathcal C are conflict-free when no pair of ℛ\mathcal R conflicts with a pair of 𝒞\mathcal C✦, and the points (i,j)(i, j) and (p,s)(p, s) of the conflicts between them form the sets Z(ℛ,𝒞)={(i,j):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some p,s},H(ℛ,𝒞)={(p,s):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some i,j}.\begin{aligned} Z(\mathcal R, \mathcal C) &= \{(i, j) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } p, s\},\\ H(\mathcal R, \mathcal C) &= \{(p, s) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } i, j\}. \end{aligned}(4) A pair (P,Q)(P, Q) of families is compatible when PP and QQ are conflict-free.✦ The diagonal of XX is the family Δ={(v,v):v∈X}\Delta = \{(v, v) : v \in X\}, the main diagonal of the array✦, and a pair (P,Q)(P, Q) of families is admissible when it is compatible and both PP and QQ contain Δ\Delta✦.

A pair in X×XX \times X is covered by two families ℛ\mathcal R and 𝒞\mathcal C when it lies in F1ℛ∪F2𝒞F_1 \mathcal R \cup F_2 \mathcal C, and uncovered otherwise.✦ The number of pairs uncovered by PP and QQ is d(P,Q)=|(X×X)\(F1P∪F2Q)|,d(P, Q) = \bigl|(X \times X) \setminus (F_1 P \cup F_2 Q)\bigr|,(5)✦ and the objective of (P,Q)(P, Q) is M+dM + d, where M=|P|+|Q|M = |P| + |Q| and d=d(P,Q)d = d(P, Q)✦.

New Families and Pruning

The new families of a pair (P,Q)(P, Q) are ℛ=(X×X)\F22Q,𝒞=(X×X)\F12P.\mathcal R = (X \times X) \setminus F_2^2 Q, \qquad \mathcal C = (X \times X) \setminus F_1^2 P.(6)

A pruning result of two families ℛ\mathcal R and 𝒞\mathcal C is a pair (ℛ′,𝒞′)(\mathcal R', \mathcal C') of conflict-free families with ℛ′⊆ℛ\mathcal R' \subseteq \mathcal R and 𝒞′⊆𝒞\mathcal C' \subseteq \mathcal C such that ℛ′\mathcal R' contains every pair of ℛ\mathcal R that conflicts with no pair of 𝒞\mathcal C, 𝒞′\mathcal C' contains every pair of 𝒞\mathcal C with which no pair of ℛ\mathcal R conflicts, and |ℛ\ℛ′|+|𝒞\𝒞′|≤|H(ℛ,𝒞)|+|U|,|\mathcal R \setminus \mathcal R'| + |\mathcal C \setminus \mathcal C'| \le |H(\mathcal R, \mathcal C)| + |U|,(7)✦ where UU is the set of the points of Z(ℛ,𝒞)Z(\mathcal R, \mathcal C) uncovered by ℛ′\mathcal R' and 𝒞′\mathcal C'.

The Claim

Theorem 1. Let XX be the finite vertex set of a digraph, let (P,Q)(P, Q) be a pair of families of pairs in X×XX \times X, and let ℛ\mathcal R and 𝒞\mathcal C be its new families.

If the digraph is oriented, then (Δ,Δ) is an admissible pair.(\Delta, \Delta) \text{ is an admissible pair.}(8)✦ If (P,Q)(P, Q) is compatible, QQ contains Δ\Delta and the digraph has positive indegree, then col⁡jP≠Xfor every vertex j.\operatorname{col}_j P \neq X \quad \text{for every vertex } j.(9)✦ If (P,Q)(P, Q) is compatible, PP contains Δ\Delta and the digraph has positive indegree, then row⁡iQ≠Xfor every vertex i.\operatorname{row}_i Q \neq X \quad \text{for every vertex } i.(10)✦

If XX is nonempty, the digraph has strict growth and every column of PP is nonempty and proper, then |P|+|F12P|<2|F1P|.|P| + |F_1^2 P| < 2\,|F_1 P|.(11)✦ If XX is nonempty, the digraph has strict growth and every row of QQ is nonempty and proper, then |Q|+|F22Q|<2|F2Q|.|Q| + |F_2^2 Q| < 2\,|F_2 Q|.(12)✦

If (P,Q)(P, Q) is admissible and the digraph has positive indegree and strict growth, then |P|+|Q|+2d(P,Q)<|ℛ|+|𝒞|.|P| + |Q| + 2\,d(P, Q) < |\mathcal R| + |\mathcal C|.(13)✦ If (P,Q)(P, Q) is compatible and PP contains Δ\Delta, then Δ⊆ℛ,\Delta \subseteq \mathcal R,(14)✦ and if (P,Q)(P, Q) is compatible and QQ contains Δ\Delta, then Δ⊆𝒞.\Delta \subseteq \mathcal C.(15)✦ If PP contains Δ\Delta, then Δ and 𝒞 are conflict-free,\Delta \text{ and } \mathcal C \text{ are conflict-free},(16)✦ and if QQ contains Δ\Delta, then ℛ and Δ are conflict-free.\mathcal R \text{ and } \Delta \text{ are conflict-free}.(17)✦ With no further hypothesis, H(ℛ,𝒞)⊆(X×X)\(F1P∪F2Q).H(\mathcal R, \mathcal C) \subseteq (X \times X) \setminus (F_1 P \cup F_2 Q).(18)✦

If (P,Q)(P, Q) is admissible and (P′,Q′)(P', Q') is a pruning result of ℛ\mathcal R and 𝒞\mathcal C, then (P′,Q′) is an admissible pair.(P', Q') \text{ is an admissible pair.}(19)✦ If (P′,Q′)(P', Q') is a pruning result of any two families ℛ0\mathcal R_0 and 𝒞0\mathcal C_0 with |H(ℛ0,𝒞0)|≤d(P,Q)|H(\mathcal R_0, \mathcal C_0)| \le d(P, Q) and |P|+|Q|+2d(P,Q)<|ℛ0|+|𝒞0||P| + |Q| + 2\,d(P, Q) < |\mathcal R_0| + |\mathcal C_0|, then |P|+|Q|+d(P,Q)<|P′|+|Q′|+d(P′,Q′).|P| + |Q| + d(P, Q) < |P'| + |Q'| + d(P', Q').(20)✦

If some pair of families has a given property, admissibility for instance, then there is a pair (P0,Q0)(P_0, Q_0) with the property such that every pair (P′,Q′)(P', Q') with the property has |P′|+|Q′|+d(P′,Q′)≤|P0|+|Q0|+d(P0,Q0).|P'| + |Q'| + d(P', Q') \le |P_0| + |Q_0| + d(P_0, Q_0).(21)✦

What Is Checked

The claims (8) to (21) are stated over a digraph on a finite set XX with its image FF and the conditions of being oriented, of positive indegree and of strict growth, and over families of pairs in X×XX \times X with their left and right images, columns and rows, the diagonal, conflicts, conflict-free families and the sets ZZ and HH, compatible and admissible pairs, covered and uncovered pairs, the number dd and the objective M+dM + d, the new families ℛ\mathcal R and 𝒞\mathcal C, and pruning results with their set UU.