Daily Archives: May 10, 2010

Francisco Santos Disproves the Hirsch Conjecture

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention:

Title: “A counter-example to the Hirsch conjecture”

Author: Francisco Santos, Universidad de Cantabria


I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture”?

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $d$-step theorem of Klee and Walkup.

Great news! Congratulations Paco!

Hirsch’s conjecture (1957) states that the  graph of a d-dimensional polytope with n facets  has diameter no more than nd. That is, any two vertices of the polytope may be connected to each other by a path of at most nd edges.

We had quite a few posts regarding the Hirsch conjecture and related problems.