Theorem 1 with Lemmas 3 and 5 — RANKING's n(1 − 1/e) − o(n) guarantee
ProvedKVVMatching.Ranking.ranking_guaranteeFor every , there is a threshold such that for every and every bipartite graph on boys and girls that contains a perfect matching, RANKING's expected matching size satisfies
Girls arrive in the fixed order ; each girl takes her highest-priority adjacent unmatched boy. The expectation is the uniform average over all rankings of boys. Because the graph is arbitrary, this also covers any preselected girl-arrival order by relabeling.
The paper writes the lower-order error as . Formally, the same works for every perfect-matchable graph of size , expressing the worst-case performance measure rather than a separate asymptotic statement for each graph. The claim is the RANKING guarantee obtained from the paper's Theorem 1 together with Lemmas 3 and 5.
import Definitions.Def_KVVMatching_Ranking_Algorithms import Definitions.Def_DiscreteConvex_IntegralConvexityB_IsPerfectMatchingBij
namespace KVVMatching.Ranking
/-- The RANKING guarantee drawn from Theorem 1 with Lemmas 3 and 5.
The asymptotic threshold is uniform over all graphs of a given size. -/
theorem ranking_guarantee (ε : ℝ) (hε : 0 < ε) :
∃ N : ℕ, ∀ (n : ℕ), N ≤ n → ∀ (adj : Fin n → Fin n → Prop),
(∃ τ : Fin n ≃ Fin n,
DiscreteConvex.IntegralConvexityB.IsPerfectMatchingBij
{p : Fin n × Fin n | adj p.1 p.2} τ) →
(1 - Real.exp (-1) - ε) * (n : ℝ) ≤ rankingExpectation adj := by sorry
end KVVMatching.Ranking
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.