Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, pp. 348–349 — h^≺(U) = f(U) for every lower ideal U of ≺, and h^≺ ∈ B_f

Proved
SchrijverSFM.Alg.greedy_mem_baseB

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

base-polytopegreedy-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function

Let V={0,…,n−1}V = \{0, \dots, n-1\}V={0,…,n−1}, let fff be a submodular real function on the subsets of VVV with f(∅)=0f(\emptyset) = 0f(∅)=0, and let ≺\prec≺ be a total order on VVV with greedy vector h≺(v)=f(v≺∪{v})−f(v≺)h^\prec(v) = f(v_\prec \cup \{v\}) - f(v_\prec)h≺(v)=f(v≺​∪{v})−f(v≺​), where v≺={u∣u≺v}v_\prec = \{u \mid u \prec v\}v≺​={u∣u≺v}. Then

  1. h≺(U)=f(U)h^\prec(U) = f(U)h≺(U)=f(U) for every lower ideal UUU of ≺\prec≺ (a set with u∈U, w≺u⇒w∈Uu \in U,\ w \prec u \Rightarrow w \in Uu∈U, w≺u⇒w∈U), where h≺(U)=∑v∈Uh≺(v)h^\prec(U) = \sum_{v \in U} h^\prec(v)h≺(U)=∑v∈U​h≺(v);
  2. h≺h^\prech≺ belongs to the base polytope:
h≺(U)≤f(U)  for all U⊆V,h≺(V)=f(V).h^\prec(U) \le f(U) \ \text{ for all } U \subseteq V, \qquad h^\prec(V) = f(V).h≺(U)≤f(U)  for all U⊆V,h≺(V)=f(V).

Every greedy vector is therefore a point of BfB_fBf​, so every convex combination of greedy vectors, which is how the algorithm stores its current point, lies in BfB_fBf​. The identity on lower ideals is what makes the Case 1 set a minimizer.

Formalization Note A total order is a permutation σ\sigmaσ of Fin n read as a position map (u≺vu \prec vu≺v iff σ(u)<σ(v)\sigma(u) < \sigma(v)σ(u)<σ(v)).

Preamble
import Mathlib
import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg

open NonmonotoneSubmod.Shared

theorem greedy_mem_baseB {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f)
    (hf0 : f ∅ = 0) (σ : Equiv.Perm (Fin n)) :
    (∀ U : Finset (Fin n), IsLowerIdeal σ U → xsum (greedy f σ) U = f U) ∧
      greedy f σ ∈ baseB f := by sorry
end SchrijverSFM.Alg
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 348 (§2, sentence after display (6)) and pp. 348–349 (§2, last paragraph)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me