Theorem 5.7 -- L-convex sets are closed under intersection
ProvedDiscreteConvex.LConvexSets.lconvex_intersection_propertiesdiscrete-convex-analysisdiscrete-geometry
Theorem 5.7, parts (1) and (4) (p.125). For L-convex sets : (1) (convexity in intersection); (4) if is nonempty, it is again an L-convex set.
Formalization Note. The book's parts (2)-(3) additionally describe via a specific representation and characterize nonemptiness via absence of a negative cycle in the associated graph; these are not needed by Theorem 5.9's own statement (only by its proof) and are omitted from this milestone as a scope decision.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.125, Theorem 5.7.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSets_LConvexSet import Definitions.Def_DiscreteConvex_LConvexSets_ConvexClosureSet
Formal statement
namespace DiscreteConvex.LConvexSets
/-- Theorem 5.7, parts (1) and (4) (Murota, *Discrete Convex Analysis*, SIAM 2003, p.125). For
L-convex sets `D1, D2 ⊆ Zⱽ`: (1) `D̄1 ∩ D̄2 = (D1 ∩ D2)‾` (convexity in intersection); (4) if
`D1 ∩ D2` is nonempty, it is again an L-convex set. -/
theorem lconvex_intersection_properties {V : Type*} [Fintype V] [DecidableEq V]
(D1 D2 : Set (V → ℤ)) (hD1 : LConvexSet D1) (hD2 : LConvexSet D2) :
ConvexClosureSet D1 ∩ ConvexClosureSet D2 = ConvexClosureSet (D1 ∩ D2) ∧
((D1 ∩ D2).Nonempty → LConvexSet (D1 ∩ D2)) := by sorry
end DiscreteConvex.LConvexSets
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.125, Theorem 5.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.