The unbounded Hirsch conjecture fails in dimension (Klee–Walkup 1967)
OpenHirschDim4.unbounded_four_counterexampleThe unbounded Hirsch conjecture fails in dimension : there is a simple, unbounded -dimensional polyhedron with facets and two vertices at graph distance at least . It is obtained from the Hirsch-sharp polytope ( facets, diameter ) by a projective transformation sending a facet containing neither vertex to infinity; this preserves the distance but destroys boundedness. This is why the bounded problem in dimension remains open while its unbounded and monotone variants already fail. This milestone targets the non-Hirsch (lower-bound) part of the source theorem, which states diameter exactly .
Formalization Note. Uses KleeWalkup67.FiveStep.IsFacetPresentation and IsSimple (the latter requires a vertex and exactly tight facets at each vertex); ¬ IsBounded records unboundedness; ∀ k<5, ¬ Reach ... k u v is distance .
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk import Definitions.Def_KleeWalkup67_FiveStep_Polyhedra open scoped RealInnerProductSpace
namespace HirschDim4
theorem unbounded_four_counterexample :
∃ (a : Fin 8 → EuclideanSpace ℝ (Fin 4)) (b : Fin 8 → ℝ)
(u v : EuclideanSpace ℝ (Fin 4)),
KleeWalkup67.FiveStep.IsFacetPresentation a b ∧
KleeWalkup67.FiveStep.IsSimple a b ∧
¬ Bornology.IsBounded (Hirsch.Hpoly 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 HirschDim4Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.