This is the user sandbox of Andreschulz. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.
Writing an article and ready to request its creation?
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture stated that every graph of ad-dimensional polytope with n facets has diameter no more than n − d. It was proven by Francisco Santos Leal in 2010 that the conjecture is not true in general.
every graph of an 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 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. The best known upper bounds showed only that polytopes have sub-exponential diameter as a function of n and d. After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos, from the University of Cantabria. The result was presented at the conference 100 Years in Seattle: the mathematics of Klee and Grünbaum and appeared in Annals of Mathematics. 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.
- 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.
- 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.
- Miranda, Eva (2012), "The Hirsch conjecture has been disproved: An interview with Francisco Santos" (PDF), Newsletter of the European Mathematical Society (86): 31–36.
- 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 (2011), "A counterexample to the Hirsch conjecture", Annals of Mathematics (Princeton University and Institute for Advanced Study) 176 (1): 383–412, arXiv:1006.2814, doi:10.4007/annals.2012.176.1.7, MR 2925387
- Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, pp. 83–93.