Hirsch conjecture
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch [es] to George B. Dantzig in 1957[1][2] and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method.
The Hirsch conjecture was proven for d < 4 and for various special cases,[3] while the best known upper bounds on the diameter are only sub-exponential in n and d.[4] After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, from the University of Cantabria.
[5][6][7] The result was presented at the conference 100 Years in Seattle: the mathematics of Klee and Grünbaum and appeared in Annals of Mathematics.
[8] Specifically, the paper presented a 43-dimensional polytope of 86 facets with a diameter of more than 43.
The counterexample has no direct consequences for the analysis of the simplex method, as it does not rule out the possibility of a larger but still linear or polynomial number of steps.
Various equivalent formulations of the problem had been given, such as the d-step conjecture, which states that the diameter of any 2d-facet polytope in d-dimensional Euclidean space is no more than d; Santos Leal's counterexample also disproves this conjecture.
The Hirsch conjecture then indicates that the diameter of this cube cannot be greater than three.
[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
For example, any polytope with dimension 3 or lower satisfies the conjecture.
[10] Other attempts to solve the conjecture manifested out of a desire to formulate a different problem whose solution would imply the Hirsch conjecture.
Theorem The following statements are equivalent: 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.
[10] 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.
for which there exist a pair of distinct vertices such that every facet of
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.
This counterexample does not disprove the polynomial Hirsch conjecture, which remains an open problem.
