The Hirsch conjecture
On May 10 2010, I announced a counter-example to the 53 year-old Hirsch conjecture.
The very same day the news was on Gil Kalai's blog and on Wikipedia. This page contains some not very structured comments and information about the solution to the conjecture.
The paper containing details of the proof has been published by Ann. Math. and is also available (in preprint form) from the arXiv:
The following two papers partially answer questions that were left open in the first one (v2 of the first paper contains pointers to them):
Expository and survey papers:
Francisco Santos, Tamon Stephen, Hugh Thomas,
Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids.
Discrete Comput. Geom. 47:3 (2012), 569-576. DOI: 10.1007/s00454-011-9361-9
Two proofs that prismatoids of dimension 4 have width 4 (or less).
Benjamin Matschke, Francisco Santos, Christophe Weibel,
The width of 5-dimensional prismatoids
Preprint, February 2012, 28 pages.
Prismatoids of dimension 5 exist with (a) width growing as O(sqrt(n)) and (b) width six and "only" 25 vertices. The latter implies counter-examples to Hirsch exist in dimension 20. One thing this paper contains is explicit coordinates for this smaller non-Hirsch polytope. You can see them, and more details, in Christophe's page on the topic.
A survey I wrote on the topic with Edward D. Kim before disproving the conjecture (the counter-example is only mentioned as a "note added in proof"):
E.D. Kim and F. Santos,
An update on the Hirsch conjecture,
preprint July 2009.
Jahresbericht der Deutschen Mathematiker-Vereinigung, Volume 112(2) (June 2010), 73-98.
The survey grew too much and ended up being too technical, so part of it was excised as a "companion" paper.
It is on the ArXiv but we do not have plans to publish it:
E.D. Kim and F. Santos,
Companion to "An update on the Hirsch conjecture",
preprint December 2009.
An expository paper on the Hirsch conjecture and the counter-example, in Spanish:
F. Santos, Sobre un contraejemplo a la Conjetura de Hirsch,
La Gaceta de la RSME, Vol. 13 (2010), Num. 3, 525-538.
This paper was translated into German by Julian Pfeifle, and has appeared in
Mitteilungen der DMV, Vol. 18-4, 214-220.
Since June 2010 I have delivered talks on the counter-example
in several places. You can look at the following versions.
- The one from the 8th EUROPT Workshop
"Advances in Continuous Optimization"
in Aveiro (July 10, 2010).
This is the "final version" of
essentially the same talk I gave in seminars in
Santander (June 7), Madrid (June 18), Zürich (June 24), and Lausanne (June 25).
It is targeted at a general mathematical audience and focuses more on the context
of the Hirsch Conjecture (linear programming, simplex method, history) than on the counter-example itself.
PDF file, 1 Mb
- A slightly abridged and updated version of this talk was delivered at the Exploratory Workshop on Mixed Integer and Linear Programming (Seville, December 3, 2010), and also in a seminar in Valladolid (November 5).
PDF file, 1 Mb
- An even more expository talk (in Spanish) was given on October 6,
en acción seminar organized by my department. This one was
90 minutes long and targeted to a mathematically inclined public, but
not professional mathematicians (secondary school teachers,
PDF file, 1.6 Mb
- The version delivered at the 100
years in Seattle: The Mathematics of Klee and Grümbaum conference on July 30, 2010.
This is addressed to a more specialized audience, and hence it contains more
details of the proof, and much less "context material". Still, I think it is
easy to follow without much background on polytope theory.
This version emphasizes that my counter-example is somehow based on two Theorems from the 1967 paper
"The d-step conjecture for polyhedra of dimension d <6" by Victor Klee and David Walkup.
Basically the same talk was repeated at the Bernoulli Conference on DCG in Lausanne on September 2.
PDF file, 1 Mb
- During the DCG semester
organized at EPFL-Lausanne I gave a second talk, in
the Conference on
Geometric Graph Theory (September 28, 2010). This one is
significantly different from the previous ones: it focuses in the
"prismatoid" part of the construction and contains (some) details of
the 4-prismatoid and 5-prismatoid results contained in the
Santos-Stephen-Thomas and Matschke-Santos-Weibel papers mentioned above.
PDF file, 0.9 Mb
- In October 2011 I gave a three lectures on the Hirsch Conjecture
and the counter examples at UC Davis, expanded to an 8 hour minicourse
in March 2012 in Seville. The three parts had the following titles:
Meet the press
On May 26, the news that a spaniard had solved a 50 year-old math problem got to the national press. You can see me on the webs of
El Diario Montańés,
On May 27th the two local newspapers,
El Diario Montañes, devoted one page each to the news.
On June 18 and June 21 respectively,
published interviews with me. The weekly magazine
Tiempo did the same on September 3:
I was also interviewed by several
and even the spanish public national
My university also produced a video
about the discovery.
Last but not least, sono infinitamente grato to Bernd Sturmfels for mentioning me and the discovery in an interview in La Stampa, on April 27 2011:
Update: Recently (2012) both La Recherche and
New Scientist have
featured articles about linear programming and the refutation of the