Theorem 4 — rank-sum lower bound on the labels of cheap bases
OpenGroupLabeledMatroid.Proximity.Supplement.rank_sum_label_countLet be a matroid on a finite ground set with rank function , let be an abelian group (possibly infinite), a labeling and a cost function. For write and , and for let
Suppose is the unique min-cost -base of : is a base, and every base with satisfies , with equality only for . For let
Then
This is a weighted analogue, valid for every abelian group, of the Schrijver–Seymour bound for : under the uniqueness assumption on it bounds from below the number of distinct labels of bases of cost at most by the rank sum of the cost-filtered color classes. Taking gives the unweighted Corollary 13.
Formalization Note is a Mathlib matroid on a finite type with ground M.E; is the rank of the ground. Only labels occurring on the ground have nonempty , so the sum over is the finite sum over . The minimum over is written as " for all ", which for rank () gives ; every set has rank then, so the statement is the paper's under any reading of . The comparison is in , since the right-hand side can be negative.
Differences from the source:
- encoding: finite ground set E and subsets → Finset subsets of a finite ambient type with ground M.E and natural ranks cast to ℤ; reason: every finite matroid admits this representation; the inequality is compared in ℤ, so no truncation occurs
- encoding: sum over h ∈ G → sum over the labels occurring on the ground; reason: every other h has R_h = ∅ of rank 0, so the sums are equal, and the sum is finite even for infinite G
- encoding: c(e) ≤ min_{b∈B} c(b) → c(e) ≤ c(x) for every x ∈ B; reason: equivalent for nonempty B; for B = ∅ (rank 0) all ranks vanish, so both sides are unchanged
import Definitions.Def_GroupLabeledMatroid_Proximity_LabelModel
namespace GroupLabeledMatroid.Proximity.Supplement
open GroupLabeledMatroid.Proximity
theorem rank_sum_label_count {E G : Type*} [Fintype E] [DecidableEq E] [AddCommGroup G] [DecidableEq G]
(M : Matroid E) (ℓ : E → G) (c : E → ℝ) (B : Finset E)
(hB : IsUniqueLabelMinimum M ℓ c B) :
((labelsUnder M ℓ c (costSum c B)).card : ℤ) ≥
(∑ h ∈ (ground M).image ℓ,
(rankOn M ((colorClass M ℓ h).filter (fun e => ∀ x ∈ B, c e ≤ c x)) : ℤ)) -
(rankOn M (ground M) : ℤ) + 1 := by sorry
end GroupLabeledMatroid.Proximity.Supplement