Lemma 7 — circuit–base exchange
ProvedGroupLabeledMatroid.Proximity.circuit_base_exchangegroup-labelingmatroidsoptimizationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a base and a circuit of a finite matroid . For every there is an element such that
This is the circuit–base exchange fact used in the block counting lemmas.
Differences from the source:
- encoding: finite ground set E and finite subsets → Finset subsets of a finite ambient type with classical decidable equality, genuine Mathlib ground M.E, and finite natural ranks; reason: every finite source ground admits this representation; arbitrary subsets M.E support minors; finite rank conversion has no infinite case; classical equality imposes no restriction on the label group
Preamble
import Mathlib
Formal statement
namespace GroupLabeledMatroid.Proximity
theorem circuit_base_exchange {E : Type*} [Fintype E] [DecidableEq E]
(M : Matroid E) (B C : Finset E) (hB : M.IsBase (B : Set E))
(hC : M.IsCircuit (C : Set E)) (b : E) (hb : b ∈ B ∩ C) :
∃ a ∈ C \ B, M.IsBase ((insert a (B.erase b) : Finset E) : Set E) := by sorry
end GroupLabeledMatroid.Proximity
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. 5, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.