Display (24), Β§6, p. 354 β f(Y) + c(Y) β₯ f(X) + c(X) for X β Y in π
ProvedSchrijverSFM.Ring.f_add_c_monotonemonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-familysubmodular-functionsubmodular-minimization
Let be a finite set and a ring family on with and for all ( the smallest set of containing ). Let be submodular on , let as in (23), and . Then for all with ,
So is monotone on . This is the inequality used in the last step of (27), and it is where the weights earn their place in the definition of .
Formalization Note The hypothesis is necessary: with , (so ), , and (values off ), one gets and .
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem f_add_c_monotone {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (hempty : β
β C) (huniv : Finset.univ β C)
(hM : β u v : V, u β v β M C u β M C v) (f : Finset V β β) (hf : SubmodularOn C f) :
β X β C, β Y β C, X β Y β f X + csum C f X β€ f Y + csum C f Y := 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 (24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.