Topological Prismatoids and Small Simplicial Spheres of Large Diameter

Abstract

We introduce topological prismatoids, a combinatorial abstraction of the (geometric) prismatoids recently introduced by the second author to construct counter-examples to the Hirsch conjecture. We show that the “strong d-step Theorem” that allows to construct such large-diameter polytopes from “non-d-step” prismatoids still works at this combinatorial level. Then, using metaheuristic methods on the flip graph, we construct four combinatorially different non-d-step 4-dimensional topological prismatoids with 14 vertices. This implies the existence of 8-dimensional spheres with 18 vertices whose combinatorial diameter exceeds the Hirsch bound. These examples are smaller that the previously known examples by Mani and Walkup in 1980 (24 vertices, dimension 11). Our non-Hirsch spheres are shellable but we do not know whether they are realizable as polytopes.

Keywords:

• simplicial complex
• simplicial sphere
• combinatorial diameter
• Hirsch conjecture

2000 Mathematics Subject Classification:

• 52B05
• 52B12
• 90C60
• 90C05

Acknowledgements

We thank Mortitz Firsching and Michael Joswig for useful discussions and comments.

Additional information

Funding

This work is supported by project MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE) and grant EVF-2015-230 of the Einstein Foundation Berlin. Work of F. Criado is supported by the Berlin Mathematical School.