LEMMA 2 — every coordinate occurs in a tight shortest path
ProvedGomory69.MasterFaces.lemma_2facetsgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-path
Suppose is a face of with . For every there is a nonnegative integer solution of the group equation such that
Thus some shortest path to passes through the group vertex . The claim ensures that no coordinate of a facet is absent from all tight integer points.
Formalization Note The displayed integer-vector assertion is the first sentence of the lemma; the path-through- assertion is its graph interpretation.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_GroupPolyhedron
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), LEMMA 2, p. 472. -/
theorem lemma_2 {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) :
∃ t : N → ℕ, GroupSolution N g₀ t ∧
dot π (castSolution t) = π₀ ∧ 0 < t g := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), pp. 472–473, LEMMA 2. DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.