Obstructions to weak decomposability for simplicial polytopes

DOI10.1090/S0002-9939-2014-12101-0MaRDI QIDQ3190213zbMATH OpenOpenAlexFDO

Authors Nicolai Hähnle, Steven Klee, Vincent Pilaud

Publication date 16 September 2014

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

(weak) decomposabilitysimplicial polytopes

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Abstract: Provan and Billera introduced notions of (weak) decomposability of simplicial complexes as a means of attempting to prove polynomial upper bounds on the diameter of the facet-ridge graph of a simplicial polytope. Recently, De Loera and Klee provided the first examples of simplicial polytopes that are not weakly vertex-decomposable. These polytopes are polar to certain simple transportation polytopes. In this paper, we refine their analysis to prove that these $d$-dimensional polytopes are not even weakly $O(sqrtd)$-decomposable. As a consequence, (weak) decomposability cannot be used to prove a polynomial version of the Hirsch conjecture.

Recommendations

• Simplicial decomposability
• scientific article; zbMATH DE number 3884983
• A combinatorial decomposition of simplicial complexes
• Equidecomposable and weakly neighborly polytopes
• An Obstacle to a Decomposition Theorem for Near-Regular Matroids
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• A combinatorial decomposition of acyclic simplicial complexes
• Decomposability of polytopes
• scientific article; zbMATH DE number 5542507
• On decomposing suspensions of simplicial spaces

Cites work

• A continuous d-step conjecture for polytopes
• A counterexample to the Hirsch conjecture
• A linear bound on the diameter of the transportation polytope
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An update on the Hirsch conjecture
• An upper bound for the diameter of a polytope
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• Diameter of polyhedra: limits of abstraction
• Paths on Polytopes
• Signature classes of transportation polytopes
• The d-Step Conjecture and Its Relatives
• The many facets of linear programming
• The width of five-dimensional prismatoids
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable

Cited in

(2)

• A decomposition of 2-weak vertex-packing polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes

This page was built for publication: Obstructions to weak decomposability for simplicial polytopes

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