The Setting
Let be a relation on a finite set , the arc relation of a digraph on in which loops are allowed. The points of form a square array, the point in row and column , and a family of pairs in is a set of points of the array. This item defines when and are compatible and when admissible, the number of points that neither family reaches, the objective built from that number and the sizes of and , and two new families formed from them.
Coordinate Images and Conflicts
The left image of a family of pairs in is the family of the pairs obtained from a pair of by advancing its first coordinate along an arc, and its right image is the family obtained in the same way by advancing the second coordinate: (1)✦ (2)✦ We write and .
A point of is covered by when it lies in , and by when it lies in . A pair in conflicts with a pair when and .✦
The Claim
Definition 1. Let be a relation on a finite set , and let and be families of pairs in . The families and are compatible, or conflict-free, when no pair of conflicts with a pair of : (3)✦
The diagonal of is the family (4)✦ and and are admissible when they are compatible and both contain the diagonal: (5)✦
For , the column of at and the row of at are the subsets of (6)✦ (7)✦
The uncovered points of and are the points of covered by neither family, (8)✦ and is their number.✦ The objective of and is the natural number (9)✦
From and from two new families are formed, the left candidate family and the right candidate family : (10)✦ (11)✦
What Is Checked
The definitions (3) to (11) are stated over an arbitrary relation on a finite set and two families and of pairs in , through the images (1) and (2) and the conflict of two pairs.
About these constructions the library proves one identity: when and are compatible, (12)✦