“A Counterexample to the Hirsch Conjecture,” is Now Out


Francisco (Paco) Santos’s paper “A Counterexample to the Hirsch Conjecture” is now out

For some further information and links to the media see also this page. Here is a link to a TV interview.

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, that any two vertices of the polytope can be connected to each other by a path of at most n-d edges. This paper presents the first counter-example to the conjecture. Our polytope has dimension 43 and 86 facets. It is obtained from a 5-dimensional polytope with 48 facets which violates a certain generalization of the d-step conjecture of Klee and Walkup.

This is certainly a major event.  Continue reading