The Hirsch conjecture, posed in 1957, stated that the graph of a $d$-dimensional polytope or polyhedron with $n$ facets cannot have diameter greater than $n−d$ . The conjecture itself has been disproved by Klee-Walkup (1967) for unbounded polyhedra and by the speaker (2012) for bounded polytopes; but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the Hirsch bound by more than 25% is known.

In this talk I will (1) review the history and motivation for the Hirsch Conjecture, related to the complexity of the simplex method, (2) describe the constructions of counter-examples to it, and (3) report on other attempts and progress on the question, mostly those that try to answer the diameter question by generalizing it to the world of simplicial complexes. This approach has a long history, starting by Adler and Dantzig’s definition of “abstract polytopes” which are the same objects that combinatorial topologists now call “normal pseudo-manifolds”.