The Klee–Walkup polytope is Hirsch-sharp ( facets, distance )
OpenHirschDim4.klee_walkup_Q4discrete-geometryhirsch-conjecturelinear-optimizationpolytopes
There is a -dimensional polytope with facets and two vertices at graph distance at least . Since , it meets the Hirsch bound with equality: it is Hirsch-sharp. This is the lower-bound half of (Klee–Walkup 1967). is the smallest non-trivial Hirsch-sharp polytope (more facets than twice its dimension) and the starting block of every known Hirsch-sharp polytope with . Kim and Santos give small explicit integer coordinates for the dual (nine vectors ); the two tetrahedra and are at dual-graph distance .
Formalization Note. The conclusion ∀ k<5, ¬ Reach (Hpoly a b) k u v says the distance is at least ; the matching upper bound is separate. Simplicity of is not required here.
Preamble
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk import Definitions.Def_SantosHirsch_Counter_Setting open scoped RealInnerProductSpace
Formal statement
namespace HirschDim4
theorem klee_walkup_Q4 :
∃ (a : Fin 9 → EuclideanSpace ℝ (Fin 4)) (b : Fin 9 → ℝ)
(u v : EuclideanSpace ℝ (Fin 4)),
Bornology.IsBounded (Hirsch.Hpoly a b) ∧
SantosHirsch.Counter.IsFacetPresentation a b ∧
u ∈ Set.extremePoints ℝ (Hirsch.Hpoly a b) ∧
v ∈ Set.extremePoints ℝ (Hirsch.Hpoly a b) ∧
∀ k < 5, ¬ Hirsch.Reach (Hirsch.Hpoly a b) k u v := by sorry
end HirschDim4Source
Kim & Santos, An update on the Hirsch conjecture, arXiv:0907.1186, Theorem 3.8 and Section 3.3 (explicit coordinates), attributing to V. Klee & D. W. Walkup, The d-step conjecture for polyhedra of dimension d<6, Acta Math. 117 (1967), 53-78, https://doi.org/10.1007/BF02395040. Lower-bound (sharpness) half of H(9,4)=5.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.