An improved Kalai-Kleitman bound for the diameter of a polyhedron

Abstract

Kalai and Kleitman established the bound $n^{\log (d)+2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d{)}^{\log (d)}$.

4 pages

Cited by in corpus (1)

• An improved upper bound on the diameters of subset partition graphs