base_polytope_extreme_bases
def
The set of greedy bases of a set function f on Finset (Fin n) consists of the vectors generated by Edmonds' greedy algorithm over all permutations π of Fin n.
Statement
def base_polytope_extreme_bases {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ)- Defined in
- Edmonds 1970; Fujishige 1980
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Used by 1
- linopt_major_cycle_discards_corral_atomThe formal major-cycle relation can discard the previous atom even though the enlarged two-atom support is already a corral, for the base…
Read back from the Lean
Given an implicit natural number $n$ and a set function $f : \mathrm{Finset}(\mathrm{Fin}\ n) \to \mathbb{R}$, base_polytope_extreme_bases f is the set of all vectors $p : \mathrm{Fin}\ n \to \mathbb{R}$ for which there exists a permutation $\pi$ of $\mathrm{Fin}\ n$ such that for all $i : \mathrm{Fin}\ n$,
$$p(i) = f(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(j) \le \pi^{-1}(i)\}) - f(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(j) < \pi^{-1}(i)\}).$$
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 set of greedy bases (extreme points) of the base polytope of f. -/ def base_polytope_extreme_bases {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ) := { p | ∃ π : Equiv.Perm (Fin n), p = fun i => f (Finset.univ.filter (fun j => π.symm j ≤ π.symm i)) - f (Finset.univ.filter (fun j => π.symm j < π.symm i)) }