Joint Pure Mathematics and Combinatorics & Optimization Colloquium

 Patrick Dornian, Combinatorics and Optimization, University of Waterloo

"Disproving the Hirsch Conjecture"

In 1957, Warren M. Hirsch suggested that a d-dimensional polytope with n facets could not have combinatorial diameter greater than n - d. That is, given any two vertices of the polytope one may reach one from the other by walking along a maximum of n - d edges (Or in the words of graph theory, the diameter of the polytope's edge-vertex graph is at most n-d) . This implies a lower bound on the runtime of the simplex algorithm, as well as providing a nice topological characterization of polytopes themselves. It remained a well known open problem in polyhedral combinatorics for over 50 years, until a counterexample was presented by Francisco Santos in 2010. We will examine a brief history of the problem, and then sketch out Santos' construction by replacing most of the hard math with pretty pictures and hand waving.