The Hirsch conjecture in dimension four

The Hirsch conjecture claimed that one can travel between any two vertices of a $d$-dimensional polytope with $n$ facets in at most $n - d$ steps along edges. It is false in high dimensions, where the smallest known counterexample now lives in dimension 19, and true up to dimension 3. The task is to settle the first open case, dimension 4.

Problem

Let $P \subset \mathbb{R}^4$ be a bounded, full-dimensional convex polytope with $n$ facets. Its graph has the vertices of $P$ as nodes and the edges of $P$ as arcs; the combinatorial diameter of $P$ is the largest graph distance between two vertices.

Question. Is the diameter of every such $P$ at most $n - 4$? A counterexample is an explicit 4-polytope whose diameter exceeds $n - 4$; a proof would establish the Hirsch bound in dimension 4.

Background

Warren M. Hirsch posed the question to George Dantzig in 1957; Dantzig's simplex method for linear programming moves along edges of a polytope [4]. Santos disproved the conjecture in 2012 with a 43-dimensional counterexample built from prismatoids of large width [1]. Matschke, Santos and Weibel brought the dimension down to 20 [2], and in 2025 Swirszcz, Wagner, Williamson and coauthors at Google DeepMind generated non-Hirsch polytopes in dimension 19, the smallest known, by large-scale computer search [3]. Epoch asks for dimension 4 because a counterexample there is expected to need a new idea rather than a refinement of these constructions.

What is known

• The bound holds for $d \le 3$ (Epoch's summary).
• Counterexamples exist in dimension 43 (Santos, 2012) [1], 20 (Matschke, Santos and Weibel) [2] and 19 (Swirszcz et al., 2025) [3].
• The conjecture is open for $4 \le d \le 18$.

What would count as progress

• An explicit rational 4-polytope given both by its facet inequalities $Ax \le b$ ($n$ rows, none redundant) and by its full vertex list, together with two vertices at graph distance greater than $n - 4$. Exact rational arithmetic confirms the facets, the vertices, the edge graph and the distance.
• Epoch scores submissions with its own verifier on a JSON file with integer $A$ and $b$ and exact rational vertices.
• A proof that every 4-polytope satisfies the Hirsch bound would settle the question the other way.

References

1. F. Santos, A counterexample to the Hirsch conjecture, Ann. of Math. 176 (2012), 383–412. doi:10.4007/annals.2012.176.1.7
2. B. Matschke, F. Santos and C. Weibel, The width of five-dimensional prismatoids, Proc. London Math. Soc. 110 (2015), 647–672. doi:10.1112/plms/pdu064
3. G. Swirszcz, A. Z. Wagner, G. Williamson et al., Advancing geometry with AI: multi-agent generation of polytopes, 2025. arXiv:2502.05199
4. E. D. Kim and F. Santos, An update on the Hirsch conjecture, Jahresber. Dtsch. Math.-Ver. 112 (2010), 73–98. doi:10.1365/s13291-010-0001-8

Source

Imported from FrontierMath: Open Problems, hirsch-conjecture, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.