The width of 5-dimensional prismatoids

Abstract

Santos' construction of counter-examples to the Hirsch Conjecture (2012) is based on the existence of prismatoids of dimension d of width greater than d. Santos, Stephen and Thomas (2012) have shown that this cannot occur in $d\le 4$. Motivated by this we here study the width of 5-dimensional prismatoids, obtaining the following results: - There are 5-prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to non-Hirsch polytopes of dimension 20, rather than the original dimension 43. - There are 5-prismatoids with $n$ vertices and width $\Omega (\sqrt{n})$ for arbitrarily large $n$. Hence, the width of 5-prismatoids is unbounded.

31 pages, 10 figures. Changes from v1: the introduction has been edited, and a minor correction made in the statement of Proposition 1.5

References in corpus (2)

• A counterexample to the Hirsch conjecture
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

Cited by in corpus (6)

• Improving bounds on the diameter of a polyhedron in high dimensions
• Hirsch polytopes with exponentially long combinatorial segments
• Topological Prismatoids and Small Simplicial Spheres of Large Diameter
• Tail diameter upper bounds for polytopes and polyhedra
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• Obstructions to weak decomposability for simplicial polytopes