# Hirsch conjecture

In mathematical programming and polyhedral combinatorics, the **Hirsch conjecture** is the 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^{[es]} 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 conjecture is now known to be false in general.

The Hirsch conjecture was proven for *d* < 4 and for various special cases,^{[3]} while the best known upper bounds on the diameter are only sub-exponential in *n* and *d*.^{[4]} After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, 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 2*d*-facet polytope in *d*-dimensional Euclidean space is no more than *d*.^{[1]}^{[9]}

## Notes

- ↑
^{1.0}^{1.1}Ziegler (1994), p. 84. - ↑ Dantzig (1963), pp. 160 and 168.
- ↑ E.g. see Naddef (1989) for 0-1 polytopes.
- ↑ Kalai & Kleitman (1992).
- ↑ Santos (2011).
- ↑ Kalai (2010).
- ↑ "Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch",
*Gaussianos*, May 24, 2010 - ↑ Santos (2011)
- ↑ 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.
- 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, MR 1130448, arXiv:math/9204233 , doi:10.1090/S0273-0979-1992-00285-9. - Klee, Victor; Walkup, David W. (1967), "The
*d*-step conjecture for polyhedra of dimension*d*< 6",*Acta Mathematica*,**133**: 53–78, MR 0206823, doi:10.1007/BF02395040. - 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, MR 1017214, doi:10.1007/BF01589099. - Santos, Francisco (2011), "A counterexample to the Hirsch conjecture",
*Annals of Mathematics*, Princeton University and Institute for Advanced Study,**176**(1): 383–412, MR 2925387, arXiv:1006.2814 , doi:10.4007/annals.2012.176.1.7 - Ziegler, Günter M. (1994), "The Hirsch Conjecture",
*Lectures on Polytopes*, Graduate Texts in Mathematics,**152**, Springer-Verlag, pp. 83–93.