OctoInformBeta

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

Lemma 3.1: Members without conflicts are kept, and the deletions number at most |H||H| plus the points of ZZ that the pruned families leave uncovered

Two families of pairs can be pruned free of conflicts.

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. 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.✦ Take two families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX\times X and look at the conflicts of a member of ℛ\mathcal R with a member of 𝒞\mathcal C. Deleting members from the two families removes conflicts, and the question is how few deletions suffice to remove all of them, if every member without a conflict is to stay. The pruning lemma, Lemma 3.1 of OpenAI’s proof of Seymour’s second-neighborhood conjecture, answers it.

Conflicts, Images and Coverage

Families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX\times X are conflict-free when no member of ℛ\mathcal R conflicts with a member of 𝒞\mathcal C.✦

The sets ZZ and HH of two families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX\times X are the subsets of X×XX\times X formed by the points (i,j)(i,j), respectively (p,s)(p,s), of the conflicts of a member (p,j)(p,j) of ℛ\mathcal R with a member (i,s)(i,s) of 𝒞\mathcal C: Z={(i,j):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some p,s∈X},Z=\{(i,j) : (p,j)\in\mathcal R \text{ conflicts with } (i,s)\in\mathcal C \text{ for some } p,s\in X\},(1)✦ H={(p,s):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some i,j∈X}.H=\{(p,s) : (p,j)\in\mathcal R \text{ conflicts with } (i,s)\in\mathcal C \text{ for some } i,j\in X\}.(2)✦

The left image F1SF_1S and the right image F2SF_2S of a family SS of pairs in X×XX\times X are the families obtained from the members of SS by advancing the first, respectively the second, coordinate along an arc: F1S={(i,j):(p,j)∈S and p→i for some p∈X},F_1S=\{(i,j) : (p,j)\in S \text{ and } p\to i \text{ for some } p\in X\},(3)✦ F2S={(i,j):(i,s)∈S and s→j for some s∈X}.F_2S=\{(i,j) : (i,s)\in S \text{ and } s\to j \text{ for some } s\in X\}.(4)✦

A point of X×XX\times X is covered by two families ℛ\mathcal R and 𝒞\mathcal C of pairs when it lies in F1ℛ∪F2𝒞F_1\mathcal R\cup F_2\mathcal C.✦ For two further 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.✦

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, with sets ZZ and HH as in (1) and (2). Then there are subfamilies ℛ′⊆ℛ\mathcal R'\subseteq\mathcal R and 𝒞′⊆𝒞\mathcal C'\subseteq\mathcal C such that ℛ′\mathcal R' and 𝒞′\mathcal C' are conflict-free, every member of ℛ\mathcal R that conflicts with no member of 𝒞\mathcal C lies in ℛ′\mathcal R', every member of 𝒞\mathcal C with which no member of ℛ\mathcal R conflicts lies in 𝒞′\mathcal C', and |ℛ\ℛ′|+|𝒞\𝒞′|≤|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)✦

What Is Checked

The claim is stated for every relation →\to on a finite set XX and every two families ℛ\mathcal R and 𝒞\mathcal C of pairs in X×XX\times X, over the conflict of two pairs, conflict-free families, the sets ZZ and HH of (1) and (2), the left and right images (3) and (4) with the points they cover, and the uncovered part of ZZ.