Speaker : Michel Goemans

Title : The diameter of polytopes, the Hirsch conjecture, and related combinatorial and algorithmic questions.

Abstract : The Hirsch conjecture, postulated in 1957, states that the diameter of the skeleton of any d-dimensional polytope with n facets is at most n-d. Although disproved more than 50 years later by Santos, many variants and weakenings of the conjecture are still unsolved, including the polynomial version of the conjecture stating that the diameter is bounded by a polynomial in n. The conjecture is also related to the complexity of the simplex method for linear programming, a major open question. In this talk, I will present several variants of the conjecture, a few results, and motivate the important of these questions from both a combinatorial and algorithmic point-of-view.

Reception following talk in room 2-290!