Polynomial monotone Hirsch conjecture: does every polytope admit a polynomial-length monotone path once coherence fails?

For a convex polytope $P$ and a linear functional $c$, a monotone path is an edge path in the graph of $P$ along which $c$ strictly increases, from a vertex minimizing $c$ to a vertex maximizing $c$; such paths are exactly the trajectories available to the simplex method for linear programming. A monotone path is coherent if it arises as the sequence of optima of a parametric linear program $\max((w+\lambda c)^{\intercal}x)$ as the parameter $\lambda$ sweeps the real line. Black and Xue (2026) proved that coherence alone cannot yield short paths: for every $d\ge 3$ they construct a $(d+1)$-dimensional polytope with $(2d+1)(d+1)+1$ facets and an objective for which every coherent monotone path has length at least $2^{d-1}-1$, refuting the coherent analogue of the polynomial Hirsch conjecture. What their result leaves open is the polynomial monotone Hirsch conjecture in its source-to-sink form: is there a polynomial $p$, in the number of facets $n$ and the dimension $d$, that bounds the length of a shortest (not necessarily coherent) monotone path on every polytope for every admissible objective? The complementary refutation direction asks whether polytopes exist on which every monotone path — not just every coherent one — is exponentially long. No resolution in either direction is known: the linear monotone Hirsch conjecture is false (Todd 1980, for arbitrary starting vertices), the best general upper bound on the monotone diameter remains Kalai's subexponential-type bound, and the undirected polynomial Hirsch conjecture remains open with quasipolynomial upper bounds. The problem is open.

Background

A convex polytope is the bounded intersection of finitely many half-spaces; its standard size parameters are its dimension $d$ and its number of facets (codimension-one faces) $n$. The graph, or 1-skeleton, of a polytope has the vertices as nodes and the edges as arcs, and the combinatorial diameter is the maximum, over pairs of vertices, of the shortest graph distance between them. Hirsch's 1957 conjecture (posed in a letter to Dantzig and surveyed by Kim and Santos) asserted that every $d$-polytope with $n$ facets has diameter at most $n-d$; Santos disproved this in 2012. The surviving polynomial Hirsch conjecture asks only for some polynomial upper bound on the diameter in terms of $n$ and $d$. It remains open: the best upper bound is still quasipolynomial — $n^{2+\log_2 d}$ due to Kalai and Kleitman (1992), improved to $(n-d)^{\log_2 d}$ by Todd (2014, as documented in Sukegawa's account) and then to Sukegawa's $(n-d)^{\log_2 O(d/\log d)}$ (2019) — while the best lower bounds are only linear in $n-d$ (about $1.05(n-d)$ as reported by Black and Xue in 2026).

The diameter problem is motivated by the simplex method for linear programming, which traverses the graph of the feasible polytope while increasing a linear objective at each step. An edge path along which a linear functional $c$ strictly increases is called a monotone path. Call $c$ admissible if it is nonconstant on every edge; an admissible $c$ orients the graph acyclically with a unique source (a $c$-minimizing vertex) and a unique sink (a $c$-maximizing vertex). Several monotone strengthenings of Hirsch's bound have been studied. The monotone Hirsch conjecture — that from every starting vertex some monotone path to the optimum has length at most $n-d$ — is false: Todd (1980) disproved it already in dimension 4. The weaker strict monotone Hirsch conjecture, attributed to Ziegler, asks whether the source-to-sink distance in this orientation is at most $n-d$; it has been confirmed by exhaustive computation for $(d,n)=(4,9)$ and $(5,10)$ (Gallagher and Morris 2018) and remains open in general. In the polynomial regime nothing is known in either direction: as summarized by Blanchard, De Loera, and Louveaux (2021), the best general upper bound for the monotone diameter is Kalai's subexponential-type bound of $m^{2\sqrt{m}}$ for $m$ facets, which in particular also bounds source-to-sink monotone paths, and no family of polytopes with all monotone paths superpolynomially long is known.

A distinguished subclass of monotone paths comes from parametric optimization. A monotone path for the objective $c$ is coherent if it equals the sequence of optimal vertices of the parametric linear program $\max((w+\lambda c)^{\intercal}x)$ over $P$ as $\lambda$ ranges over the reals, for a suitable auxiliary objective $w$. Coherent monotone paths are precisely the vertices of the monotone path polytope, a special case of the fiber polytope construction of Billera and Sturmfels (1992), and Billera, Kapranov, and Sturmfels (1994) showed that the space of all monotone paths (a simplicial complex known from Baues' work in algebraic topology) deformation retracts onto the boundary of the monotone path polytope, so the coherent paths carry the topology of all monotone paths. Algorithmically, coherent paths are traced by the shadow simplex (parametric) method of Gass and Saaty, on which essentially all strongest positive analyses of path lengths on polytopes rest. Single exponentially long coherent monotone paths have been known since Zadeh's 1973 network-flow examples and in the deformed-product constructions of Amenta and Ziegler, but a polytope generally has exponentially many coherent paths, so one long path is weak evidence.

Black and Xue (2026) closed the coherent case. For each $d\ge 3$ they construct a $(d+1)$-dimensional polytope with $(2d+1)(d+1)+1$ facets and a linear objective such that every coherent monotone path has length at least $2^{d-1}-1$: not even the Kalai–Kleitman quasipolynomial bound survives within the coherent subclass. Their construction further implies that any polynomial-length monotone path on these polytopes must be superpolynomially many flips away from every coherent path (a flip moves between monotone paths agreeing outside one two-dimensional face), and yields distribution-independent exponential lower bounds for the semi-random shadow simplex method, for the number of simplices stabbed by a ray in a regular triangulation (a triangulation of a point configuration induced by a convex piecewise-linear lifting function, obtained here by slicing the normal fan of the constructed polytope), and for the number of parametric optima in one-parameter linear optimization. The coherent analogue of the polynomial Hirsch conjecture is thus refuted — and the question for general, non-coherent monotone paths becomes sharp, since coherence was the only systematic source of candidate short paths.

Problem Statement

Throughout, a polytope is a bounded intersection of finitely many half-spaces in a real vector space; its facets are its maximal proper faces, and its graph (1-skeleton) has the vertices as nodes and the edges (one-dimensional faces) as arcs. A linear functional $c$ is admissible for a polytope $P$ if it is nonconstant on every edge of $P$; an admissible $c$ orients the graph of $P$ acyclically, with a unique source, the $c$-minimizing vertex, and a unique sink, the $c$-maximizing vertex. A $c$-monotone path is an edge path along which $c$ strictly increases; its length is its number of edges. Let $\Delta_{sm}(d,n)$ denote the maximum, over all $d$-dimensional polytopes with $n$ facets and all admissible linear functionals $c$, of the length of a shortest $c$-monotone path from the $c$-minimizing vertex to the $c$-maximizing vertex. The polynomial monotone Hirsch conjecture (in the min-to-max form stated by Black and Xue, following the strict monotone Hirsch conjecture of Ziegler) asks:

Is there a polynomial $p$, in the number of facets $n$ and the dimension $d$, such that $\Delta_{sm}(d,n)\le p(n,d)$ for all $n>d\ge 1$? Equivalently, does every polytope, for every admissible linear objective, admit at least one monotone path — possibly far from coherent — of polynomially bounded length from a minimizer to a maximizer?

The complementary refutation direction, the exact logical negation of the conjecture above, asks whether there exist, for unbounded dimension, polytopes and admissible objectives such that every monotone path from a minimizer to a maximizer is superpolynomially long (the stronger exponential form is the one Black and Xue realized for coherent paths). The coherent subclass — the paths arising as the sequence of optima of a parametric linear program — is settled negatively by the source paper, so what remains open is the general case of arbitrary monotone paths. A positive resolution would imply the polynomial Hirsch conjecture for the undirected combinatorial diameter (as stated in the source for the monotone variants), while a negative resolution would unconditionally rule out every polynomial-time monotone, pivot-based simplex method. Improving bounds on the undirected diameter alone, or on the coherent subclass alone, does not answer this question.

References

1. Alexander E. Black and Lei Xue, Any Proof of Polynomial Hirsch Must be Completely Incoherent, arXiv:2607.11628 (2026). DOI 10.48550/arxiv.2607.11628, https://arxiv.org/abs/2607.11628
2. Gil Kalai and 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, https://doi.org/10.1090/s0273-0979-1992-00285-9
3. Francisco Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics 176 (2012) 383-412. DOI 10.4007/annals.2012.176.1.7, https://doi.org/10.4007/annals.2012.176.1.7
4. Edward D. Kim and Francisco Santos, An update on the Hirsch conjecture, Jahresbericht der Deutschen Mathematiker-Vereinigung 112 (2010) 73-98. DOI 10.1365/s13291-010-0001-8, arXiv:0907.1186, https://doi.org/10.1365/s13291-010-0001-8
5. Michael J. Todd, The monotonic bounded Hirsch conjecture is false for dimension at least 4, Mathematics of Operations Research 5 (1980) 599-601. DOI 10.1287/moor.5.4.599, https://doi.org/10.1287/moor.5.4.599
6. Gil 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. Louis J. Billera and Bernd Sturmfels, Fiber polytopes, Annals of Mathematics 135 (1992) 527-549. DOI 10.2307/2946575, https://doi.org/10.2307/2946575
8. L. J. Billera, M. M. Kapranov, and B. Sturmfels, Cellular strings on polytopes, Proceedings of the American Mathematical Society 122 (1994) 549-555. DOI 10.1090/S0002-9939-1994-1205482-0, https://doi.org/10.1090/S0002-9939-1994-1205482-0
9. Nina Amenta and Günter M. Ziegler, Deformed products and maximal shadows of polytopes, Contemporary Mathematics 223 (1999) 57-90. DOI 10.1090/conm/223/03132, https://doi.org/10.1090/conm/223/03132
10. Norman Zadeh, A bad network problem for the simplex method and other minimum cost flow algorithms, Mathematical Programming 5 (1973) 255-266. DOI 10.1007/bf01580132, https://doi.org/10.1007/bf01580132
11. Günter M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995. DOI 10.1007/978-1-4613-8431-1, https://doi.org/10.1007/978-1-4613-8431-1
12. Moïse Blanchard, Jesús A. De Loera, and Quentin Louveaux, On the Length of Monotone Paths in Polyhedra, SIAM Journal on Discrete Mathematics 35 (2021) 1746-1768. DOI 10.1137/20m1315646, arXiv:2001.09575, https://arxiv.org/abs/2001.09575
13. J. Mackenzie Gallagher and Walter D. Morris, Jr., A Proof of the Strict Monotone 5-step Conjecture, arXiv:1806.03403 (2018), https://arxiv.org/abs/1806.03403
14. 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
15. Bento Natura, Circuit Diameter of Polyhedra is Strongly Polynomial, arXiv:2602.06958 (2026), https://arxiv.org/abs/2602.06958
16. Alexander E. Black and Raphael Steiner, Finding Short Paths on Simple Polytopes, arXiv:2603.05482 (2026), https://arxiv.org/abs/2603.05482
17. 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, arXiv:2502.05199 (2025), https://arxiv.org/abs/2502.05199
18. Saul Gass and Thomas Saaty, The computational algorithm for the parametric objective function, Naval Research Logistics Quarterly 2 (1955) 39-45. DOI 10.1002/nav.3800020106, https://doi.org/10.1002/nav.3800020106