“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 -dimensional polytope with facets cannot have (combinatorial) diameter greater than . That is, that any two vertices of the polytope can be connected to each other by a path of at most 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 -step conjecture of Klee and Walkup.

This is certainly a major event. The Hirsch conjecture with the very appealing “non-revisiting” formulation, with the neat formula , and with the many equivalent forms, captured the imagination of many people.  We saw it here: When we tried to discuss related questions, most people and most comments targeted the original conjecture itself.

The proof demonstrates not only Paco’s own ingenuity and endurance but also the steady progress in constructing polytopes and related combinatorial objects. The computer package POLYMAKE created by  Ewgenij Gawrilow and Michael Joswig  played an important role in giving a different verification of the properties of the five-dimensional construction in the paper.

Paco quotes  Klee and Kleinschmidt who wrote that “finding a counterexample will be merely a small first step in the line of investigation related to the conjecture.” But it is left to be seen if related questions such as the “polynomial Hirsch conjecture” will also draw as much interest as the original conjecture did. Certainly, Paco’s achievement may lead to renewed interest in these related problems. 

So it is time to read, learn and discuss the paper. (It is good that our term just ended.)