Topological prismatoids and small simplicial spheres of large diameter

DOI10.1080/10586458.2019.1641766MaRDI QIDQ5094480zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 3 August 2022

Published in Experimental Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(3)

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

Describes a project that uses

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)