Corollary to Lemma 4 — expected size from double coverage
ProvedKVVMatching.Ranking.corollary_lemma_4bipartite-matchingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
On an upper-triangular adjacency matrix with unit diagonal, let be the matching produced by RANKING in the rows-arrive picture, with uniformly random row order. Let be the indices whose row and column are both matched. Then
The assertion applies to RANKING's output itself; its coverage property follows from the algorithm and the diagonal condition. The expectation is over all row orders.
Preamble
import Definitions.Def_KVVMatching_Ranking_Algorithms
Formal statement
namespace KVVMatching.Ranking
/-- Corollary to Lemma 4, p. 354: expected matching cardinality in terms of
indices whose row and column are both covered. -/
theorem corollary_lemma_4 {n : ℕ} (adj : Fin n → Fin n → Prop)
(hdiag : ∀ i, adj i i)
(hupper : ∀ i j, adj i j → i ≤ j) :
rowRankingExpectation adj = (n : ℝ) / 2 +
(1 / 2 : ℝ) * ((n.factorial : ℝ)⁻¹ *
∑ σ : Equiv.Perm (Fin n),
((doubleCovered (rowRankingMatching adj σ)).card : ℝ)) := by sorry
end KVVMatching.Ranking
Source
Karp, Vazirani, Vazirani, An Optimal Algorithm for On-line Bipartite Matching, STOC 1990, p. 354, Corollary following Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.