Bounds on the diameters of rr-stacked and kk-neighborly polytopes

preprint2013arXivOpen access

Abstract

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 rr, then the diameter of the facet-ridge graph of ΔΔ is not larger than 2r−2n2^{r-2}n, where nn 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 kk-neighborly spheres, rr-stacked spheres, and polytopes with small grg_r. Specifically, our bounds imply that rr-stacked spheres with r=O(log⁡n)r=O(\log n) satisfy the polynomial Hirsch conjecture.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.