base_polytope_submodular
def
The base polytope B(f) of a set function f on Finset (Fin n) is the set of points x in ℝ^n satisfying ∑_{i ∈ S} x i ≤ f(S) for all subsets S and ∑_{i} x i = f(Finset.univ).
Statement
def base_polytope_submodular {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ)- Defined in
- Fujishige 1980; Schrijver "Combinatorial Optimization" Sec. 44.1
- Verified
- 11 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a natural number $n$ and a set function $f : \mathrm{Finset}(\mathrm{Fin}\ n) \to \mathbb{R}$, base_polytope_submodular f is defined as the set of vectors $x : \mathrm{Fin}\ n \to \mathbb{R}$ satisfying:
1. For every subset $S \subseteq \mathrm{Fin}\ n$, $\sum_{i \in S} x(i) \le f(S)$; and
2. The total sum over all coordinates $\sum_{i : \mathrm{Fin}\ n} x(i)$ equals $f(\mathrm{univ})$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The base polytope B(f) of a set function f on Finset (Fin n). -/ def base_polytope_submodular {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ) := { x | (∀ S : Finset (Fin n), ∑ i ∈ S, x i ≤ f S) ∧ ∑ i : Fin n, x i = f Finset.univ }