Topological prismatoids and small simplicial spheres of large diameter

DOI10.1080/10586458.2019.1641766zbMATH Open1494.52007arXiv1807.03030OpenAlexW3103462803WikidataQ127453445 ScholiaQ127453445MaRDI QIDQ5094480FDOQ5094480

Authors:

Publication date: 3 August 2022

Published in: Experimental Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1807.03030

Recommendations

• The width of five-dimensional prismatoids
• More polytopes meeting the conjectured Hirsch bound
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• A counterexample to the Hirsch conjecture
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

zbMATH Keywords

simplicial complexcombinatorial diameterHirsch conjecturesimplicial sphere

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• polymake: a framework for analyzing convex polytopes
• More bounds on the diameters of convex polytopes
• P.l. homeomorphic manifolds are equivalent by elementary shellings
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Simplicial Manifolds, Bistellar Flips and a 16-Vertex Triangulation of the Poincaré Homology 3-Sphere
• A counterexample to the Hirsch conjecture
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Edge-graph diameter bounds for convex polytopes with few facets
• Paths on Polytopes
• The width of five-dimensional prismatoids
• Simplicial moves on balanced complexes
• A 3-Sphere Counterexample to the W_v-Path Conjecture
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• Randomized construction of complexes with large diameter
• Heuristics for sphere recognition

Cited In (3)

• The width of five-dimensional prismatoids
• Combining realization space models of polytopes
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

Uses Software

• polymake

This page was built for publication: Topological prismatoids and small simplicial spheres of large diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5094480)