Speaker: Francisco Santos
Title: 50 years of the Hirsch conjecture
The Hirsch conjecture was stated in 1957 in a letter from Warren M.
Hirsch
to George Dantzig. It states that the graph of a $d$-polytope with $n$
facets
cannot have diameter greater than $n - d$.
Despite being one of the most fundamental, basic and old problems in
polytope theory, what we know is quite scarce. Most notably, no
polynomial
upper bound is known for the diameters of polytopes. In contrast, very
few polytopes
are known where the bound $n-d$ is attained (basically one, apart from
trivial examples
and polytopes constructed from it). In this talk we will have a look
at the conjecture
focusing on "partial counterexamples".