Theorem 6.51 -- polyhedral_mnat_convex_supermodular
DisprovedDiscreteConvex.MConvexFunctionsD.polyhedral_mnat_convex_supermodularcombinatoricsdiscrete-convex-analysis
Theorem 6.51 (p.163). A polyhedral M-convex function is supermodular: for all .
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.163, Theorem 6.51.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexFunctionsD_MNaturalConvexR
Formal statement
namespace DiscreteConvex.MConvexFunctionsD
open scoped Pointwise
open Classical
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 6.51 (p.182). -/
theorem polyhedral_mnat_convex_supermodular (f : (V → ℝ) → WithTop ℝ) (hf : MNaturalConvexR f) :
∀ x y : V → ℝ, f x + f y ≤ f (fun v => max (x v) (y v)) + f (fun v => min (x v) (y v)) := by sorry
end DiscreteConvex.MConvexFunctionsD
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.163, Theorem 6.51
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.