Hirsch conjecture
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the generally false statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957[1][2] and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method.
The Hirsch conjecture was proven for d < 4 and for various special cases.[3] The best known upper bounds showed only that polytopes have sub-exponential diameter as a function of n and d.[4] After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos, from the University of Cantabria.[5][6][7] The result was presented at the conference 100 Years in Seattle: the mathematics of Klee and Grünbaum and appeared in Annals of Mathematics.[8] Specifically, the paper presented a 43-dimensional polytope of 86 facets with a diameter of more than 43. The counterexample has no direct consequences for the analysis of the simplex method, as it does not rule out the possibility of a larger but still linear or polynomial number of steps.
Various equivalent formulations of the problem had been given, such as the d-step conjecture, which states that the diameter of any 2d-facet polytope in d-dimensional Euclidean space is no more than d.[1][9]
Notes
- ^ a b Ziegler (1994), p. 84.
- ^ Dantzig (1963), pp. 160 and 168.
- ^ E.g. see Naddef (1989) for 0-1 polytopes.
- ^ Kalai & Kleitman (1992).
- ^ Santos (2010).
- ^ Kalai (2010).
- ^ http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/
- ^ Franciscos Santos (2012). "A counterexample to the Hirsch conjecture". Annals of Mathematics. 176 (1). Princeton University and Institute for Advanced Study: 383–412. doi:10.4007/annals.2012.176.1.7. Retrieved 2012-05-23.
{{cite journal}}: Cite has empty unknown parameter:|1=(help) - ^ Klee & Walkup (1967).
References
- Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
- Kalai, Gil (10 May 2010). "Francisco Santos Disproves the Hirsch Conjecture". Retrieved 11 May 2010.
{{cite web}}: Invalid|ref=harv(help) - Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, 26 (2): 315–316, arXiv:math/9204233, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448.
- Klee, Victor; Walkup, David W. (1967), "The d-step conjecture for polyhedra of dimension d < 6", Acta Mathematica, 133: 53–78, doi:10.1007/BF02395040, MR 0206823.
- Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming, 45 (1): 109–110, doi:10.1007/BF01589099, MR 1017214.
- Santos, Francisco (2010). "A counterexample to the Hirsch conjecture". arXiv:1006.2814 [math.CO].
- Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 83–93.