Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — rank-sum lower bound on the labels of cheap bases

Open
GroupLabeledMatroid.Proximity.Supplement.rank_sum_label_count

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

group-labelingmatroidsoptimizationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let M=(E,I)M=(E,\mathcal I)M=(E,I) be a matroid on a finite ground set EEE with rank function rrr, let GGG be an abelian group (possibly infinite), ℓ:E→G\ell:E\to Gℓ:E→G a labeling and c:E→Rc:E\to\mathbb Rc:E→R a cost function. For X⊆EX\subseteq EX⊆E write ℓ(X)=∑e∈Xℓ(e)\ell(X)=\sum_{e\in X}\ell(e)ℓ(X)=∑e∈X​ℓ(e) and c(X)=∑e∈Xc(e)c(X)=\sum_{e\in X}c(e)c(X)=∑e∈X​c(e), and for θ∈R\theta\in\mathbb Rθ∈R let

ℓ≤θ(M)={ℓ(D):D is a base of M with c(D)≤θ}.\ell_{\le\theta}(M)=\{\ell(D): D \text{ is a base of } M \text{ with } c(D)\le\theta\}.ℓ≤θ​(M)={ℓ(D):D is a base of M with c(D)≤θ}.

Suppose BBB is the unique min-cost ℓ(B)\ell(B)ℓ(B)-base of MMM: BBB is a base, and every base DDD with ℓ(D)=ℓ(B)\ell(D)=\ell(B)ℓ(D)=ℓ(B) satisfies c(B)≤c(D)c(B)\le c(D)c(B)≤c(D), with equality only for D=BD=BD=B. For h∈Gh\in Gh∈G let

Rh={e∈E: ℓ(e)=h and c(e)≤min⁡b∈Bc(b)}.R_h=\{e\in E:\ \ell(e)=h \text{ and } c(e)\le \min_{b\in B}c(b)\}.Rh​={e∈E: ℓ(e)=h and c(e)≤b∈Bmin​c(b)}.

Then

∣ℓ≤c(B)(M)∣ ≥ ∑h∈Gr(Rh)−r(E)+1.|\ell_{\le c(B)}(M)|\ \ge\ \sum_{h\in G} r(R_h)-r(E)+1.∣ℓ≤c(B)​(M)∣ ≥ h∈G∑​r(Rh​)−r(E)+1.

This is a weighted analogue, valid for every abelian group, of the Schrijver–Seymour bound for Zp\mathbb Z_pZp​: under the uniqueness assumption on BBB it bounds from below the number of distinct labels of bases of cost at most c(B)c(B)c(B) by the rank sum of the cost-filtered color classes. Taking c≡0c\equiv 0c≡0 gives the unweighted Corollary 13.

Formalization Note MMM is a Mathlib matroid on a finite type with ground M.E; r(E)r(E)r(E) is the rank of the ground. Only labels occurring on the ground have nonempty RhR_hRh​, so the sum over GGG is the finite sum over ℓ[E]\ell[E]ℓ[E]. The minimum over BBB is written as "c(e)≤c(x)c(e)\le c(x)c(e)≤c(x) for all x∈Bx\in Bx∈B", which for rank 000 (B=∅B=\emptysetB=∅) gives Rh=EhR_h=E_hRh​=Eh​; every set has rank 000 then, so the statement is the paper's under any reading of min⁡∅\min\emptysetmin∅. The comparison is in Z\mathbb ZZ, 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
Preamble
import Definitions.Def_GroupLabeledMatroid_Proximity_LabelModel
Formal statement
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
Source
Siyue Liu, Taihei Oki, Chao Xu, Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases, STOC 2027 submission #554 (October 2026), p. 3, Theorem 4 (restated p. 8, proof pp. 6–8); notation ℓ≤θ(M) p. 6

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me