LEMMA 1 — subpaths of a shortest path remain shortest
ProvedGomory69.MasterFaces.lemma_1group-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-path
Let be a shortest path from to , represented by a nonnegative integer vector on . If coordinatewise and , then is shortest for its displacement :
Because arc lengths depend only on the increment, this also covers a copy of starting at any group vertex.
Formalization Note Paths are multiplicity vectors. The starting vertex of the translated subpath does not change its minimization claim and so is absent from the Lean statement.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_GroupPolyhedron
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), LEMMA 1, p. 472; paths are represented by multiplicity vectors. -/
theorem lemma_1 {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(N : Finset G) (hN : (0 : G) ∉ N) (g₀ h : G) (π : N → ℝ)
(t t' : N → ℕ) (ht : IsShortest N g₀ π t)
(ht' : GroupSolution N h t') (hle : ∀ g : N, t' g ≤ t g) :
IsShortest N h π t' := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 472, LEMMA 1. DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.