The Setting
Let be a relation on a finite set . A pair in conflicts with a pair in when and .✦ Take two families and of pairs in and look at the conflicts of a member of with a member of . 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 and of pairs in are conflict-free when no member of conflicts with a member of .✦
The sets and of two families and of pairs in are the subsets of formed by the points , respectively , of the conflicts of a member of with a member of : (1)✦ (2)✦
The left image and the right image of a family of pairs in are the families obtained from the members of by advancing the first, respectively the second, coordinate along an arc: (3)✦ (4)✦
A point of is covered by two families and of pairs when it lies in .✦ For two further families and , the uncovered part of is the set of the points of that and do not cover.✦
The Claim
Theorem 1. Let be a relation on a finite set , and let and be families of pairs in , with sets and as in (1) and (2). Then there are subfamilies and such that and are conflict-free, every member of that conflicts with no member of lies in , every member of with which no member of conflicts lies in , and (5)✦
What Is Checked
The claim is stated for every relation on a finite set and every two families and of pairs in , over the conflict of two pairs, conflict-free families, the sets and of (1) and (2), the left and right images (3) and (4) with the points they cover, and the uncovered part of .