AFTD Auto-Formalizing Theoretical Domains

matroid_polytope

def

The matroid polytope P(M): the convex hull of the indicator vectors of the independent sets of a matroid M on {0, …, m−1}.

Statement

def matroid_polytope {m : ℕ} (M : Matroid (Fin m)) : Set (Fin m → ℝ)
Defined in
arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Definition 2.2 (P(F) for a matroid constraint F)
Verified
07 Oct 2026
Axioms
none listed
Built on 1
Used by 5

Lean source view module on GitHub

/-- The matroid polytope `P(M) = conv{1_S : S independent in M}` of a matroid on `Fin m`. -/
def matroid_polytope {m : ℕ} (M : Matroid (Fin m)) : Set (Fin m → ℝ) :=
  convexHull ℝ {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S}
See it in the graphDiscuss this resultChallenge it