ยง6, p. 353 โ ๐ is the collection of all lower ideals of some partial order on V
ProvedSchrijverSFM.Ring.lower_ideal_representationbirkhoff-representationlower-idealp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partial-orderring-family
Let be a finite set and a ring family of subsets of (closed under union and intersection) with and . For let be the smallest set of containing , and assume for all . Then there is a partial order on (reflexive, transitive, antisymmetric) whose lower ideals are exactly the sets of :
This is the representation Schrijver uses to describe a ring family completely by the sets , after the normalization , , .
Formalization Note The partial order is given as a relation r : V โ V โ Prop with its three axioms stated explicitly. The hypotheses are the paper's normalization "We can assume that , , and for all ", where (the smallest set of is empty) is โ
โ C.
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem lower_ideal_representation {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) :
โ r : V โ V โ Prop,
(โ v, r v v) โง (โ u v w, r u v โ r v w โ r u w) โง (โ u v, r u v โ r v u โ u = v) โง
โ X : Finset V, X โ C โ โ u v, r u v โ v โ X โ u โ X := 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, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.