Polynomial bounds for the graph diameter of polytopes
Let $d \ge 1$ and let $P \subset \mathbb{R}^d$ be a convex polytope with nonempty interior and exactly $n$ facets, so that $n \ge d + 1$. Let $\operatorname{diam} G(P)$ be the diameter of its graph: the largest, over pairs of vertices of $P$, of the least number of edges of $P$ in a path joining them. Hirsch conjectured that $\operatorname{diam} G(P) \le n - d$. Santos disproved this with a $43$-dimensional polytope with $86$ facets and diameter at least $44$, and gave an infinite family of polytopes of a fixed dimension whose diameters exceed $(1 + \epsilon) n$ for a fixed $\epsilon > 0$. Kalai and Kleitman proved the quasi-polynomial bound $\operatorname{diam} G(P) \le n^{\log_2 d + 2}$, which Todd improved to $(n - d)^{\log_2 d}$.
Problem. Are there absolute constants $C, k > 0$ such that $$\operatorname{diam} G(P) \le C (n + d)^k$$ for every $d \ge 1$ and every such polytope $P$? The polytope need not be simple or rational, and paths may traverse edges in either direction.
Source: The polynomial Hirsch conjecture, as in Santos (2012), Conjecture 1.3: a weakening of the Hirsch conjecture (Hirsch, 1957, published by Dantzig (1963)). Stated with a bound in n + d by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG, OC
- Keywords
- AIM Open Applied Problems, convex polytopes, graph diameter, Hirsch conjecture
References
@article{santos2012,
author = {Santos, Francisco},
title = {A counterexample to the {H}irsch conjecture},
journal = {Ann. of Math. (2)},
volume = {176},
number = {1},
year = {2012},
pages = {383--412},
doi = {10.4007/annals.2012.176.1.7},
eprint = {1006.2814},
archivePrefix = {arXiv},
}
@book{dantzig1963,
author = {Dantzig, George B.},
title = {Linear Programming and Extensions},
publisher = {Princeton University Press},
address = {Princeton, NJ},
year = {1963},
}
@article{kalai1992,
author = {Kalai, Gil and Kleitman, Daniel J.},
title = {A quasi-polynomial bound for the diameter of graphs of polyhedra},
journal = {Bull. Amer. Math. Soc. (N.S.)},
volume = {26},
number = {2},
year = {1992},
pages = {315--316},
doi = {10.1090/S0273-0979-1992-00285-9},
eprint = {math/9204233},
archivePrefix = {arXiv},
}
@article{todd2014,
author = {Todd, Michael J.},
title = {An improved {K}alai--{K}leitman bound for the diameter of a polyhedron},
journal = {SIAM J. Discrete Math.},
volume = {28},
number = {4},
year = {2014},
pages = {1944--1947},
doi = {10.1137/140962310},
eprint = {1402.3579},
archivePrefix = {arXiv},
}
@misc{aim-polynomial-hirsch,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial bounds for the graph diameter of polytopes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/311-polynomial-hirsch.md},
note = {Entry 311 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00891, "Polynomial bounds for the graph diameter of polytopes", clopen.solutions.