Prof. Francisco Santos, Ph.D.
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 Santos (2010) 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 we review the motivation for the Hirsch Conjecture, related to the complexity of the simplex method, we describe our constructions of counter-examples to it, and 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 nothing but “normal pseudo-manifolds”, but it is still (or again) an active area of research.
Datum: 07.04.2016, Raum: G03-106, Zeit: 17:00