Matching bound for the augmented bipartite graph of two families of pairs: every matching of has at most edges
OpenOAI.SeymourSecondNeighborhood.Pruning.matching_boundLet be a finite set with an arbitrary binary relation , and let be two families of ordered pairs. A left member and a right member conflict if and ; a conflict contributes the point to and the point to . A member covers a point when , and a member covers when . The augmented bipartite graph has left vertex set and right vertex set , where are two copies of ; its edges join each conflicting pair , each to the right copy of every point of it covers, and each to the left copy of every point of it covers (there are no edges between and ). The statement is that
where a matching is a set of edges with pairwise distinct left endpoints and pairwise distinct right endpoints. This is the core of Section 3 of the manuscript, where it is proved by a rank argument: with generic real coefficients attached to the arrows, four matrices satisfy , a maximum matching with the fewest member–member edges is encoded by , and , and Lemma 3.2 (Pruning.lemma_3_2, kernels at maximum support rank) controls the kernel vectors. Together with K\H{o}nig's theorem (Pruning.konig) it implies the pruning lemma Pruning.lemma_3_1, and hence (through prop_4_1, lemma_2_2 and lemma_2_3) Seymour's second-neighborhood conjecture. The bound is tight: for the complete loopless relation on points with one has .
Formalization note. Both sides of are encoded as (X × X) ⊕ (X × X): Sum.inl for members of (left) or (right), Sum.inr for the copies of points of . The hypothesis hM says every element of M is an edge of of one of the three kinds, and h₁, h₂ say M is a matching.
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
namespace OAI.SeymourSecondNeighborhood.Pruning
variable {X : Type*} [Fintype X] [DecidableEq X]
/-- **Matching bound in the augmented bipartite graph `Γ`.** The graph `Γ` has left vertex set
`R ⊔ Z` (members of `R`, and left copies `Sum.inr z` of the points `z ∈ Z = pointsZ arrow R C`)
and right vertex set `C ⊔ Z` (members of `C`, and right copies of the points of `Z`), encoded as
`(X × X) ⊕ (X × X)` on both sides. Its edges are
* the conflict edges `(inl l, inl c)` with `l ∈ R`, `c ∈ C`, `Conflict arrow l c`;
* the left-cover edges `(inl l, inr z)` with `l ∈ R`, `z ∈ Z`, `CoversL arrow l z`;
* the right-cover edges `(inr z, inl c)` with `z ∈ Z`, `c ∈ C`, `CoversR arrow c z`.
Every matching `M` of `Γ` (a set of edges of `Γ` on which both projections are injective) has at
most `|Z| + |H|` edges, where `H = pointsH arrow R C`. -/
theorem matching_bound (arrow : X → X → Prop) (R C : Finset (X × X))
(M : Finset (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X))))
(hM : ∀ e ∈ M,
(∃ l ∈ R, ∃ c ∈ C, e = (Sum.inl l, Sum.inl c) ∧ Conflict arrow l c) ∨
(∃ l ∈ R, ∃ z ∈ pointsZ arrow R C, e = (Sum.inl l, Sum.inr z) ∧ CoversL arrow l z) ∨
(∃ z ∈ pointsZ arrow R C, ∃ c ∈ C, e = (Sum.inr z, Sum.inl c) ∧ CoversR arrow c z))
(h₁ : Set.InjOn Prod.fst (M : Set (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X)))))
(h₂ : Set.InjOn Prod.snd (M : Set (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X))))) :
M.card ≤ (pointsZ arrow R C).card + (pointsH arrow R C).card := by
sorry
end OAI.SeymourSecondNeighborhood.Pruning