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
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {0, …, m−1}.
- Used by 5
- sSup_indep_le_sSup_multilinear_extensionThe best integral value max{f(S) : S independent in M} is at most the best fractional value max_{x∈P(M)} F(x), because every independent…
- perm_group_symmetrize_mem_matroid_polytopeFor a strongly symmetric instance, symmetrizing a point of the matroid polytope stays inside the matroid polytope.
- matroid_symmetry_gap_le_oneFor every strongly symmetric instance max{f(S) : S independent in M} with respect to a permutation group G, the best symmetrized…
- symmetry_gap_numerator_eq_sSup_fixedFor a strongly symmetric instance the numerator of the symmetry gap, sup_{x∈P(M)} F(x̄), equals the supremum of F over the points of the…
- symmetrize_image_matroid_polytope_eq_fixedFor a strongly symmetric instance, the image of the matroid polytope under symmetrization is exactly the set of points of the polytope…
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}