The polynomial Hirsch question for polytopes and normal complexes, and the non-revisiting property beyond flag normal complexes

After Santos' 2012 counterexample to the Hirsch conjecture, Adiprasito and Benedetti (Mathematics of Operations Research, 2014) confirmed the conjecture for all flag normal simplicial complexes by proving the non-revisiting path property via the right-angled spherical metric and CAT(1) geometry, and their paper explicitly leaves two questions open: whether any universal linear or even polynomial upper bound on the diameter exists for polytopes or normal complexes, and whether the non-revisiting property still holds for flag complexes once the normality assumption is dropped while retaining the connected facet-ridge graph that normality provides. Both questions are open as of August 2026: the best general upper bound remains the quasi-polynomial $(n-d)^{\log_2 O(d/\log d)}$ (Sukegawa 2018); 2025 work produced the first infinite family of Hirsch counterexamples whose excess width grows linearly in the number of vertices; the circuit-diameter relaxation was settled positively (Natura 2026) and the coherent-monotone-path analog refuted (Black-Xue 2026), leaving the central question untouched in both directions. The problem: is the maximum diameter of $d$-polytopes with $n$ facets (and of normal complexes) bounded by a linear or polynomial function of $n$ and $d$, and does the non-revisiting property hold for pure flag complexes with a connected facet-ridge graph once the normality assumption is dropped?

Background

A convex polytope is the bounded intersection of finitely many half-spaces; its dimension $d$ is the dimension of its affine hull and its facets are its $(d-1)$-dimensional faces. The graph (or 1-skeleton) of a polytope has the polytope's vertices as nodes and its edges as links, and its diameter is the largest number of edges on a shortest vertex-to-vertex path. This diameter is a natural lower bound for the number of iterations of the simplex method for linear programming, since every simplex run walks along edges of the constraint polyhedron. Writing $n$ for the number of facets, Warren Hirsch proposed in 1957, in a letter to George Dantzig, that the diameter of a $d$-dimensional polyhedron with $n$ facets is at most $n-d$; this is the Hirsch conjecture. The version for unbounded polyhedra was disproved by Klee and Walkup (1967), who also showed the bounded version for polytopes equivalent to the $d$-step conjecture, the special case $n=2d$. A complementary equivalent, the non-revisiting path conjecture, was introduced in the 1960s by Klee and Wolfe (as recounted in Adiprasito-Benedetti): for any two facets of a simplicial polytope there is a path of adjacent facets in which no vertex is left and later re-entered — formally, for every vertex, the facets containing it form a contiguous block of the path. A non-revisiting facet path is short: at most $n-d$ steps for the boundary of a simplicial $d$-polytope with $n$ vertices, because the first facet already contains $d$ vertices and every later facet of the path must contribute a vertex not seen before, otherwise the path would revisit. Hence this property implies the Hirsch bound on the facet-ridge graph. The bounded Hirsch conjecture stood for over fifty years until Santos (2012) constructed a 43-dimensional polytope with 86 facets whose diameter exceeds $n-d$, refuting it together with the $d$-step and non-revisiting path conjectures; Matschke, Santos and Weibel (2015) reduced the counterexample dimension to 20 using 5-dimensional prismatoids (polytopes whose vertices lie on two parallel facets; the minimum number of steps between those two facets in the dual graph is the prismatoid's width, and width exceeding the dimension produces Hirsch counterexamples). The known violations are nevertheless small, and the correct order of the maximum diameter $\Delta(d,n)$ of a $d$-polytope with $n$ facets remains unknown. The best general upper bounds are old: exponential bounds of the form $2^{d-1}n$ due to Larman (1970) and Barnette (1974), and the quasi-polynomial bounds of Kalai and of Kalai-Kleitman (1992), improved by Todd (2014) and by Sukegawa (2016, 2018) to $(n-d)^{\log_2 O(d/\log d)}$. No polynomial bound is known, and no family of polytopes with super-linear diameter is known either, so both a positive and a negative answer to the polynomial question are compatible with current knowledge. The question is also studied on a combinatorial abstraction: a pure $(d-1)$-dimensional simplicial complex on $n$ vertices is normal if the link of every face of codimension at least 2 is connected; the facet-ridge graph (dual graph) has the facets as nodes and joins facets sharing a ridge, that is, a codimension-one face. Normality in particular forces the facet-ridge graph itself to be connected, since the link of the empty face is the whole complex; a pure complex with connected facet-ridge graph is called strongly connected, a property strictly weaker than normality. By polarity, the facet-ridge graph of the boundary of a simplicial $d$-polytope with $n$ vertices is the graph of the dual $d$-polytope with $n$ facets, and all polytope boundaries, spheres, and triangulated manifolds are normal, so the normal complexes form a common generalization of the polytope case. A complex is flag if every inclusion-minimal non-face has exactly two elements, equivalently if the complex is the clique complex of its own graph; a polytope is called flag (in this simplicial context) when its boundary complex is flag. Adiprasito and Benedetti (2014) endowed a flag complex with the right-angled spherical metric, in which every edge has length $\pi/2$ and every face is a spherical simplex; by a classical criterion of Gromov for spaces with curvature bounded above, a flag complex with this metric is CAT(1) — a length space whose geodesic triangles are, in the comparison sense, no fatter than triangles on the unit sphere — and every vertex star is geodesically convex, so a geodesic never re-enters a vertex star it has left. Normality is then used to bridge between facets that meet only in codimension-2 faces, by induction on links. The result: every flag normal complex satisfies the non-revisiting path conjecture, and hence a pure flag normal $(d-1)$-complex on $n$ vertices has facet-ridge diameter at most $n-d$; in particular every flag polytope and every flag triangulation of a connected manifold obeys the Hirsch bound. (Earlier, Provan and Billera had established the Hirsch bound for vertex-decomposable complexes, a shellable subclass.) The proof uses both hypotheses, and the paper's introduction states openly that, after Santos' counterexamples, 'we do not know whether a linear or even a polynomial upper bound exist' for polytopes or for normal complexes, and invites the question whether the normality assumption is needed at all for flag complexes. Since normality already guarantees a connected facet-ridge graph, this second question is meaningful for complexes that stay strongly connected: flagness alone does not prevent disconnection, as the disjoint union of two simplices (pure and flag, but with no facet path between its two components) shows. These two questions are the problem stated below.

Problem Statement

Let $\Delta(d,n)$ denote the maximum, over all $d$-dimensional convex polytopes with $n$ facets, of the diameter of their graphs. Part A (the polynomial Hirsch question, stated by the source): (i) Does there exist a universal constant $C$ such that $\Delta(d,n)\le C(n-d)$ for all $d$ and $n$, that is, a linear Hirsch-type bound surviving Santos' counterexamples? (ii) If not, does there at least exist a two-variable polynomial $p$ with $\Delta(d,n)\le p(n,d)$ for all $d$ and $n$? The source poses the same two questions for the strictly larger class of pure normal $(d-1)$-dimensional simplicial complexes with $n$ vertices, where the diameter is that of the facet-ridge graph; since every polytope boundary is normal, a positive answer at the normal-complex level implies the polytope answer, while a negative construction within normal complexes does not by itself settle the polytope question. Part B (the source's companion structural question): with the normality assumption dropped but the connectedness of the facet-ridge graph that normality provides retained — that is, for strongly connected complexes — does every pure flag $(d-1)$-complex with $n$ vertices admit a non-revisiting facet path between any two facets, and hence have facet-ridge diameter at most $n-d$? (Flagness alone cannot stand in for normality outright: the disjoint union of two $(d-1)$-simplices is pure and flag, yet no facet path at all joins its two components.)

These sub-questions are separately answerable rather than jointly required, and the nested relations among them bear on what counts as a resolution: a proof of the linear bound (i) also settles the polynomial question (ii), a super-polynomial construction within a given class settles (ii) negatively and hence (i) as well for that class, and Part B is independent of Part A. A definitive answer in either direction to any one of (i), (ii), or Part B resolves that sub-question.

References

1. Karim Alexander Adiprasito and Bruno Benedetti, The Hirsch Conjecture Holds for Normal Flag Complexes, Mathematics of Operations Research 39 (2014), DOI 10.1287/moor.2014.0661; arXiv:1303.3598, https://arxiv.org/abs/1303.3598
2. 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://arxiv.org/abs/1006.2814
3. Victor Klee and 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
4. D. G. Larman, Paths on polytopes, Proceedings of the London Mathematical Society s3-20 (1970), 161-178, DOI 10.1112/plms/s3-20.1.161, https://doi.org/10.1112/plms/s3-20.1.161
5. D. Barnette, An upper bound for the diameter of a polytope, Discrete Mathematics 10 (1974), 9-13, DOI 10.1016/0012-365X(74)90016-8, https://doi.org/10.1016/0012-365X(74)90016-8
6. G. Kalai, Upper bounds for the diameter and height of graphs of convex polyhedra, Discrete & Computational Geometry 8 (1992), 363-372, DOI 10.1007/BF02293053, https://doi.org/10.1007/BF02293053
7. G. Kalai and D. 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, https://doi.org/10.1090/S0273-0979-1992-00285-9
8. J. S. Provan and L. J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Mathematics of Operations Research 5 (1980), 576-594, DOI 10.1287/moor.5.4.576, https://doi.org/10.1287/moor.5.4.576
9. M. Gromov, Hyperbolic Groups, Mathematical Sciences Research Institute Publications 8 (Essays in Group Theory), Springer (1987), 75-263, DOI 10.1007/978-1-4613-9586-7_3, https://doi.org/10.1007/978-1-4613-9586-7_3
10. Francisco Santos, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, 2013, arXiv:1307.5900, https://arxiv.org/abs/1307.5900
11. 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://arxiv.org/abs/1402.3579
12. Noriyoshi Sukegawa, Improving bounds on the diameter of a polyhedron in high dimensions, 2016, arXiv:1604.04039, https://arxiv.org/abs/1604.04039
13. Noriyoshi Sukegawa, An Asymptotically Improved Upper Bound on the Diameter of Polyhedra, Discrete & Computational Geometry 62 (2019), 690-699 (first published online 2018), DOI 10.1007/s00454-018-0016-y, https://doi.org/10.1007/s00454-018-0016-y
14. Benjamin Matschke, Francisco Santos, and 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://arxiv.org/abs/1202.4701
15. Jean-Philippe Labbé, Thibault Manneville, and Francisco Santos, Hirsch polytopes with exponentially long combinatorial segments, Mathematical Programming 165 (2017), 663-688 (first published online 2016), DOI 10.1007/s10107-016-1099-y; arXiv:1510.07678, https://arxiv.org/abs/1510.07678
16. Francisco Criado and Francisco Santos, The maximum diameter of pure simplicial complexes and pseudo-manifolds, 2016, arXiv:1603.06238, https://arxiv.org/abs/1603.06238
17. Bruno Benedetti and Matteo Varbaro, On the dual graph of Cohen-Macaulay algebras, 2014, arXiv:1403.3241, https://arxiv.org/abs/1403.3241
18. Brent Holmes, On the diameter of dual graphs of Stanley-Reisner rings with Serre (S_2) property and Hirsch type bounds on abstractions of polytopes, 2016, arXiv:1611.07354, https://arxiv.org/abs/1611.07354
19. Laura Sanità, The diameter of the fractional matching polytope and its hardness implications, 2018, arXiv:1806.03397, https://arxiv.org/abs/1806.03397
20. Daniel Dadush and Sophie Huiberts, A Friendly Smoothed Analysis of the Simplex Method, 2017, arXiv:1711.05667, https://arxiv.org/abs/1711.05667
21. Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava, A Spectral Approach to Polytope Diameter, 2021, arXiv:2101.12198, https://arxiv.org/abs/2101.12198
22. Volker Kaibel and Kirill Kukharenko, Polytope Extensions with Linear Diameters, 2023, arXiv:2307.05246, https://arxiv.org/abs/2307.05246
23. Xavier Allamigeon, Quentin Canu, and Pierre-Yves Strub, A Formal Disproof of the Hirsch Conjecture, 2023, arXiv:2301.04060, https://arxiv.org/abs/2301.04060
24. Christian Nöbel and Raphael Steiner, Complexity of polytope diameters via perfect matchings, 2024, arXiv:2404.04158, https://arxiv.org/abs/2404.04158
25. Alex Davies, Prateek Gupta, Sebastien Racaniere, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, and Geordie Williamson, Drums of high width, 2025, arXiv:2503.09919, https://arxiv.org/abs/2503.09919
26. Grzegorz Swirszcz, Adam Zsolt Wagner, Geordie Williamson, Sam Blackwell, Bogdan Georgiev, Alex Davies, Ali Eslami, Sebastien Racaniere, Theophane Weber, and Pushmeet Kohli, Advancing Geometry with AI: Multi-agent Generation of Polytopes, 2025, arXiv:2502.05199, https://arxiv.org/abs/2502.05199
27. Bento Natura, Circuit Diameter of Polyhedra is Strongly Polynomial, 2026, arXiv:2602.06958, https://arxiv.org/abs/2602.06958
28. Alexander E. Black and Lei Xue, Any Proof of Polynomial Hirsch Must be Completely Incoherent, 2026, arXiv:2607.11628, https://arxiv.org/abs/2607.11628
29. Stefan Glock, Olaf Parczyk, Silas Rathke, and Tibor Szabó, The maximum diameter of d-dimensional simplicial complexes, 2026, arXiv:2602.20890, https://arxiv.org/abs/2602.20890