Hirsch conjecture

The graph of a convex polytope ${\displaystyle P}$ is any graph whose vertices are in bijection with the vertices of ${\displaystyle P}$ in such a way that any two vertices of the graph are joined by an edge if and only if the two corresponding vertices of ${\displaystyle P}$ are joined by an edge of the polytope. The diameter of ${\displaystyle P}$, denoted ${\displaystyle \delta (P)}$, is the diameter of any one of its graphs. These definitions are well-defined since any two graphs of the same polytope must be isomorphic as graphs. We may then state the Hirsch conjecture as follows:

Conjecture Let ${\displaystyle P}$ be a d-dimensional convex polytope with n facets. Then ${\displaystyle \delta (P)\leq n-d}$.

For example, a cube in three dimensions has six facets. The Hirsch conjecture then indicates that the diameter of this cube cannot be greater than three. Accepting the conjecture would imply that any two vertices of the cube may be connected by a path from vertex to vertex using, at most, three steps. For all polytopes of dimension at least 8, this bound is actually optimal; no polytope of dimension ${\displaystyle d\geq 8}$ has a diameter less than n-d, with n being the number of its facets, as before.[10] In other words, for nearly all cases, the conjecture provides the minimum number of steps needed to join any two vertices of a polytope by a path along its edges. Since the simplex method essentially operates by constructing a path from some vertex of the feasible region to an optimal point, the Hirsch conjecture would provide a lower bound needed for the simplex method to terminate in the worst-case scenario.

The Hirsch conjecture is a special case of the polynomial Hirsch conjecture, which claims that there exists some positive integer k such that, for all polytopes ${\displaystyle P}$, ${\displaystyle \delta (P)=O(n^{k})}$, where n is the number of facets of P.

The Hirsch conjecture has been proven true for a number of cases. For example, any polytope with dimension 3 or lower satisfies the conjecture. Any d-dimensional polytope with n facets such that ${\displaystyle n-d\leq 6}$ satisfies the conjecture as well.[10]

Other attempts to solve the conjecture manifested out of a desire to formulate a different problem whose solution would imply the Hirsch conjecture. One example of particular importance is the d-step conjecture, a relaxation of the Hirsch conjecture that has actually been shown to be equivalent to it.

Theorem The following statements are equivalent:

1. ${\displaystyle \delta (P)\leq n-d}$ for all d-dimensional polytopes ${\displaystyle P}$ with n facets.
2. ${\displaystyle \delta (P)\leq d}$ for all d-dimensional polytopes ${\displaystyle P}$ with 2d facets.

In other words, in order to prove or disprove the Hirsch conjecture, one only needs to consider polytopes with exactly twice as many facets as its dimension. Another significant relaxation is that the Hirsch conjecture holds for all polytopes if and only if it holds for all simple polytopes.[10]

The octahedron is one of the most well-known examples of a spindle.

Unfortunately, the Hirsch conjecture is not true in all cases, as shown by Francisco Santos in 2011. Santos' explicit construction of a counterexample comes both from the fact that the conjecture may be relaxed to only consider simple polytopes, and from equivalence between the Hirsch and d-step conjectures.[8] In particular, Santos produces his counterexample by examining a particular class of polytopes called spindles.

Definition A d-spindle is a d-dimensional polytope ${\displaystyle P}$ for which there exist a pair of distinct vertices such that every facet of ${\displaystyle P}$ contains exactly one of these two vertices.

The length of the shortest path between these two vertices is called the length of the spindle. The disproof of the Hirsch conjecture relies on the following theorem, referred to as the strong d-step theorem for spindles.

Theorem (Santos) Let ${\displaystyle P}$ be a d-spindle. Let n be the number of its facets, and let l be its length. Then there exists an ${\displaystyle (n-d)}$-spindle, ${\displaystyle P'}$, with ${\displaystyle 2n-2d}$ facets and a length bounded below by ${\displaystyle l+n-2d}$. In particular, if ${\displaystyle l>d}$, then ${\displaystyle P'}$ violates the d-step conjecture.

Santos then proceeds to construct a 5-dimensional spindle with length 6, hence proving that there exists another spindle that serves as a counterexample to the Hirsch conjecture. The first of these two spindles has 48 facets and 322 vertices, while the spindle that actually disproves the conjecture has 86 facets and is 43-dimensional. This counterexample does not disprove the polynomial Hirsch conjecture, which remains an open problem.[8]

• Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
• Kalai, Gil (10 May 2010). "Francisco Santos Disproves the Hirsch Conjecture". Retrieved 11 May 2010.
• Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, 26 (2): 315–316, arXiv:math/9204233, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448, S2CID 37821778.
• Klee, Victor; Walkup, David W. (1967), "The d-step conjecture for polyhedra of dimension d < 6", Acta Mathematica, 133: 53–78, doi:10.1007/BF02395040, MR 0206823.
• Miranda, Eva (2012), "The Hirsch conjecture has been disproved: An interview with Francisco Santos" (PDF), Newsletter of the European Mathematical Society (86): 31–36.
• Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming, 45 (1): 109–110, doi:10.1007/BF01589099, MR 1017214, S2CID 24632864.
• Santos, Francisco (2011), "A counterexample to the Hirsch conjecture", Annals of Mathematics, Princeton University and Institute for Advanced Study, 176 (1): 383–412, arXiv:1006.2814, doi:10.4007/annals.2012.176.1.7, MR 2925387, S2CID 15325169
• Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 83–93.