Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — filtered color-rank drop under contraction of bib_ibi​

Open
GroupLabeledMatroid.Proximity.Supplement.filtered_rank_drop

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, GGG an arbitrary abelian group, ℓ: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). 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. Let r≥1r\ge 1r≥1 be the rank and enumerate B={b1,…,br}B=\{b_1,\dots,b_r\}B={b1​,…,br​} with c(b1)≤⋯≤c(br)c(b_1)\le\dots\le c(b_r)c(b1​)≤⋯≤c(br​).

For i∈[r+1]i\in[r+1]i∈[r+1] put B<i={b1,…,bi−1}B_{<i}=\{b_1,\dots,b_{i-1}\}B<i​={b1​,…,bi−1​}, Mi=M/B<iM_i=M/B_{<i}Mi​=M/B<i​ with rank function rir_iri​, and Ehi=Eh∖B<iE_h^i=E_h\setminus B_{<i}Ehi​=Eh​∖B<i​, where Eh={e∈E:ℓ(e)=h}E_h=\{e\in E:\ell(e)=h\}Eh​={e∈E:ℓ(e)=h}. For i∈[r]i\in[r]i∈[r] put

Rhi={e∈Ehi:c(e)≤c(bi)},Hi={h∈G:bi∈clMi(Rhi)},R_h^i=\{e\in E_h^i : c(e)\le c(b_i)\},\qquad H_i=\{h\in G : b_i\in \mathrm{cl}_{M_i}(R_h^i)\},Rhi​={e∈Ehi​:c(e)≤c(bi​)},Hi​={h∈G:bi​∈clMi​​(Rhi​)},

and set Rhr+1=Ehr+1R_h^{r+1}=E_h^{r+1}Rhr+1​=Ehr+1​. Then for every i∈[r]i\in[r]i∈[r] and every h∈Gh\in Gh∈G,

ri(Rhi)−ri+1(Rhi+1)≤1{h∈Hi}.r_i(R_h^i)-r_{i+1}(R_h^{i+1})\le \mathbf 1\{h\in H_i\}.ri​(Rhi​)−ri+1​(Rhi+1​)≤1{h∈Hi​}.

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 HiH_iHi​. 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 kkk is the source's k+1k+1k+1, so i : Fin r stands for i+1∈[r]i+1\in[r]i+1∈[r], and the Lean stage rrr is the terminal stage r+1r+1r+1, where stageR is the whole remaining color class. The integer difference inequality is written additively in N\mathbb NN.

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
Preamble
import Definitions.Def_GroupLabeledMatroid_Proximity_ContractionFiltration
Formal statement
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
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. 8, Lemma 12; standing hypotheses and definitions of M_i, r_i, R_h^i, H_i pp. 6–7 (§3, §3.1)

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