Remote Access Proceedings of the American Mathematical Society
Green Open Access

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?)

  • [Bal74] M. L. Balinski, On two special classes of transportation polytopes, Pivoting and extensions, Math. Programming Stud. 1 (1974), 43-58. MR 0478012 (57 #17508)
  • [Bar74] David Barnette, An upper bound for the diameter of a polytope, Discrete Math. 10 (1974), 9-13. MR 0355826 (50 #8300)
  • [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 (94h:90037),
  • [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 (2008c:90052),
  • [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
  • [DTZ09] Antoine Deza, Tamás Terlaky, and Yuriy Zinchenko, A continuous $ d$-step conjecture for polytopes, Discrete Comput. Geom. 41 (2009), no. 2, 318-327. MR 2471877 (2010e:52022),
  • [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 (2012b:52020),
  • [Kal10] G. Kalai.
    Polymath 3: The Polynomial Hirsch Conjecture, 2010. http://gilkalai.
  • [Kim10] Edward Dong Huhn Kim, Geometric combinatorics of transportation polytopes and the behavior of the simplex method, Thesis (Ph.D.)-University of California, Davis, 2010. ProQuest LLC, Ann Arbor, MI. MR 2941616
  • [KK87] Victor Klee and Peter Kleinschmidt, The $ d$-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718-755. MR 913867 (89a:52018),
  • [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 (92h:52017),
  • [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 (2011f:52014),
  • [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 (38 #4134)
  • [Lar70] D. G. Larman, Paths of polytopes, Proc. London Math. Soc. (3) 20 (1970), 161-178. MR 0254735 (40 #7942)
  • [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 (82c:52010),
  • [San12] F. Santos,
    A counterexample to the Hirsch conjecture,
    Ann. of Math. (2) 176 (2012), no. 1, 383-412. MR 2925387
  • [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,
  • [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 (85b:52008)

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

American Mathematical Society