Discrete Geometry and Combinatorics Seminar

Mike ToddCornell University
An improved Kalai-Kleitman bound on the diameter of polyhedra

Monday, March 24, 2014 - 2:30pm
Malott 206

We show that the diameter of a $d$-polyhedron with $n$ facets is at most $(n-d)^{\log(d)}$, improving the Kalai-Kleitman bound of $n^{\log(d)+1}$. The new bound is more closely related to the (false) Hirsch bound of $n-d$, and is symmetric between the polyhedron of a linear programming problem and that of its dual. Time permitting, we will also discuss some results of Eisenbrand et al., Kim, and Santos on the diameters of various set families abstracting the vertex-facet incidences of convex polyhedra or polytopes.