A counter-example to the Hirsch conjecture

Francisco Santos
University of Cantabria

The Hirsch conjecture, stated in 1957, said that if a polyhedron is defined by $n$ linear inequalities in $d$ variables then its combinatorial diameter should be at most $n-d$. That is, it should be possible to travel from any vertex to any other vertex in at most $n-d$ steps (traversing an edge at each step). The unbounded case was disproved by Klee and Walkup in 1967. In this talk I describe my construction of counter-examples to the bounded case (polytopes). The smallest counter-example so far has dimension 23 and 46 facets, and is obtained by a lifting and perturbation argument from a 5-dimensional polytope with 28 facets. The conjecture was posed and is relevant in the context of the simplex method in linear programming.

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?