Display (25), §6, p. 354 — f(X) ≤ f(Y) + c(v) when Y = X ∪ {v}, v ∉ X, X, Y ∈ 𝒞
ProvedSchrijverSFM.Ring.step_le_add_cp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-familysubmodular-functionsubmodular-minimization
Let be a finite set, a ring family on , and submodular on . Let be the union of the sets of not containing and as in (23). If , and , then
This one-element step is display (25); chaining it along a maximal chain from to in gives the monotonicity (24) of on .
Formalization Note The paper's standing normalization (, ) is not needed for this step and is not assumed, so the statement is slightly more general than the page.
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem step_le_add_c {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (f : Finset V → ℝ) (hf : SubmodularOn C f)
(X Y : Finset V) (hX : X ∈ C) (hY : Y ∈ C) (v : V) (hv : v ∉ X) (hXY : Y = insert v X) :
f X ≤ f Y + cw C f v := by sorry
end SchrijverSFM.Ring
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 354, §6, display (25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.