Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)



Obstructions to weak decomposability for simplicial polytopes

Authors: Nicolai Hähnle, Steven Klee and Vincent Pilaud
Journal: Proc. Amer. Math. Soc. 142 (2014), 3249-3257
MSC (2010): Primary 52B12; Secondary 90C05, 05E45
Published electronically: June 10, 2014
MathSciNet review: 3223380
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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(\sqrt {d})$-decomposable. As a consequence, (weak) decomposability cannot be used to prove a polynomial version of the Hirsch Conjecture.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 52B12, 90C05, 05E45

Retrieve articles in all journals with MSC (2010): 52B12, 90C05, 05E45

Additional Information

Nicolai Hähnle
Affiliation: Institut für Mathematik, Technische Universität Berlin, Strasse des 17.Juni 136, 10623 Berlin, Germany
Address at time of publication: Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany

Steven Klee
Affiliation: Department of Mathematics, Seattle University, 901 12th Avenue, Seattle, Washington 98122

Vincent Pilaud
Affiliation: CNRS and LIX, École Polytechnique, 91128 Palaiseau, France

Received by editor(s): July 9, 2012
Received by editor(s) in revised form: October 6, 2012
Published electronically: June 10, 2014
Additional Notes: The second author was partially supported by NSF VIGRE grant DMS-0636297 during his time at UC Davis
The third author was partially supported by grant MTM2011-22792 of the Spanish Ministerio de Ciencia e Innovación and by European Research Project ExploreMaps (ERC StG 208471).
Communicated by: Jim Haglund
Article copyright: © Copyright 2014 American Mathematical Society