Hirsch conjecture

The graph of a convex polytope P is any graph whose vertices are in bijection with the vertices of 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 P are joined by an edge of the polytope. The diameter of P, denoted \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: 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 d\geq 8 has a diameter less than n-d, with n being the number of its facets, as before. 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 P, \delta(P)=O(n^k), where n is the number of facets of P. == Progress and intermediate results ==

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 n-d\leq 6 satisfies the conjecture as well. 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: • \delta(P)\leq n-d for all d-dimensional polytopes P with n facets. • \delta(P)\leq d for all d-dimensional polytopes 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. == Counterexample ==

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 only to consider simple polytopes, and from the equivalence between the Hirsch and d-step conjectures. In particular, Santos produces his counterexample by examining a particular class of polytopes called spindles, defining a d-spindle is a d-dimensional polytope P for which there exist a pair of distinct vertices such that every facet of 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: 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. ==Notes==