Abstract
The Hirsch Conjecture (1957) stated 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.
This paper presents the first counterexample to the conjecture. Our polytope has dimension $43$ and $86$ facets. It is obtained from a $5$-dimensional polytope with $48$ facets that violates a certain generalization of the $d$-step conjecture of Klee and Walkup.
Full Article