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.
Copyright. All Rights Reserved.