OctoInformBeta

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

Conflicts, the sets Z and H, and covered points: Pairs (p,j)(p, j), (i,s)(i, s) conflict when p→ip \to i and s→js \to j; a pruning leaves none, deleting at most |H||H| pairs plus one per uncovered point of ZZ

Conflicting pairs, covered points and what a pruning must achieve.

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, and let ℛ\mathcal{R} and 𝒞\mathcal{C} be families of pairs in X×XX \times X. A pair of ℛ\mathcal{R} advances its first coordinate along an arc, a pair of 𝒞\mathcal{C} advances its second, and a pair of one family may conflict with a pair of the other. Pruning the two families means deleting pairs from both so that no conflict is left between them; the question is how few deletions suffice.

The library defines conflicts and covered points, and states, for two given families and for every two families, what a pruning must achieve.

Conflicts and Covered Points

A pair (p,j)(p, j) of X×XX \times X conflicts with a pair (i,s)(i, s) of X×XX \times X when p→iands→j.p \to i \quad\text{and}\quad s \to j.(1)✦ Two 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 set ZZ of ℛ\mathcal{R} and 𝒞\mathcal{C} is the subset of X×XX \times X of the points (i,j)(i, j) of their conflicts, and the set HH of ℛ\mathcal{R} and 𝒞\mathcal{C} is the subset of X×XX \times X of the points (p,s)(p, s) of their conflicts: Z={(i,j):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some p,s},Z = \{(i, j) : (p, j) \in \mathcal{R} \text{ conflicts with } (i, s) \in \mathcal{C} \text{ for some } p, s\},(2)✦ H={(p,s):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some i,j}.H = \{(p, s) : (p, j) \in \mathcal{R} \text{ conflicts with } (i, s) \in \mathcal{C} \text{ for some } i, j\}.(3)✦

A pair aa of X×XX \times X covers a point (i,j)(i, j) of X×XX \times X from the left when a=(p,j) for some p∈X with p→i,a = (p, j) \text{ for some } p \in X \text{ with } p \to i,(4)✦ and from the right when a=(i,s) for some s∈X with s→j.a = (i, s) \text{ for some } s \in X \text{ with } s \to j.(5)✦

The left image F1ℛF_1\mathcal{R} of a family ℛ\mathcal{R} is the set of points that some pair of ℛ\mathcal{R} covers from the left✦, and the right image F2𝒞F_2\mathcal{C} of a family 𝒞\mathcal{C} is the set of points that some pair of 𝒞\mathcal{C} covers from the right.✦ A point zz of X×XX \times X is covered by the families ℛ\mathcal{R} and 𝒞\mathcal{C} when z∈F1ℛ∪F2𝒞.z \in F_1\mathcal{R} \cup F_2\mathcal{C}.(6)✦

For two further families ℛ′\mathcal{R}' and 𝒞′\mathcal{C}' of pairs in X×XX \times X, the uncovered part of ZZ is the set UU of the points of ZZ that ℛ′\mathcal{R}' and 𝒞′\mathcal{C}' do not cover: U=Z\(F1ℛ′∪F2𝒞′).U = Z \setminus (F_1\mathcal{R}' \cup F_2\mathcal{C}').(7)✦

The Claim

Definition 1. Let ℛ\mathcal{R} and 𝒞\mathcal{C} be families of pairs in X×XX \times X, with the set HH of (3). A pruning of ℛ\mathcal{R} and 𝒞\mathcal{C} is a pair of families ℛ′⊆ℛ\mathcal{R}' \subseteq \mathcal{R} and 𝒞′⊆𝒞\mathcal{C}' \subseteq \mathcal{C} such that ℛ′\mathcal{R}' and 𝒞′\mathcal{C}' are conflict-free, every pair of ℛ\mathcal{R} that conflicts with no pair of 𝒞\mathcal{C} lies in ℛ′\mathcal{R}', every pair of 𝒞\mathcal{C} that conflicts with no pair of ℛ\mathcal{R} lies in 𝒞′\mathcal{C}', and |ℛ\ℛ′|+|𝒞\𝒞′|≤|H|+|U|,|\mathcal{R} \setminus \mathcal{R}'| + |\mathcal{C} \setminus \mathcal{C}'| \le |H| + |U|,(8)✦ where UU is the set of (7). A relation →\to on a finite set XX has the pruning property when every two families of pairs in X×X have a pruning.\text{every two families of pairs in } X \times X \text{ have a pruning.}(9)✦

What Is Checked

The definitions are stated over a relation →\to on a finite set XX and families ℛ\mathcal{R}, 𝒞\mathcal{C}, ℛ′\mathcal{R}', 𝒞′\mathcal{C}' of pairs in X×XX \times X; a pruning (8) is stated in terms of conflicts (1), the sets ZZ and HH of (2) and (3), and the uncovered part (7) of ZZ.

For any two families ℛ\mathcal{R} and 𝒞\mathcal{C}, the library proves Z=F1ℛ∩F2𝒞,Z = F_1\mathcal{R} \cap F_2\mathcal{C},(10)✦ and that ℛ\mathcal{R} and 𝒞\mathcal{C} are conflict-free if and only if F1ℛ∩F2𝒞=∅.F_1\mathcal{R} \cap F_2\mathcal{C} = \emptyset.(11)✦