“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. The Hirsch conjecture with the very appealing “non-revisiting” formulation, with the neat formula n-d, 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.)

About these ads

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

  1. Pingback: Polymath5 « Euclidean Ramsey Theory

  2. Pingback: Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s