2014/12/18 by J. Mackenzie Gallagher, Gallagher, J. Mackenzie, Edward D. Kim +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.1412.5691
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+log2d. 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.