A counterexample to the Hirsch conjecture (Q447933)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A counterexample to the Hirsch conjecture |
scientific article |
Statements
A counterexample to the Hirsch conjecture (English)
0 references
30 August 2012
0 references
The Hirsch Conjecture from 1957 states that the graph of a \(d\)-dimensional polytope with \(n\) facets cannot have combinatorial diameter greater than \(n-d\). That is, any two vertices of the polytope can be connected by a path of at most \(n-d\) edges. In this paper this general conjecture is disproved by presenting a counterexample to it. The polytope of the counterexample has dimension \(43\) and \(86\) facets.
0 references
graph diameter
0 references
Hirsch conjecture
0 references
polytopes
0 references
simplex algorithm
0 references
0 references
