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(s)
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):
-
Francisco Santos, Tamon Stephen, Hugh Thomas,
Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids.
arXiv:1104.2630
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.
arXiv:1202.4701
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.
Expository and survey papers:
-
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.
arXiv:0907.1186
Jahresbericht der Deutschen Mathematiker-Vereinigung, Volume 112(2) (June 2010), 73-98.
DOI: 10.1365/s13291-010-0001-8
-
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.
arXiv:0912.4235
-
An expository paper on the Hirsch conjecture and the counter-example, in Spanish:
F. Santos, Sobre un contraejemplo a la Conjetura de Hirsch,
arXiv:1007.3283
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.
Talk Talk
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,
2010 in
the Matemáticas
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,
undergraduate students,...).
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:
The same course was delivered in Döllnsee (near Berlin) in August 2012
and in Ellwangen (as part of the Séminaire Lotharingien de
Combinatoire) in March 2013.
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 Mundo,
El País,
ABC,
La Vanguardia,
La razón,
20 minutos,
yahoo,
El Diario Montańés,
Europa Press,
EFE,...
On May 27th the two local newspapers,
Alerta and
El Diario Montañes, devoted one page each to the news.
On June 18 and June 21 respectively,
ABC and
El País
published interviews with me. The weekly magazine
Tiempo did the same on September 3:
I was also interviewed by several
radio stations
and even the spanish public national
TV.
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
Hirsch conjecture.
