Lemma 3.1 (pruning two families of pairs): conflicts can be removed by deleting at most plus the number of uncovered points of members
OpenOAI.SeymourSecondNeighborhood.Pruning.lemma_3_1Let be a finite set with an arbitrary binary relation (no orientation or irreflexivity is assumed), and let be two families of ordered pairs, regarded as separate copies even where they agree. A left member and a right member conflict if and . Let
A point is covered by a member when , and by a member when . Then there are subfamilies and with no conflicts between them, such that every member of (resp. ) that conflicts with no member of (resp. ) is retained, and
This is Lemma 3.1 of the manuscript, its main new ingredient. The proof there builds a bipartite graph on and (conflicting members adjacent; each member adjacent to the opposite copy of every point of it covers), shows by a rank argument with generically chosen real coefficients (Lemma 3.2, lemma_3_2) that a maximum matching has at most edges, and takes a K\H{o}nig vertex cover of that size; deleting its original members gives the pruning. The statement is purely about finite relations and families of pairs; in the application (prop_4_1) its two cost terms are bounded by the numbers of uncovered points before and after pruning.
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
namespace OAI.SeymourSecondNeighborhood.Pruning
variable {X : Type*} [Fintype X] [DecidableEq X]
theorem lemma_3_1 (arrow : X → X → Prop) (R C : Finset (X × X)) :
∃ R' ⊆ R, ∃ C' ⊆ C,
(∀ l ∈ R', ∀ c ∈ C', ¬ Conflict arrow l c) ∧
(∀ l ∈ R, (∀ c ∈ C, ¬ Conflict arrow l c) → l ∈ R') ∧
(∀ c ∈ C, (∀ l ∈ R, ¬ Conflict arrow l c) → c ∈ C') ∧
(R \ R').card + (C \ C').card
≤ (pointsH arrow R C).card + (uncovered arrow R C R' C').card := by
sorry
end OAI.SeymourSecondNeighborhood.Pruning