An improved upper bound on the diameters of subset partition graphs
arXiv:1412.5691
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 . 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.
arXiv comment6 pages
References in corpus (5)
- A counterexample to the Hirsch conjecture
- Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Constructing subset partition graphs with strong adjacency and end-point count properties
- An improved Kalai-Kleitman bound for the diameter of a polyhedron
- Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count