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 -dimensional polytopes are not even weakly -decomposable. As a consequence, (weak) decomposability cannot be used to prove a polynomial version of the Hirsch Conjecture.

**[Bal74]**M. L. Balinski,*On two special classes of transportation polytopes*, Math. Programming Stud.**1**(1974), 43–58. Pivoting and extensions. MR**0478012****[Bar74]**David Barnette,*An upper bound for the diameter of a polytope*, Discrete Math.**10**(1974), 9–13. MR**0355826****[BR93]**M. L. Balinski and Fred J. Rispoli,*Signature classes of transportation polytopes*, Math. Programming**60**(1993), no. 2, Ser. A, 127–144. MR**1239594**, 10.1007/BF01580606**[BvdHS06]**Graham Brightwell, Jan van den Heuvel, and Leen Stougie,*A linear bound on the diameter of the transportation polytope*, Combinatorica**26**(2006), no. 2, 133–139. MR**2223631**, 10.1007/s00493-006-0010-5- [DL11]
J. A. De Loera,
*New insights into the complexity and geometry of linear optimization*,

Optima, newsletter of the Mathematical Optimization Society**87**(2011), 1-13. **[DLK12]**Jesús A. De Loera and Steven Klee,*Transportation problems and simplicial polytopes that are not weakly vertex-decomposable*, Math. Oper. Res.**37**(2012), no. 4, 670–674. MR**2997897**, 10.1287/moor.1120.0554**[DTZ09]**Antoine Deza, Tamás Terlaky, and Yuriy Zinchenko,*A continuous 𝑑-step conjecture for polytopes*, Discrete Comput. Geom.**41**(2009), no. 2, 318–327. MR**2471877**, 10.1007/s00454-008-9096-4**[EHRR10]**Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß,*Diameter of polyhedra: limits of abstraction*, Math. Oper. Res.**35**(2010), no. 4, 786–794. MR**2777514**, 10.1287/moor.1100.0470- [Kal10]
G. Kalai.

Polymath 3: The Polynomial Hirsch Conjecture, 2010.`http://gilkalai.``wordpress.com`. **[Kim10]**Edward Dong Huhn Kim,*Geometric combinatorics of transportation polytopes and the behavior of the simplex method*, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–University of California, Davis. MR**2941616****[KK87]**Victor Klee and Peter Kleinschmidt,*The 𝑑-step conjecture and its relatives*, Math. Oper. Res.**12**(1987), no. 4, 718–755. MR**913867**, 10.1287/moor.12.4.718**[KK92]**Gil Kalai and Daniel J. Kleitman,*A quasi-polynomial bound for the diameter of graphs of polyhedra*, Bull. Amer. Math. Soc. (N.S.)**26**(1992), no. 2, 315–316. MR**1130448**, 10.1090/S0273-0979-1992-00285-9**[KS10]**Edward D. Kim and Francisco Santos,*An update on the Hirsch conjecture*, Jahresber. Dtsch. Math.-Ver.**112**(2010), no. 2, 73–98. MR**2681516**, 10.1365/s13291-010-0001-8**[KW68]**Victor Klee and Christoph Witzgall,*Facets and vertices of transportation polytopes*, Mathematics of the Decision Sciences, Part I (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 257–282. MR**0235832****[Lar70]**D. G. Larman,*Paths of polytopes*, Proc. London Math. Soc. (3)**20**(1970), 161–178. MR**0254735**- [Loc77]
E. R. Lockeberg,
*Refinements in boundary complexes of polytopes*.

Ph.D. thesis, University College London, 1977. - [MSW12]
B. Matschke, F. Santos, and C. Weibel,
*The width of 5-dimensional prismatoids*.

Preprint`arXiv:1202.4701`, 2012. **[PB80]**J. Scott Provan and Louis J. Billera,*Decompositions of simplicial complexes related to diameters of convex polyhedra*, Math. Oper. Res.**5**(1980), no. 4, 576–594. MR**593648**, 10.1287/moor.5.4.576- [San12]
Francisco
Santos,
*A counterexample to the Hirsch conjecture*, Ann. of Math. (2)**176**(2012), no. 1, 383–412. MR**2925387**, 10.4007/annals.2012.176.1.7 **[Tod02]**Michael J. Todd,*The many facets of linear programming*, Math. Program.**91**(2002), no. 3, Ser. B, 417–436. ISMP 2000, Part 1 (Atlanta, GA). MR**1888985**, 10.1007/s101070100261**[YKK84]**V. A. Yemelichev, M. M. Kovalëv, and M. K. Kravtsov,*Polytopes, graphs and optimisation*, Cambridge University Press, Cambridge, 1984. Translated from the Russian by G. H. Lawden. MR**744197**

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

Email:
haehnle@or.uni-bonn.de

**Steven Klee**

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

Email:
klees@seattleu.edu

**Vincent Pilaud**

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

Email:
vincent.pilaud@lix.polytechnique.fr

DOI:
http://dx.doi.org/10.1090/S0002-9939-2014-12101-0

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