An abstract view on the polynomial Hirsch conjecture

Nicolai Hähnle
École Polytechnique Fédérale de Lausanne (EPFL)

The best known upper-bound on the diameter of polyhedra is the quasi-
polynomial bound due to Kalai and Kleitman. What properties of polyhedra make
this upper-bound work? What techniques could be useful in improving it? We
present a range of purely combinatorial abstractions of the graph of a
polyhedron as a way of understanding these questions better. We report on
recent developments in a collaborative online polymath project, and discuss a
potential attack on the polynomial Hirsch conjecture that has surfaced there,
which includes an abstraction in which the Kalai-Kleitman bound is essentially

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?