Obstructions to weak decomposability for simplicial polytopes
HTML articles powered by AMS MathViewer
- by Nicolai Hähnle, Steven Klee and Vincent Pilaud PDF
- Proc. Amer. Math. Soc. 142 (2014), 3249-3257 Request permission
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
- M. L. Balinski, On two special classes of transportation polytopes, Math. Programming Stud. 1 (1974), 43–58. Pivoting and extensions. MR 478012, DOI 10.1007/bfb0121240
- David Barnette, An upper bound for the diameter of a polytope, Discrete Math. 10 (1974), 9–13. MR 355826, DOI 10.1016/0012-365X(74)90016-8
- M. L. Balinski and Fred J. Rispoli, Signature classes of transportation polytopes, Math. Programming 60 (1993), no. 2, Ser. A, 127–144. MR 1239594, DOI 10.1007/BF01580606
- 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, DOI 10.1007/s00493-006-0010-5
- 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.
- 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, DOI 10.1287/moor.1120.0554
- 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, DOI 10.1007/s00454-008-9096-4
- 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, DOI 10.1287/moor.1100.0470
- G. Kalai. Polymath 3: The Polynomial Hirsch Conjecture, 2010. http://gilkalai. wordpress.com.
- 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
- Victor Klee and Peter Kleinschmidt, The $d$-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718–755. MR 913867, DOI 10.1287/moor.12.4.718
- 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, DOI 10.1090/S0273-0979-1992-00285-9
- Edward D. Kim and Francisco Santos, An update on the Hirsch conjecture, Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73–98. MR 2681516, DOI 10.1365/s13291-010-0001-8
- Victor Klee and Christoph Witzgall, Facets and vertices of transportation polytopes, Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 257–282. MR 0235832
- D. G. Larman, Paths of polytopes, Proc. London Math. Soc. (3) 20 (1970), 161–178. MR 254735, DOI 10.1112/plms/s3-20.1.161
- E. R. Lockeberg, Refinements in boundary complexes of polytopes. Ph.D. thesis, University College London, 1977.
- B. Matschke, F. Santos, and C. Weibel, The width of 5-dimensional prismatoids. Preprint arXiv:1202.4701, 2012.
- 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, DOI 10.1287/moor.5.4.576
- Francisco Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2) 176 (2012), no. 1, 383–412. MR 2925387, DOI 10.4007/annals.2012.176.1.7
- 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, DOI 10.1007/s101070100261
- 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
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
- MR Author ID: 860480
- Email: vincent.pilaud@lix.polytechnique.fr
- 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
- © Copyright 2014 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 142 (2014), 3249-3257
- MSC (2010): Primary 52B12; Secondary 90C05, 05E45
- DOI: https://doi.org/10.1090/S0002-9939-2014-12101-0
- MathSciNet review: 3223380