THEOREM 2, p. 460 — every vertex of P(G, N, g0) is irreducible
ProvedGomory69.Asymptotic.theorem_2group-polyhedronirreducibilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vertices
Let be a finite Abelian group, a set of nonzero elements of and . Every vertex of is an integer point: there is a nonnegative integer solution of the group equation
with (coordinatewise), and this is irreducible.
Together with THEOREM 1, this bounds the size of every vertex of the corner polyhedron.
Formalization Note "Vertex" is an extreme point of the convex hull. The paper's one-line statement contains two facts, made explicit here: a vertex of is one of the integer solutions it is the hull of, and that integer solution is irreducible.
Preamble
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron
Formal statement
namespace Gomory69.Asymptotic
/-- THEOREM 2 (p. 460): every vertex of `P(𝒢, 𝒩, g₀)` is (the real image of) an
irreducible nonnegative integer solution of the group equation (5). -/
theorem theorem_2 {G : Type*} [AddCommGroup G] [Finite G] (𝒩 : Finset G)
(h𝒩 : (0 : G) ∉ 𝒩) (g₀ : G) (v : ↥𝒩 → ℝ)
(hv : v ∈ Set.extremePoints ℝ (groupPolyhedron 𝒩 g₀)) :
∃ t ∈ groupSolutions 𝒩 g₀, toReal 𝒩 t = v ∧ IsIrreducible 𝒩 t := by sorry
end Gomory69.Asymptotic
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 460, THEOREM 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.