In mathematical programming and polyhedral combinatorics, the Hirsch conjecture concerns the diameter of edge-vertex graphs in polytopes, proposing that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n minus d. Warren M. Hirsch introduced the idea in 1957 through correspondence with George B. Dantzig, motivated by analyzing the simplex method. The conjecture has since been proven false.
Facts
Debunked
Progress Toward ResolutionThe conjecture was disproved in May 2010, when Francisco Santos Leal of the University of Cantabria announced a 43-dimensional counterexample polytope of 86 facets with a diameter of more than 43. 1 Prize Status
Prize Status (category) StatementThe edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n minus d. 1 Proposed Year Classification
Resolution Status Chronology
Resolved Year Connections
In Branch
Source Hirsch Conjecture (Wikipedia)
Sources
1. Hirsch Conjecture (Wikipedia)
Lead section
the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n - d
History section
The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957.
Counterexample section
After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, from the University of Cantabria.
Lead section, resolution status
The conjecture is now known to be false in general.
In Branch: Combinatorics, Lead sentence
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.