OctoInformBeta

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

Proposition 4.1: On a nonempty finite vertex set, some nonempty proper set SS of vertices has |S|+|F2(S)|≥2|F(S)||S| + |F^2(S)| \ge 2|F(S)|

Pruning excludes strict growth in oriented graphs of positive indegree.

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 DD be a digraph on a finite vertex set VV, with arcs written u→wu \to w. An oriented graph is a digraph with no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦ A digraph DD on VV has positive indegree when every vertex vv has an in-neighbor, a vertex uu with u→vu \to v.✦

The image F(S)F(S) of a set SS of vertices of DD is the set of vertices that receive an arc from a vertex of SS, F(S)={y∈V:x→y for some x∈S},F(S) = \{\, y \in V : x \to y \text{ for some } x \in S \,\},(1)✦ and F2(S)=F(F(S))F^2(S) = F(F(S)). The image may meet SS itself.

A set SS of vertices is proper when S≠VS \neq V. A digraph DD on VV 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)|.(2)✦

The question is whether a nonempty finite oriented graph with positive indegree can have strict growth. The library takes it up under one further hypothesis on the arcs of DD, the pruning statement, which concerns finite families of pairs of vertices and the conflicts between them.

Conflicts and Pruning

Let →\to be a relation on a finite set XX. A pair (p,j)(p, j) in X×XX \times X conflicts with a pair (i,s)(i, s) in X×XX \times X when p→ip \to i and s→js \to j.✦ Two finite families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX \times X are conflict-free when no pair of ℛ\mathcal R conflicts with a pair of 𝒞\mathcal C.✦

The point sets ZZ and HH of two finite families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX \times X are the sets of the points (i,j)(i, j) and (p,s)(p, s) of their conflicts, 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 &= \{\, (i, j) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } p, s \,\},\\ H &= \{\, (p, s) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } i, j \,\}. \end{aligned}(3)

The left image F1ℛF_1\mathcal R of a finite family ℛ\mathcal R of pairs in X×XX \times X is the set of pairs obtained by advancing the first coordinate of a pair of ℛ\mathcal R along an arc✦, and the right image F2𝒞F_2\mathcal C of a finite family 𝒞\mathcal C is the set obtained by advancing the second, F1ℛ={(i,j):p→i for some (p,j)∈ℛ},F2𝒞={(i,j):s→j for some (i,s)∈𝒞}.F_1\mathcal R = \{\, (i, j) : p \to i \text{ for some } (p, j) \in \mathcal R \,\}, \qquad F_2\mathcal C = \{\, (i, j) : s \to j \text{ for some } (i, s) \in \mathcal C \,\}.(4)✦ A pair in X×XX \times X is covered by ℛ\mathcal R and 𝒞\mathcal C when it lies in F1ℛ∪F2𝒞F_1\mathcal R \cup F_2\mathcal C.✦ For two further finite families ℛ′\mathcal R' and 𝒞′\mathcal C', the uncovered part of ZZ is the set Z\(F1ℛ′∪F2𝒞′)Z \setminus (F_1\mathcal R' \cup F_2\mathcal C') of the points of ZZ that ℛ′\mathcal R' and 𝒞′\mathcal C' do not cover.✦

A pruning result for finite families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX \times X consists of two finite families ℛ′⊆ℛ\mathcal R' \subseteq \mathcal R and 𝒞′⊆𝒞\mathcal C' \subseteq \mathcal C that are conflict-free, that keep every pair of ℛ\mathcal R conflicting with no pair of 𝒞\mathcal C and every pair of 𝒞\mathcal C with which no pair of ℛ\mathcal R conflicts, and that satisfy |ℛ\ℛ′|+|𝒞\𝒞′|≤|H|+|Z\(F1ℛ′∪F2𝒞′)|.|\mathcal R \setminus \mathcal R'| + |\mathcal C \setminus \mathcal C'| \le |H| + |Z \setminus (F_1\mathcal R' \cup F_2\mathcal C')|.(5)✦ The pruning statement for →\to is the assertion that any two finite families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX \times X have a pruning result.✦

The Claim

Theorem 1. Let DD be an oriented graph with positive indegree on a nonempty finite vertex set VV, and suppose the pruning statement holds for the arcs of DD, as a relation on X=VX = V. Then some nonempty proper set SS of vertices of DD satisfies |S|+|F2(S)|≥2|F(S)|.|S| + |F^2(S)| \ge 2\,|F(S)|.(6)✦

In the paper, the result reads: there is no nonempty finite oriented graph in which every vertex has an in-neighbor and every nonempty proper set SS of vertices satisfies |S|+|F2(S)|<2|F(S)||S| + |F^2(S)| < 2|F(S)|.

What Is Checked

The claim is stated over oriented graphs with positive indegree on a nonempty finite vertex set, the image FF of (1) and strict growth (2), and the pruning statement with what it is built from: conflicts and conflict-free families, the point sets ZZ and HH, the images F1F_1 and F2F_2, covered pairs, the uncovered part of ZZ and pruning results.