Linear diameter bounds for polytopes after the Hirsch conjecture: Santos' Question 1.9 and the Hähnle conjecture

The Hirsch conjecture asserted that the graph of a $d$-dimensional polytope with $n$ facets has diameter at most $n-d$; Santos' 43-dimensional counterexample (2012) disproved it but left the underlying quantitative question — how large can the diameter be —, as Santos himself put it, "almost as open as it was before." This problem records the surviving core in the form the source states it: (i) Santos' Question 1.9, whether a universal constant $c$ independent of $d$ bounds every such diameter by $cn$ (Santos suspects not); (ii) the conjectured positive answer, the bound $\Delta(d,n)\le dn$ credited by Santos to N. Hähnle (Conjecture 1.10, almost equivalent to $d(n-d)$, Conjecture 1.11); and (iii) the complementary lower-bound question of how large the relative Hirsch excess $\delta/(n-d)-1$ can be. The best known upper bound is still only quasi-polynomial, $\Delta(d,n)\le(n-d)^{\log_2 O(d/\log d)}$ (Sukegawa 2019), and the best lower bounds are linear — polytopes whose relative excess approaches $1/16$ (Davies et al. 2025). Resolving Question 1.9 in either direction — a proof of a universal linear bound, or a family of polytopes with superlinear diameter — would settle whether polytope diameters are linear at all: the central open quantitative question of polyhedral combinatorics and the combinatorial core of worst-case simplex-method complexity.

Background

A convex polytope is the bounded solution set of a finite system of linear inequalities; a facet is a face of dimension one less than the polytope itself, and the graph (or 1-skeleton) of a polytope is the abstract graph whose nodes are its vertices (0-dimensional faces) with an edge for each 1-dimensional face. The combinatorial diameter of a polytope is the maximum, over pairs of vertices, of the number of edges on a shortest path between them. Write $\Delta(d,n)$ for the maximum diameter over all $d$-dimensional polytopes with $n$ facets. Because each pivot of the simplex method for linear programming moves along an edge of the feasibility polyhedron, $\Delta(d,n)$ is a worst-case lower bound on the number of iterations of the simplex method under any pivot rule (Kalai–Kleitman 1992), so the growth of $\Delta(d,n)$ is the combinatorial core of pivot-method complexity.

In 1957 W. M. Hirsch conjectured that $\Delta(d,n)\le n-d$. Klee and Walkup (1967) proved the equivalent $d$-step conjecture for dimensions $d<6$ and disproved Hirsch's bound for unbounded polyhedra; the bounded case stood until Santos (2012) constructed a 43-dimensional polytope with 86 facets and diameter at least 44. His construction starts from a spindle — a polytope with two vertices such that every facet contains exactly one of them, the spindle's length being the graph distance between the two — of dimension 5 with 48 facets and length 6, and converts it through a 'strong $d$-step' theorem into the high-dimensional non-Hirsch polytope.

The disproof leaves the quantitative question open in both directions, and the known bounds form a strict hierarchy: the Hirsch bound $n-d$ is false; a universal bound $c\cdot n$ with $c$ independent of $d$ (Santos' Question 1.9) is the strongest conceivable linear improvement and is suspected by Santos to be false; the $d$-dependent linear bound $\Delta(d,n)\le dn$ (Santos' Conjecture 1.10, credited there to N. Hähnle; almost equivalent, by a small translation Santos records, to $\Delta(d,n)\le d(n-d)$, Conjecture 1.11) is the conjectured positive answer; a bound polynomial in $d$ and $n$ (the 'polynomial Hirsch' question, discussed in Santos' 2013 survey) is open; and the best theorem is the quasi-polynomial bound $\Delta(d,n)\le n^{\log_2 d+2}$ of Kalai–Kleitman (1992), improved by Todd (2014) to $(n-d)^{\log_2 d}$ and by Sukegawa (2019) to $(n-d)^{\log_2 O(d/\log d)}$ — that is, $n$ raised to a power that still grows with $\log d$. No polynomial upper bound is known.

On the lower side, define the relative Hirsch excess of a non-Hirsch polytope with $n$ facets, dimension $d$ and diameter $\delta$ as $\delta/(n-d)-1$, the fractional amount by which it violates the Hirsch bound. Santos' propagation results (products plus gluing) carry a fixed positive excess to infinite families — in a fixed high dimension, excess arbitrarily close to $1/20$ — but no operation is known that increases excess. All known non-Hirsch polytopes arise from 5-dimensional prismatoids (polytopes whose vertices all lie on two parallel facets; in recent work, 'drums'), whose width — the graph distance between the two special facets in the facet–ridge graph, a ridge being a face of dimension two less than the polytope — controls the excess obtainable; the largest excess known is $1/16$, from the drum family of Davies et al. (2025). Two further results delimit the methods: Eisenbrand–Hähnle–Razborov–Rothvoß (2010) showed that natural combinatorial abstractions of polyhedra already admit superlinear diameters, so abstraction-only arguments cannot prove a polynomial bound; and Bonifas–Di Summa–Eisenbrand–Hähnle–Niemeier (2012) proved a polynomial bound only for constraint matrices whose sub-determinants are bounded.

Problem Statement

Let $\Delta(d,n)$ denote the maximum, over all $d$-dimensional convex polytopes with $n$ facets, of the combinatorial diameter of the polytope's graph — that is, of the maximum, over pairs of vertices of the polytope, of the number of edges on a shortest path between them in the graph whose nodes are the vertices and whose edges are the 1-dimensional faces.

(1) Santos' Question 1.9. Does there exist a constant $c$, independent of both $d$ and $n$, such that

$$\Delta(d,n)\ \le\ c\,n\quad\text{for all }d\ge 1\text{ and }n\ge d+1?$$

Santos suspects the answer is negative, but neither a superlinear lower bound nor a linear upper bound is currently known.

(2) Positive sharpening (Santos' Conjectures 1.10 and 1.11, the former credited to N. Hähnle). Is $\Delta(d,n)\le dn$; almost equivalently, by the small translation Santos records in his Remark 6.4, $\Delta(d,n)\le d(n-d)$?

(3) Negative sharpening. How large can the relative Hirsch excess $\delta(P)/(n-d)-1$ of a non-Hirsch polytope $P$ of dimension $d$ with $n$ facets and diameter $\delta(P)$ be — is it uniformly bounded over all polytopes, over all $d$ and $n$, and what is its supremum?

These three items are facets of a single objective: determining whether polytope diameters are linearly bounded, the question Santos isolates as what his counterexample leaves 'almost as open as it was before'. A complete resolution of item (1) in either direction completes the problem: a proof exhibiting a universal constant $c$ (item (2) being the conjectured dimension-dependent linear bound, not a stronger claim), or a construction, with complete proof, of a family of polytopes whose diameters exceed $c\cdot n$ for every constant $c$ along the family (which in particular makes the relative Hirsch excess of item (3) unbounded).

References

1. Francisco Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics 176 (2012) 383–412. DOI: 10.4007/annals.2012.176.1.7; arXiv:1006.2814. https://doi.org/10.4007/annals.2012.176.1.7
2. Victor Klee, David W. Walkup, The d-step conjecture for polyhedra of dimension d<6, Acta Mathematica 117 (1967) 53–78. DOI: 10.1007/BF02395040. https://doi.org/10.1007/BF02395040
3. Gil Kalai, Daniel J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bulletin of the American Mathematical Society 26 (1992) 315–316. DOI: 10.1090/S0273-0979-1992-00285-9; arXiv:math/9204233. https://doi.org/10.1090/S0273-0979-1992-00285-9
4. Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, Thomas Rothvoß, Diameter of Polyhedra: Limits of Abstraction, Mathematics of Operations Research 35 (2010) 786–794. DOI: 10.1287/moor.1100.0470. https://doi.org/10.1287/moor.1100.0470
5. Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, On sub-determinants and the diameter of polyhedra, Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG 2012), 357–362. DOI: 10.1145/2261250.2261304; arXiv:1108.4272. https://doi.org/10.1145/2261250.2261304
6. Benjamin Matschke, Francisco Santos, Christophe Weibel, The width of five-dimensional prismatoids, Proceedings of the London Mathematical Society 110 (2015) 647–672. DOI: 10.1112/plms/pdu064; arXiv:1202.4701. https://doi.org/10.1112/plms/pdu064
7. Francisco Santos, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, TOP 21 (3) (2013) 426–460. DOI: 10.1007/s11750-013-0295-7; arXiv:1307.5900. https://doi.org/10.1007/s11750-013-0295-7
8. Michael J. Todd, An improved Kalai–Kleitman bound for the diameter of a polyhedron, SIAM Journal on Discrete Mathematics 28 (2014) 1944–1947. DOI: 10.1137/140962310; arXiv:1402.3579. https://doi.org/10.1137/140962310
9. Noriyoshi Sukegawa, Improving bounds on the diameter of a polyhedron in high dimensions, Discrete Mathematics 340 (2017) 2134–2142. DOI: 10.1016/j.disc.2017.04.005; arXiv:1604.04039. https://doi.org/10.1016/j.disc.2017.04.005
10. Noriyoshi Sukegawa, An asymptotically improved upper bound on the diameter of polyhedra, Discrete & Computational Geometry 62 (2019) 690–699. DOI: 10.1007/s00454-018-0016-y. https://doi.org/10.1007/s00454-018-0016-y
11. Francisco Criado, Francisco Santos, Topological prismatoids and small simplicial spheres of large diameter, Experimental Mathematics 31 (2022) 461–473. DOI: 10.1080/10586458.2019.1641766; arXiv:1807.03030. https://doi.org/10.1080/10586458.2019.1641766
12. Nicolai Hähnle, Steven Klee, Vincent Pilaud, Obstructions to weak decomposability for simplicial polytopes, Proceedings of the American Mathematical Society 142 (2014) 3249–3257. DOI: 10.1090/S0002-9939-2014-12101-0; arXiv:1206.6143. https://doi.org/10.1090/S0002-9939-2014-12101-0
13. J. Mackenzie Gallagher, Walter D. Morris Jr., A proof of the strict monotone 5-step conjecture, Discrete & Computational Geometry 65 (2021) 476–488. DOI: 10.1007/s00454-019-00161-3; arXiv:1806.03403. https://doi.org/10.1007/s00454-019-00161-3
14. Xavier Allamigeon, Quentin Canu, Pierre-Yves Strub, A formal disproof of the Hirsch conjecture, arXiv:2301.04060 (2023). https://arxiv.org/abs/2301.04060
15. Grzegorz Swirszcz, Adam Zsolt Wagner, Geordie Williamson, Sam Blackwell, Bogdan Georgiev, Alex Davies, Ali Eslami, Sebastien Racaniere, Theophane Weber, Pushmeet Kohli, Advancing geometry with AI: multi-agent generation of polytopes, arXiv:2502.05199 (2025). https://arxiv.org/abs/2502.05199
16. Alex Davies, Prateek Gupta, Sebastien Racaniere, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, Geordie Williamson, Drums of high width, arXiv:2503.09919 (2025). https://arxiv.org/abs/2503.09919
17. Alexander E. Black, Lei Xue, Any proof of polynomial Hirsch must be completely incoherent, arXiv:2607.11628 (2026). https://arxiv.org/abs/2607.11628
18. Bento Natura, Circuit diameter of polyhedra is strongly polynomial, arXiv:2602.06958 (2026). https://arxiv.org/abs/2602.06958
19. Stefan Glock, Olaf Parczyk, Silas Rathke, Tibor Szabó, The maximum diameter of $d$-dimensional simplicial complexes, arXiv:2602.20890 (2026). https://arxiv.org/abs/2602.20890