Hirsch conjecture

From Wikipedia, the free encyclopedia

In mathematical programming and geometry, Hirsch's conjecture states 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 may be connected to each other by a path of at most n − d edges.

Hirsch's conjecture is known to be true for d < 4 and for various special cases,^[1] but in general the status of the problem is unknown. The best known upper bounds show only that polytopes have sub-exponential diameter as a function of n and d.^[2] Various equivalent formulations of the problem have 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.^[3]^[4] The d-step conjecture is known to be true for for d < 6.^[4]

The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957.^[3]^[5]

[edit] Notes

^ E.g. see Naddef (1989) for 0-1 polytopes.
^ Kalai & Kleitman (1992).
^ ^a ^b Ziegler (1994), p. 84.
^ ^a ^b Klee & Walkup (1967).
^ Dantzig (1963), pp. 160 and 168.

[edit] References

Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press .

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, MR 1130448, 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 http://dx.doi.org/10.1007/BF02395040 .

Naddef, Denis (1989), “The Hirsch conjecture is true for (0,1)-polytopes”, Mathematical Programming 45 (1): 109–110, MR 1017214, DOI 10.1007/BF01589099 .