The Setting
Let be a relation on a finite set , written with arcs , and let and be families of pairs in . A pair of and a pair of conflict when and .β¦
The set is the set of the pairs , and the set of the pairs , for which some and conflict. A pair covers a pair from the left when β¦, and a pair covers a pair from the right when .β¦
When real numbers are placed on the arcs of and four matrices are built from them, how do vectors in the kernels of these matrices sit on the two pairs of a conflict? And how large is a matching of the bipartite graph whose edges are the conflicts and the covers, measured against ?
Coefficients and the Four Maps
Real coefficients , one number for each pair of points , of , are supported on when whenever .β¦
For real coefficients and , the real matrices , , and act on vectors , and by (1) (2) for , and .
Fibers and Locally Maximal Ranks
For a family of pairs in and a point of , the fiber of at is the set β¦, and the restriction of a vector to it is the vector with entries .β¦
For points and of and real coefficients , the fiber matrix is the real matrix with rows indexed by and columns by whose entry in row and column is .β¦
A real matrix with rows indexed by a set and columns by a set is supported on a set of positions when for every .β¦
Real coefficients have locally maximal ranks on and when, for every arc , every real matrix with rows indexed by and columns by that is supported on the local support of the arc satisfies (3)β¦
The Augmented Graph
The augmented bipartite graph has left side β¦ and right side β¦, with two disjoint copies of . A pair of is joined to a pair of when the two conflict, a pair of to a point of on the right when it covers the point from the left, and a point of on the left to a pair of when the pair covers the point from the right; no two points of are joined.β¦
The edges of between and form the cover graph with sides and : its edges are the positions of in (1) whose entry sits on an arc.β¦ The edges between and form the cover graph with sides and : its edges are the positions of , from (2), whose entry sits on an arc.β¦
For a matching of , its part is the set of its edges in β¦ and its part the set of its edges in .β¦
The Claim
Theorem 1. Let be a relation on a finite set and let and be families of pairs in .
(a) Let be real coefficients supported on , let be an arc, and let and . Then (4)β¦ and (5)β¦
(b) Let moreover have locally maximal ranks on and . If and conflict, then every and every satisfy (6)β¦
(c) Under the hypotheses of (b), if and conflict and some has , then every satisfies (7)β¦
(d) Under the hypotheses of (b), let and conflict for , and let and satisfy and for all and . Then (8)β¦
(e) If, in (d), is also supported on and for every , then (9)β¦
(f) Let be a maximum matching of and a maximum matching of . Let be distinct pairs of unmatched by and distinct pairs of unmatched by , with and in conflict for every . Then (10)β¦
(g) Let be a matching of whose parts and are maximum matchings of and . Then (11)β¦
What Is Checked
The claim is stated over a relation on a finite set , families and of pairs in with their conflicts, their covers and the sets and , real coefficients supported on with the maps , , and , the fiber matrices , the restrictions to fibers and the condition of locally maximal ranks, and the augmented graph with its cover graphs and and their matchings and maximum matchings.