ยง6, p. 353 โ L_v is the largest set in ๐ not containing v, the union of the M_u not containing v, and L_v โช {v} โ ๐
ProvedSchrijverSFM.Ring.L_speclower-idealp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-familysubmodular-minimization
Let be a finite set and a ring family on with and for , where is the smallest set of containing . For let be the union of all sets of not containing . Then:
- and ;
- every with satisfies , so is the largest set in not containing ;
- is the union of those not containing :
- .
Item 4 is what makes the weight of display (23) depend only on the values of on .
Formalization Note Items 1โ3 are the parenthetical description of on p. 353; item 4 is implicit in (23), which evaluates at , and it needs the hypothesis .
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem L_spec {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) (v : V) :
L C v โ C โง v โ L C v โง (โ Y โ C, v โ Y โ Y โ L C v) โง
L C v = (Finset.univ.filter (fun u => v โ M C u)).biUnion (fun u => M C u) โง
insert v (L C v) โ C := 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. 353, ยง6, sentence defining L_v and display (23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.