An improved upper bound on the diameters of subset partition graphs

Abstract

In 1992, Kalai and Kleitman proved the first subexponential upper bound for the diameters of convex polyhedra. Eisenbrand et al. proved this bound holds for connected layer families, a novel approach to analyzing polytope diameters. Very recently, Todd improved the Kalai-Kleitman bound for polyhedra to $(n-d{)}^{1+{\log }_{2}d}$. In this note, we prove an analogous upper bound on the diameters of subset partition graphs satisfying a property related to the connectivity property of connected layer families.

6 pages

References in corpus (2)

• Constructing subset partition graphs with strong adjacency and end-point count properties
• An improved Kalai-Kleitman bound for the diameter of a polyhedron