Discrete Geometry and Combinatorics Seminar
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.