Proposition 4.13 -- mconvex_induces_submodular
ProvedDiscreteConvex.MConvexSetsB.mconvex_induces_submodularcombinatoricsdiscrete-convex-analysisdiscrete-geometry
Proposition 4.13 (p.108-109), Eq. (4.25). For an M-convex set , define . Then (1) , and (2) : the convex hull of is exactly the base polyhedron of the induced submodular function .
Formalization Note. As in Theorem 4.12, the book's "" in part (2) denotes the convex hull (the surrounding text calls the polyhedral description of the M-convex polyhedron, i.e. the convex hull of ), formalized as convexHull ℝ (IntEmbed B).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.108-109, Proposition 4.13, Eq. (4.25).)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexSetsB_ExchangeAxiomB import Definitions.Def_DiscreteConvex_MConvexSetsB_InducedRho import Definitions.Def_DiscreteConvex_MConvexSetsB_SubmodularSetFunction import Definitions.Def_DiscreteConvex_MConvexSetsB_IsIntegerValued import Definitions.Def_DiscreteConvex_MConvexSetsB_IntEmbed import Definitions.Def_DiscreteConvex_MConvexSetsB_BasePolyhedron
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.108-109, Proposition 4.13, in `DiscreteConvex.MConvexSetsB`.
-/
namespace DiscreteConvex.MConvexSetsB
/-- Proposition 4.13 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.108-109). See the item's
`natural_language_statement` for the full statement. -/
theorem mconvex_induces_submodular {V : Type*} [Fintype V] [DecidableEq V] (B : Set (V → ℤ))
(hExc : ExchangeAxiomB B) (hBne : B.Nonempty) :
SubmodularSetFunction (InducedRho B) ∧ IsIntegerValued (InducedRho B) ∧
convexHull ℝ (IntEmbed B) = BasePolyhedron (InducedRho B) := by sorry
end DiscreteConvex.MConvexSetsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.108-109, Proposition 4.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.