×

A counterexample to the Hirsch conjecture. (English) Zbl 1252.52007

The Hirsch Conjecture from 1957 states that the graph of a \(d\)-dimensional polytope with \(n\) facets cannot have combinatorial diameter greater than \(n-d\). That is, any two vertices of the polytope can be connected by a path of at most \(n-d\) edges. In this paper this general conjecture is disproved by presenting a counterexample to it. The polytope of the counterexample has dimension \(43\) and \(86\) facets.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05C12 Distance in graphs

Software:

polymake
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Barnette, ”\(W_v\) paths on 3-polytopes,” J. Combinatorial Theory, vol. 7, pp. 62-70, 1969. · Zbl 0177.26804 · doi:10.1016/S0021-9800(69)80007-4
[2] D. Barnette, ”A proof of the lower bound conjecture for convex polytopes,” Pacific J. Math., vol. 46, pp. 349-354, 1973. · Zbl 0264.52006 · doi:10.2140/pjm.1973.46.349
[3] D. Barnette, ”An upper bound for the diameter of a polytope,” Discrete Math., vol. 10, pp. 9-13, 1974. · Zbl 0294.52007 · doi:10.1016/0012-365X(74)90016-8
[4] G. Blind and R. Blind, ”The cubical \(d\)-polytopes with fewer than \(2^{d+1}\) vertices,” Discrete Comput. Geom., vol. 13, iss. 3-4, pp. 321-345, 1995. · Zbl 0824.52013 · doi:10.1007/BF02574048
[5] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: Springer-Verlag, 1998. · Zbl 0948.68068
[6] L. Blum, M. Shub, and S. Smale, ”On a theory of computation and complexity over the real numbers: \({NP}\)-completeness, recursive functions and universal machines,” Bull. Amer. Math. Soc., vol. 21, iss. 1, pp. 1-46, 1989. · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[7] K. Borgwardt, The Simplex Method. A Probabilistic Analysis, New York: Springer-Verlag, 1987, vol. 1. · Zbl 0604.90092
[8] D. Bremner, A. Deza, W. Hua, and L. Schewe, More bounds on the diameter of convex polytopes, 2009. · Zbl 1266.52016 · doi:10.1080/10556788.2012.668906
[9] D. Bremner and L. Schewe, ”Edge-graph diameter bounds for convex polytopes with few facets,” Exp. Math., vol. 20, iss. 3, pp. 229-237, 2011. · Zbl 1266.52017 · doi:10.1080/10586458.2011.564965
[10] G. B. Dantzig, ”Maximization of a linear function of variables subject to linear inequalities,” in Activity Analysis of Production and Allocation, New York, N. Y.: John Wiley & Sons, 1951, vol. 13, pp. 339-347. · Zbl 0045.09802
[11] G. B. Dantzig, Linear Programming and Extensions, Princeton, NJ: Princeton Univ. Press, 1998. · Zbl 0997.90504
[12] J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, New York: Springer-Verlag, 2010, vol. 25. · Zbl 1207.52002 · doi:10.1007/978-3-642-12971-1
[13] J. Dongarra and F. Sullivan, ”Guest Editors’ Introduction: The Top 10 Algorithms,” Comput. Sci. Eng., vol. 2, pp. 22-23, 2000. · Zbl 05091596 · doi:10.1109/MCISE.2000.814652
[14] F. Eisenbrand, N. Hähnle, A. Razborov, and T. Rothvoß, ”Diameter of polyhedra: limits of abstraction,” Math. Oper. Res., vol. 35, iss. 4, pp. 786-794, 2010. · Zbl 1226.52004 · doi:10.1287/moor.1100.0470
[15] E. Fogel, D. Halperin, and C. Weibel, ”On the exact maximum complexity of Minkowski sums of polytopes,” Discrete Comput. Geom., vol. 42, iss. 4, pp. 654-669, 2009. · Zbl 1207.52012 · doi:10.1007/s00454-009-9159-1
[16] O. Friedmann, ”A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games,” in Integer Programming and Combinatorial Optimization, 15th International Conference, New York, 2011, pp. 192-206. · Zbl 1341.90143 · doi:10.1007/978-3-642-20807-2_16
[17] O. Friedmann, T. Hansen, and U. Zwick, ”Subexponential lower bounds for randomized pivoting rules for the simplex algorithm,” in STOC ’11:Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, New York, 2011, pp. 283-292. · Zbl 1288.68090 · doi:10.1145/1993636.1993675
[18] E. Gawrilow and M. Joswig, ”Polymake: a framework for analyzing convex polytopes,” in Polytopes-Combinatorics and Computation, Basel: Birkhäuser, 2000, vol. 29, pp. 43-73. · Zbl 0960.68182
[19] P. Gritzmann and V. Klee, ”Mathematical programming and convex geometry,” in Handbook of Convex Geometry, Vol. A, B, Amsterdam: North-Holland, 1993, pp. 627-674. · Zbl 0806.90098
[20] B. Grünbaum, Convex Polytopes, Second ed., New York: Springer-Verlag, 2003, vol. 221. · Zbl 1024.52001 · doi:10.1007/978-1-4613-0019-9
[21] L. G. Havcijan, ”A polynomial algorithm in linear programming,” Dokl. Akad. Nauk SSSR, vol. 244, iss. 5, pp. 1093-1096, 1979. · Zbl 0414.90086
[22] N. Hähnle, Post in G. Kalai, Polymath 3: Polynomial Hirsch Conjecture, 2010.
[23] F. B. Holt and V. Klee, ”Many polytopes meeting the conjectured Hirsch bound,” Discrete Comput. Geom., vol. 20, iss. 1, pp. 1-17, 1998. · Zbl 0926.52013 · doi:10.1007/PL00009372
[24] M. Joswig and G. M. Ziegler, ”Neighborly cubical polytopes,” Discrete Comput. Geom., vol. 24, iss. 2-3, pp. 325-344, 2000. · Zbl 1066.52012 · doi:10.1007/s004540010039
[25] G. Kalai and D. J. Kleitman, ”A quasi-polynomial bound for the diameter of graphs of polyhedra,” Bull. Amer. Math. Soc., vol. 26, iss. 2, pp. 315-316, 1992. · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9
[26] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,” Combinatorica, vol. 4, iss. 4, pp. 373-395, 1984. · Zbl 0557.90065 · doi:10.1007/BF02579150
[27] E. D. Kim and F. Santos, ”An update on the Hirsch conjecture,” Jahresber. Dtsch. Math.-Ver., vol. 112, iss. 2, pp. 73-98, 2010. · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8
[28] E. D. Kim and F. Santos, Companion to “An update on the Hirsch conjecture”. · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8
[29] V. Klee, ”Diameters of polyhedral graphs,” Canad. J. Math., vol. 16, pp. 602-614, 1964. · Zbl 0121.37701 · doi:10.4153/CJM-1964-061-2
[30] V. Klee, ”On the number of vertices of a convex polytope,” Canad. J. Math., vol. 16, pp. 701-720, 1964. · Zbl 0128.17201 · doi:10.4153/CJM-1964-067-6
[31] V. Klee, ”Paths on polyhedra. II,” Pacific J. Math., vol. 17, pp. 249-262, 1966. · Zbl 0141.21303 · doi:10.1137/0113062
[32] V. Klee, Diameters of polytopes, 1967. · Zbl 1024.52001 · doi:10.1007/978-1-4613-0019-9
[33] V. Klee and P. Kleinschmidt, ”The \(d\)-step conjecture and its relatives,” Math. Oper. Res., vol. 12, iss. 4, pp. 718-755, 1987. · Zbl 0632.52007 · doi:10.1287/moor.12.4.718
[34] V. Klee and D. W. Walkup, ”The \(d\)-step conjecture for polyhedra of dimension \(d<6\),” Acta Math., vol. 117, pp. 53-78, 1967. · Zbl 0163.16801 · doi:10.1007/BF02395040
[35] D. G. Larman, ”Paths of polytopes,” Proc. London Math. Soc., vol. 20, pp. 161-178, 1970. · Zbl 0199.59301 · doi:10.1112/plms/s3-20.1.161
[36] B. Matschke, F. Santos, and C. Weibel, The width of 5-prismatoids, 2012. · Zbl 1330.52015 · doi:10.1112/plms/pdu064
[37] N. Megiddo, ”On the complexity of linear programming,” in Advances in Economic Theory, Cambridge: Cambridge Univ. Press, 1989, vol. 12, pp. 225-268. · Zbl 0735.90044
[38] S. J. Provan and L. J. Billera, ”Decompositions of simplicial complexes related to diameters of convex polyhedra,” Math. Oper. Res., vol. 5, iss. 4, pp. 576-594, 1980. · Zbl 0457.52005 · doi:10.1287/moor.5.4.576
[39] F. Santos, T. Stephen, and H. Thomas, ”Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids,” Discrete Comput. Geom., vol. 47, iss. 3, pp. 569-576, 2012. · Zbl 1238.05078 · doi:10.1007/s00454-011-9361-9
[40] S. Smale, ”Mathematical problems for the next century,” in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 271-294. · Zbl 1031.00005
[41] D. A. Spielman and S. Teng, ”Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time,” J. ACM, vol. 51, iss. 3, pp. 385-463, 2004. · Zbl 1192.90120 · doi:10.1145/990308.990310
[42] T. Terlaky and S. Z. Zhang, ”Pivot rules for linear programming: A survey on recent theoretical developments. Degeneracy in optimization problems,” Ann. Oper. Res., vol. 46/47, iss. 1-4, pp. 203-233, 1993. · Zbl 0793.90034 · doi:10.1007/BF02096264
[43] M. J. Todd, ”The monotonic bounded Hirsch conjecture is false for dimension at least \(4\),” Math. Oper. Res., vol. 5, iss. 4, pp. 599-601, 1980. · Zbl 0457.52006 · doi:10.1287/moor.5.4.599
[44] M. J. Todd, ”Book review on “The basic George B. Dantzig” (by Richard W. Cottle, Stanford University Press, Stanford, California, 2003),” Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 123-129, 2011. · Zbl 1292.00042 · doi:10.1090/S0273-0979-2010-01303-3
[45] G. M. Ziegler, Lectures on Polytopes, New York: Springer-Verlag, 1995, vol. 152. · Zbl 0823.52002
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.