Math Conjectures

Polynomial Hirsch conjecture

OPENMajorConjectureProposed c. 1992 · Standard version

Canonical statement

There is a polynomial p∈R[X,Y]p\in\mathbb R[X,Y] such that, for all integers d≥1d\ge1, n≥d+1n\ge d+1, and every dd-dimensional convex polytope PP having exactly nn facets, the graph whose vertices and edges are the 00- and 11-dimensional faces of PP has diameter at most p(n,d)p(n,d).
View source LaTeX
There is a polynomial \(p\in\mathbb R[X,Y]\) such that, for all integers \(d\ge1\), \(n\ge d+1\), and every \(d\)-dimensional convex polytope \(P\) having exactly \(n\) facets, the graph whose vertices and edges are the \(0\)- and \(1\)-dimensional faces of \(P\) has diameter at most \(p(n,d)\).
OPT-003:[KalaiKleitman1992Diameter][Santos2012Hirsch][Todd2014Diameter]
Mathematical optimizationDiscrete geometry

Notes

The original Hirsch conjecture asserted that the vertex-edge graph of a dd-dimensional polytope with nn facets has diameter at most n−dn-d, a bound tied to how few steps an ideal simplex path could take. The surviving central question, the polynomial Hirsch conjecture, asks only whether the diameter is bounded by some fixed polynomial in nn and dd. This form became standard around 1992, when Kalai and Kleitman proved their quasipolynomial diameter bound [KalaiKleitman1992Diameter].

The linear bound itself is now known to fail: Santos constructed a polytope whose diameter exceeds n−dn-d [Santos2012Hirsch]. The violation is modest, however, and the known lower bounds on polytope diameters remain only linear. On the upper side, refinements of the Kalai–Kleitman argument, such as Todd's improved bound [Todd2014Diameter], are still quasipolynomial in the parameters.

The gulf between linear lower bounds and quasipolynomial upper bounds is essentially untouched: no polynomial upper bound has been proved and no superpolynomial-diameter polytope is known, so the conjecture is open in both directions.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.