The Hirsch Conjecture is false

You need to know: d-dimensional polytope, its vertices, edges, and facets.

Background: A (combinatorial) diameter of a polytope is the maximum number of steps needed to go from one vertex to another, where a step consists in traversing an edge.

The Theorem: On 14th June 2010, Francisco Santos submitted to arxiv a paper in which he proved the existence of a 43-dimensional polytope with 86 facets and diameter at least 44.

Short context: In 1957, Hirsch conjectured that d-dimensional polytope with n facets cannot have diameter greater than . The conjecture has applications to the complexity of the simplex method for linear programming. It was well-believed and proved in some special cases. Because , the Theorem provides a counterexample to this conjecture.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems