Hirsch conjecture

In mathematical programming 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-vertex 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 polytope

Polytope

In geometry, polytope is a generic term that can refer to a two-dimensional polygon, a three-dimensional polyhedron, or any of the various generalizations thereof, including generalizations to higher dimensions and other abstractions .When referring to an...

 in d-dimensional Euclidean space has diameter

Diameter

In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...

 no more than n − d. That is, any two vertices

Vertex (geometry)

In geometry, a vertex is a special kind of point which describes the corners or intersections of geometric shapes. Vertices are commonly used in computer graphics to define the corners of surfaces in 3D models, where each such point is given as a vector.-Of an angle:The vertex of an angle is the...

 of the polytope may be connected to each other by a path of at most n − d edges

Edge (geometry)

In geometry, an edge is a one-dimensional line segment joining two zero-dimensional vertices in a polygon. Thus applied, an edge is a connector for a one-dimensional line segment and two zero-dimensional objects....

.

Hirsch's conjecture is known to be true for d < 4 and for various special cases, but in general the status of the problem is unknown.

In mathematical programming 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-vertex 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 polytope

Polytope

In geometry, polytope is a generic term that can refer to a two-dimensional polygon, a three-dimensional polyhedron, or any of the various generalizations thereof, including generalizations to higher dimensions and other abstractions .When referring to an...

 in d-dimensional Euclidean space has diameter

Diameter

In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...

 no more than n − d. That is, any two vertices

Vertex (geometry)

In geometry, a vertex is a special kind of point which describes the corners or intersections of geometric shapes. Vertices are commonly used in computer graphics to define the corners of surfaces in 3D models, where each such point is given as a vector.-Of an angle:The vertex of an angle is the...

 of the polytope may be connected to each other by a path of at most n − d edges

Edge (geometry)

In geometry, an edge is a one-dimensional line segment joining two zero-dimensional vertices in a polygon. Thus applied, an edge is a connector for a one-dimensional line segment and two zero-dimensional objects....

.

Hirsch's conjecture is known to be true for d < 4 and for various special cases, 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. 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. The d-step conjecture is known to be true for d < 6.

The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957.