THEOREM 10 — face coefficients are shortest-path distances
ProvedGomory69.MasterFaces.theorem_10facetsgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-path
Let be a face of with . For any , the one-arc path to has minimum length among all nonnegative integer vectors representing :
This identifies each facet coefficient with a shortest-path value and supports the following subadditivity consequences.
Formalization Note The unit vector at attains the bound, so no real infimum or attainment convention is needed.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_GroupPolyhedron
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), THEOREM 10, p. 473. -/
theorem theorem_10 {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(N : Finset G) (hN : (0 : G) ∉ N) (g₀ : G) (π : N → ℝ) (π₀ : ℝ)
(hπ₀ : 0 < π₀) (hface : IsFace N g₀ π π₀) (g : N) :
∀ s : N → ℕ, GroupSolution N (g : G) s → π g ≤ dot π (castSolution s) := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 473, THEOREM 10. DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.