Bounds on the diameters of r-stacked and k-neighborly polytopes

Original · EN

We improve Larman's bound on the diameter of a polytope by showing that if Δ is a normal simplicial complex, all of whose missing faces have size at most r, then the diameter of the facet-ridge graph of Δ is not larger than 2ʳ⁻²n, where n is the number of vertices of Δ. We then use this result to provide new upper bounds on the diameters of the facet-ridge graphs of k-neighborly spheres, r-stacked spheres, and polytopes with small gᵣ. Specifically, our bounds imply that r-stacked spheres with r=O(n) satisfy the polynomial Hirsch conjecture.