Lemma 4 — matching size from doubly covered indices
ProvedKVVMatching.Ranking.lemma_4bipartite-matchingcombinatoricsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an upper-triangular adjacency matrix with unit diagonal, and let be a matching using its edges. Suppose that for each index , row or column is matched, possibly both. Write for the indices where both are matched. Then
This counting identity turns the analysis of matching size into an analysis of the indices covered on both sides. The disjunction in the hypothesis is inclusive.
Preamble
import Definitions.Def_KVVMatching_Ranking_Algorithms
Formal statement
namespace KVVMatching.Ranking
/-- Lemma 4, p. 354: counting the vertices covered by a matching. -/
theorem lemma_4 {n : ℕ} (adj : Fin n → Fin n → Prop)
(hdiag : ∀ i, adj i i)
(hupper : ∀ i j, adj i j → i ≤ j)
(M : Finset (Fin n × Fin n))
(hM : IsMatching M)
(hEdges : ∀ e ∈ M, adj e.1 e.2)
(hCover : ∀ i : Fin n, firstMatched M i ∨ secondMatched M i) :
(M.card : ℝ) = ((n : ℝ) + (doubleCovered M).card) / 2 := by sorry
end KVVMatching.Ranking
Source
Karp, Vazirani, Vazirani, An Optimal Algorithm for On-line Bipartite Matching, STOC 1990, p. 354, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.