p. 506 — vertices of P(G, g0) for groups of exponent s ∈ {2, 3}: independent support, entries below s
ProvedGomory69.SpecialGroups.vertex_characterizationgroup-polyhedronindependencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vertices
Let be a finite Abelian group in which every nonzero element has order , where or (the groups ). A nonzero nonnegative integer vector on is a vertex of for some if and only if the elements with are independent and
This characterization is what the vertex count of pp. 506–507 is built on.
Formalization Note The page does not exclude , whose empty support is independent but which solves no group equation with ; the hypothesis is added. "Vertex for some " includes that solves the group equation for that .
Preamble
import Mathlib import Definitions.Def_Gomory69_SpecialGroups_GroupPolyhedron
Formal statement
namespace Gomory69.SpecialGroups
/-- The vertex characterization of p. 506 (Gomory 1969): if every nonzero element of `𝒢` has order
`s ∈ {2, 3}`, a nonzero nonnegative integer vector `t` is a vertex of `P(𝒢, g₀)` for some
`g₀ ≠ 0̄` if and only if the `g` with `t(g) > 0` are independent and `t(g) < s` for all `g`. -/
theorem vertex_characterization {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(s : ℕ) (hs : s = 2 ∨ s = 3) (hG : AllNonzeroOfOrder G s)
(t : {g : G // g ≠ 0} → ℕ) (ht : t ≠ 0) :
(∃ g₀ : G, g₀ ≠ 0 ∧ t ∈ solutionSet g₀ ∧ toReal t ∈ Set.extremePoints ℝ (masterPolyhedron g₀)) ↔
(IsIndependent (support t) ∧ ∀ g, t g < s) := by sorry
end Gomory69.SpecialGroups
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 506
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.