Obstructions to weak decomposability for simplicial polytopes. (English) Zbl 1383.52015
Summary: 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.
MSC:
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
| 90C05 | Linear programming |
| 05E45 | Combinatorial aspects of simplicial complexes |
References:
| [1] | M. L. Balinski, On two special classes of transportation polytopes, Math. Programming Stud. 1 (1974), 43 – 58. Pivoting and extensions. |
| [2] | David Barnette, An upper bound for the diameter of a polytope, Discrete Math. 10 (1974), 9 – 13. · Zbl 0294.52007 · doi:10.1016/0012-365X(74)90016-8 |
| [3] | M. L. Balinski and Fred J. Rispoli, Signature classes of transportation polytopes, Math. Programming 60 (1993), no. 2, Ser. A, 127 – 144. · Zbl 0783.90078 · doi:10.1007/BF01580606 |
| [4] | 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. · Zbl 1150.90008 · doi:10.1007/s00493-006-0010-5 |
| [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. |
| [6] | 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. · Zbl 1297.52002 · doi:10.1287/moor.1120.0554 |
| [7] | Antoine Deza, Tamás Terlaky, and Yuriy Zinchenko, A continuous \?-step conjecture for polytopes, Discrete Comput. Geom. 41 (2009), no. 2, 318 – 327. · Zbl 1168.52009 · doi:10.1007/s00454-008-9096-4 |
| [8] | 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. · Zbl 1226.52004 · doi:10.1287/moor.1100.0470 |
| [9] | G. Kalai. Polymath 3: The Polynomial Hirsch Conjecture, 2010. http://gilkalai.wordpress.com. |
| [10] | 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. |
| [11] | Victor Klee and Peter Kleinschmidt, The \?-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718 – 755. · Zbl 0632.52007 · doi:10.1287/moor.12.4.718 |
| [12] | 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. · Zbl 0751.52006 |
| [13] | Edward D. Kim and Francisco Santos, An update on the Hirsch conjecture, Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73 – 98. · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8 |
| [14] | 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. |
| [15] | D. G. Larman, Paths of polytopes, Proc. London Math. Soc. (3) 20 (1970), 161 – 178. · Zbl 0199.59301 · doi:10.1112/plms/s3-20.1.161 |
| [16] | E. R. Lockeberg, Refinements in boundary complexes of polytopes. Ph.D. thesis, University College London, 1977. |
| [17] | B. Matschke, F. Santos, and C. Weibel, The width of 5-dimensional prismatoids. Preprint arXiv:1202.4701, 2012. · Zbl 1330.52015 |
| [18] | 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. · Zbl 0457.52005 · doi:10.1287/moor.5.4.576 |
| [19] | Francisco Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2) 176 (2012), no. 1, 383 – 412. · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7 |
| [20] | 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). · Zbl 1030.90051 · doi:10.1007/s101070100261 |
| [21] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
