The Setting
Let be the finite vertex set of a digraph, with for an arc. The proof of Proposition 4.1 is an extremal argument about two families and of pairs in ; this page states its steps.
Lay out as a square array, the pair in row and column . The left image of a family of pairs is the family of the pairs reached from a pair of by one move along an arc within its column✦, and the right image is the same within its row: (1)✦ with and . The column of a family at a vertex is the set ✦, and the row of a family at a vertex is the set ✦.
Conditions on the Digraph
The image of a set of vertices is the set (2)✦ which may meet ; we write . A set of vertices is proper when .
A digraph on is oriented when it has no loop and no pair of opposite arcs and ✦, and has positive indegree when every vertex has an in-neighbor✦. A digraph on has strict growth when every nonempty proper set of vertices satisfies (3)✦
Admissible Pairs and the Objective
A pair conflicts with a pair when and .✦ Two families and are conflict-free when no pair of conflicts with a pair of ✦, and the points and of the conflicts between them form the sets (4) A pair of families is compatible when and are conflict-free.✦ The diagonal of is the family , the main diagonal of the array✦, and a pair of families is admissible when it is compatible and both and contain ✦.
A pair in is covered by two families and when it lies in , and uncovered otherwise.✦ The number of pairs uncovered by and is (5)✦ and the objective of is , where and ✦.
New Families and Pruning
The new families of a pair are (6)
A pruning result of two families and is a pair of conflict-free families with and such that contains every pair of that conflicts with no pair of , contains every pair of with which no pair of conflicts, and (7)✦ where is the set of the points of uncovered by and .
The Claim
Theorem 1. Let be the finite vertex set of a digraph, let be a pair of families of pairs in , and let and be its new families.
If the digraph is oriented, then (8)✦ If is compatible, contains and the digraph has positive indegree, then (9)✦ If is compatible, contains and the digraph has positive indegree, then (10)✦
If is nonempty, the digraph has strict growth and every column of is nonempty and proper, then (11)✦ If is nonempty, the digraph has strict growth and every row of is nonempty and proper, then (12)✦
If is admissible and the digraph has positive indegree and strict growth, then (13)✦ If is compatible and contains , then (14)✦ and if is compatible and contains , then (15)✦ If contains , then (16)✦ and if contains , then (17)✦ With no further hypothesis, (18)✦
If is admissible and is a pruning result of and , then (19)✦ If is a pruning result of any two families and with and , then (20)✦
If some pair of families has a given property, admissibility for instance, then there is a pair with the property such that every pair with the property has (21)✦
What Is Checked
The claims (8) to (21) are stated over a digraph on a finite set with its image and the conditions of being oriented, of positive indegree and of strict growth, and over families of pairs in with their left and right images, columns and rows, the diagonal, conflicts, conflict-free families and the sets and , compatible and admissible pairs, covered and uncovered pairs, the number and the objective , the new families and , and pruning results with their set .