Abstract: 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 the first counter-examples to the bounded case (polytopes).

The conjecture was posed and is relevant in connection to linear programming since the simplex method, one of the mathematical algorithms with the greatest impact in science and engineering, solves linear programming problems by traversing the graph of the feasibility polyhedron. In the first half of the talk will explain this connection.

This talk will be accessible to graduate students.