Hirsch conjecture
Encyclopedia
In mathematical programming
and polyhedral combinatorics
, Hirsch's conjecture states that the edge
-vertex
graph
of an n-facet
polytope
in d-dimension
al 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.
Hirsch's 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. However, 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
. 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. The d-step conjecture was known to be true for d < 6, but the general case was also disproved when a counter-example was found, using a 43-dimensional polytope of 86 facets with a diameter of more than 43.
The announced counterexample would have no direct consequences for the analysis of the simplex method, as it would not rule out the possibility of a larger but still linear or polynomial number of steps.
Mathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
and polyhedral combinatorics
Polyhedral combinatorics
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes....
, Hirsch's conjecture states that the edge
Edge (geometry)
In geometry, an edge is a one-dimensional line segment joining two adjacent zero-dimensional vertices in a polygon. Thus applied, an edge is a connector for a one-dimensional line segment and two zero-dimensional objects....
-vertex
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
of an n-facet
Facet (mathematics)
A facet of a simplicial complex is a maximal simplex.In the general theory of polyhedra and polytopes, two conflicting meanings are currently jostling for acceptability:...
polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
in d-dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
has diameter no more than n − d. That is, any two vertices
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
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
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method.
Hirsch's 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. However, after more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, from the University of Cantabria
University of Cantabria
University of Cantabria , in Spanish Universidad de Cantabria, is a public university located in Santander and Torrelavega in Cantabria, Spain. It was founded in 1972 and is organized in 12 schools and colleges....
. The result was presented at the conference 100 Years in Seattle: the mathematics of Klee
Victor Klee
Victor L. Klee, Jr. was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of Washington in Seattle.Born in San Francisco, Vic Klee earned his B.A...
and Grünbaum
Branko Grünbaum
Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel....
. 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. The d-step conjecture was known to be true for d < 6, but the general case was also disproved when a counter-example was found, using a 43-dimensional polytope of 86 facets with a diameter of more than 43.
The announced counterexample would have no direct consequences for the analysis of the simplex method, as it would not rule out the possibility of a larger but still linear or polynomial number of steps.