Counter-examples to the Hirsch conjecture
Introduction
The Hirsch conjecture stated that for any d-dimensional polytope defined by n inequalities, there would be a path of length no more than (n-d) edges between any two vertices of the polytope.
The Hirsch conjecture had some important implications on Linear Programming, as the length of the path gives a lower bound on the complexity of the simplex method. The conjecture has remained open for more than 50 years, and was finally disproven in 2010 by Paco Santos, who proved that there exists a 43-dimensional polytope defined by 86 inequalities, such that a particular pair of vertices could only be connected by paths of length at least 44.
In fact, Paco Santos solved the dual problem of finding a d-dimensional polytope of n vertices such that in the adjacency graph of the facets of the polytope, some two facets would not be connected by a path of length (n-d) or less. He proved that this can be attained by prismatoids, which are polytopes where two parallel facets (called bases) cover all vertices.
What Paco Santos proved is that if we find a d-dimensional prismatoid of n vertices (with n>2d), such that its width (the distance between the two parallel facets in the facet adjacency graph) is more than d, then we can modify it into another prismatoid, (d+1)-dimensional, with n+1 vertices, and a width of more than d+1. By doing this n-2d times, we get a prismatoid of dimension n-d, with 2n-2d vertices, and a width of more than n-d. The dual of this polytope is then a counter-example to the Hirsch conjecture.
Paco Santos also found a 5-dimensional polytope of 48 vertices with a width of 6, which leads to a 43-dimensional counter-example with 86 vertices, and a width of 47.