Lemma 12 — filtered color-rank drop under contraction of
OpenGroupLabeledMatroid.Proximity.Supplement.filtered_rank_dropLet be a matroid on a finite ground set , an arbitrary abelian group, a labeling and a cost function. For write and . Suppose is the unique min-cost -base of : is a base, and every base with satisfies , with equality only for . Let be the rank and enumerate with .
For put , with rank function , and , where . For put
and set . Then for every and every ,
Contracting the next base element thus lowers the rank of each cost-filtered color class by at most one, and only for the colors in . Combined with Corollary 11 this turns the count of labels into the rank sum of Theorem 4.
Formalization Note The ground set is the ground M.E of a Mathlib matroid on a finite type; subsets are Finsets and ranks are natural numbers. The Lean stage index is the source's , so i : Fin r stands for , and the Lean stage is the terminal stage , where stageR is the whole remaining color class. The integer difference inequality is written additively in .
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; reason: every finite matroid admits this representation and finite ranks have no infinite case
- encoding: indices i ∈ [r] and terminal stage r+1 → i : Fin r represents source i+1 and natural stage k represents source k+1; H_i filtered over labels occurring on the ground; reason: stage arithmetic is a shift; a label not occurring on the ground has empty R_h^i, which cannot span the nonloop b_i, so no member of H_i is lost
- encoding: integer difference r_i(R_h^i) − r_{i+1}(R_h^{i+1}) ≤ 1{h ∈ H_i} → r_i(R_h^i) ≤ r_{i+1}(R_h^{i+1}) + 1{h ∈ H_i} in ℕ; reason: subtraction-free equivalent avoids truncated subtraction
import Definitions.Def_GroupLabeledMatroid_Proximity_ContractionFiltration
namespace GroupLabeledMatroid.Proximity.Supplement
open GroupLabeledMatroid.Proximity
theorem filtered_rank_drop {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) {r : ℕ} (hr : 0 < r)
(b : Fin r → E) (horder : IsCostOrder c B b) (i : Fin r) (h : G) :
rankOn (stageMinor M b i.val) (stageR M ℓ c b i.val h) ≤
rankOn (stageMinor M b (i.val + 1)) (stageR M ℓ c b (i.val + 1) h) +
(if h ∈ stageH M ℓ c b i then 1 else 0) := by sorry
end GroupLabeledMatroid.Proximity.Supplement