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 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 conjecture is now known to be false in general.

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