Proposition 8.2 -- supermodular_pair_conjugate_submodular
ProvedDiscreteConvex.ConjugacyDualityB.supermodular_pair_conjugate_submodularcombinatoricsdiscrete-convex-analysis
Proposition 8.2 (p.207). For a supermodular function in two variables, the Legendre-Fenchel transform is submodular.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.207, Proposition 8.2.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_ConjugacyDualityB_ConvexConjugateRW import Definitions.Def_DiscreteConvex_ConjugacyDualityB_SupermodularPair
Formal statement
namespace DiscreteConvex.ConjugacyDualityB
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 8.2 (p.207). For a supermodular function `f` in two variables, `f•` is
submodular. -/
theorem supermodular_pair_conjugate_submodular (f : (Fin 2 → ℝ) → WithTop ℝ)
(hf : SupermodularPair f) :
∀ p q : Fin 2 → ℝ, ConvexConjugateRW f p + ConvexConjugateRW f q ≥
ConvexConjugateRW f (p ⊔ q) + ConvexConjugateRW f (p ⊓ q) := by sorry
end DiscreteConvex.ConjugacyDualityB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.207, Proposition 8.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.