A non-Hirsch -dimensional polytope with facets (Matschke–Santos–Weibel 2015)
OpenHirschDim4.msw_twentydiscrete-geometryhirsch-conjecturelinear-optimizationpolytopes
There is a bounded, full-dimensional -dimensional polytope with facets whose combinatorial diameter is greater than (in fact at least ): a counterexample to the Hirsch conjecture in dimension . Matschke, Santos and Weibel (2015) obtained it from a -dimensional prismatoid of width with only vertices, via Santos's spindle construction, which outputs dimension with facets. This lowered Santos's original counterexample dimension from to ; the published polytope has vertices.
Formalization Note. IsNonHirsch a b is ¬ DiamLE (Hpoly a b) (40-20), i.e. diameter . The statement matches the shape of Santos's Corollary 1.7 with .
Preamble
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_SantosHirsch_Counter_Setting open scoped RealInnerProductSpace
Formal statement
namespace HirschDim4
theorem msw_twenty :
∃ (a : Fin 40 → EuclideanSpace ℝ (Fin 20)) (b : Fin 40 → ℝ),
(Hirsch.Hpoly a b).Nonempty ∧
Bornology.IsBounded (Hirsch.Hpoly a b) ∧
SantosHirsch.Counter.IsFacetPresentation a b ∧
SantosHirsch.Counter.IsNonHirsch a b := by sorry
end HirschDim4Source
B. Matschke, F. Santos & C. Weibel, The width of five-dimensional prismatoids, Proc. London Math. Soc. (3) 110(3) (2015), 647-672, https://doi.org/10.1112/plms/pdu064, arXiv:1202.4701 (main theorem: width-six 5-prismatoids with 25 vertices; non-Hirsch 20-polytopes). Also F. Santos, Annals of Math. 176 (2012), 383-412, Theorem 1.12 (20-dimensional, 40 facets, 36442 vertices).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.