Proposition 5.1 -- admissible_potentials_properties
DisprovedDiscreteConvex.LConvexSetsB.admissible_potentials_propertiesconvex-optimizationdiscrete-convex-analysislinear-optimization
Proposition 5.1 (p.122). Let be a distance function. (1) no negative cycle exists in the graph . (2) If , and . (3) For , is nonempty and . (4) is an integral polyhedron for an integer-valued .
These are the fundamental facts, well known in network flow theory, connecting a distance function to its set of admissible potentials.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.122, Proposition 5.1, Eq. (5.5)-(5.6).)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSetsB_DistanceFunction import Definitions.Def_DiscreteConvex_LConvexSetsB_AdmissiblePotentials import Definitions.Def_DiscreteConvex_LConvexSetsB_NoNegativeCycle import Definitions.Def_DiscreteConvex_LConvexSetsB_ShortestDist import Definitions.Def_DiscreteConvex_LConvexSetsB_TriangleInequality import Definitions.Def_DiscreteConvex_LConvexSetsB_IsIntegerValuedGamma import Definitions.Def_DiscreteConvex_LConvexSetsB_IsIntegralPolyhedron
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.122, Proposition 5.1, in `DiscreteConvex.LConvexSetsB`.
-/
namespace DiscreteConvex.LConvexSetsB
/-- Proposition 5.1 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.122). See the item's
`natural_language_statement` for the full statement. -/
theorem admissible_potentials_properties {V : Type*} [Fintype V] [DecidableEq V]
(γ : V → V → WithTop ℝ) (hγ : DistanceFunction γ) :
((AdmissiblePotentials γ).Nonempty ↔ NoNegativeCycle γ) ∧
((AdmissiblePotentials γ).Nonempty →
(∀ u v, ShortestDist γ u v = ⨆ p ∈ AdmissiblePotentials γ, (((p v - p u : ℝ)) : WithTop ℝ)) ∧
AdmissiblePotentials (ShortestDist γ) = AdmissiblePotentials γ) ∧
(TriangleInequality γ →
(AdmissiblePotentials γ).Nonempty ∧
(∀ u v, γ u v = ⨆ p ∈ AdmissiblePotentials γ, (((p v - p u : ℝ)) : WithTop ℝ))) ∧
(IsIntegerValuedGamma γ → IsIntegralPolyhedron (AdmissiblePotentials γ)) := by sorry
end DiscreteConvex.LConvexSetsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.122, Proposition 5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.