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
tight.
Copyright. All Rights Reserved.