Tutte seminar - Nicolai Hahnle

The Delta-ball game and the polynomial Hirsch conjecture

Abstract:

The polynomial Hirsch conjecture, motivated by empirical observations in linear programming, is one of the fundamental open problems in the study of polyhedra. It states that the diameter of the (vertex-edge)-graph of any d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. The best known upper bound is n^{1 + log d} (due to Kalai and Kleitman), while the best known lower bound construction has a diameter of (1 + epsilon) n for a fixed epsilon > 0 (due to Santos). I will present some recent results, both positive and negative, on approaches for proving new upper bounds on the giameter. We conjecture that the diameter is bounded by d(n-1) in a specific combinatorial relaxation of the problem. Francisco Santos recently proposed a related solitaire game played on a simplicial grid called a "Delta ball". The game proceeds in rounds. The player must select grid points in each round, while nature forbids grid points after each round according to a fixed rule. The player loses once all grid points are forbidden and no further moves are possible. The player's goal is to remain alive as long as possible. I will explain the rules of the game in detail and illustrate how it relates to the diameter problem.