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 n − d. That is, any two vertices of the polytope may be connected to each other by a path of at most n − d edges.
We had quite a few posts regarding the Hirsch conjecture and related problems.
Combinatorics and more 
I think Paco’s visit to Seattle was in late 2001 or early 2002. I remember seeing him, but I wasn’t living in Seattle in 2003.
How exciting!! Congrats to Paco; I look forward to seeing the talk in Seattle! Any chance that we’ll see a preprint?
This still leaves open the original Polymath3 question of whether the polynomial Hirsch conjecture is true and all that implies. I’m interested to see whether Paco’s approach sheds any light on that question!
That’s my whole PhD work going to trash!
To Oinky: you are absolutely right!!! I was on sabbatical in the west coast in the fall of 2001 (Davis) and then in the fall of 2003 (Berkeley), and I have mixed the two! OMG, I need to resubmit my abstract.
PS: do I know you?
To Anand:
I am afraid my construction says nothing about the polynomiality. As far as I know $2n-2$ (for example) could still be an upper bound for the diameter.
To Tarantino: I hope that is not true. As Anand says, I think the overall question “how much can the diameter of a polytope grow” is as interesting now as it was before.
Paco: We chatted briefly in Seattle. I’ve been a fan of your work for quite some time. Congratulations! This is a wonderful achievement. I hope I can make it to your talk. Seattle in July is absolutely delightful (in stark contrast to November.) Best, Oinky.
Oinky: thans again for finding the “typo”, and for your encouragement. I have checked old emails and I can now confirm that my talk at UW was in Janyary 22, 2002
I posted the updated abstract from the conference site.
Si señor. Me quito el sombrero.
Great!
Is this an explicit construction? Can you just list the coordinates of the vertices and identify the two that violate the conjecture? It can’t be that big, can it?
Congratulations! I look forward to hearing more about this.
Congratulations again! Out of curiosity, do you have any guesses on what the minimum dimension of a counterexample will turn out to be? Probably 43 is too big, but the conjecture’s known to be true for small dimensions, right?
I think it is true for 3 dimensions and open for four dimensions.
I was working on the same problem. I guess I need to find a new research topic.
To the Stanford and CMU PhD srudents,
While this is certainly a major development, there are quite a few remaining interesting questions in this research area, and probably reading Santos’s paper will raise additional problems and ideas.
Hello everyone:
– first, I fully agree with Gil. Perhaps I should not emphasize this, but my counter-example leaves the underlying question (“how big can the diameter of a polytope grow”) as open as it was before. The Hirsch conjecture was basically $n$ and my counterexample will give a lower bound of only about $1.03 n$.
– second, since harrison asked, my personal guess is the minimal counter-example will be quite small, not far from the limits were the Hirsch conjecture has been computationally verified. I will risk some numbers: I wouldn’t be surprised if the Hirsch conjecture is false in dimension four, and I would be much surprised if it is true in dimension six and for, say, twenty facets.
– to Harrison: my proof has two parts: (1) there is a 5-polytope with 48 facets, with the following properties: it has two vertices $u$ and $v$ contained in all the facets (each in 24 of them) and no path of length five joins $u$ to $v$. (2) Then there is what I call the “generalized $d$-step theorem” saying that from this, using certain wedges and perturbations, you can get a 43-dimensional polytope with 86 facets and without the Hirsch property.
Part (1) is totally explicit and has been verified with computer software (polymake). Part (2) is not explicit. On the one hand there are the “perturbations”, which may be difficult to work out explicitly. On the other hand there is the problem that this polytope will be huge. My estimate is it may have a billion vertices. I am not sure whether it is within our current computational capabilities to compute its diameter.
As a final remark, may I recommend those wanting to know more about the state-of-the-art (prior to this week) to look at my recent survey http://arxiv.org/abs/0907.1186 (or to browse through previous Hirsch posts in this blog)
typo: my second “Harrison” was meant to be a “Polik”
Thanks Paco,
I’m quite sure someone will work out the explcit construction as soon as the paper is out. I don’t think a billion vertices is such a big deal, but the perturbations may create numerical issues. How small are the perturbations?
One important lesson to be learned from Paco’s argument is, in my opinion, the imortance of non-simple polytopes (or non-simplicial polytopes for the dual setting). We know that the Hirsch conjecture could be reduced to simple polytopes, and the abstract versions usually extend the dual formulation in terms of simplicial polytopes. But one important ingredient in Paco’s construction not to think just about the simple (simplicial) case.
In addition to the survey that Paco mentioned on his posting, you may be interested to know that there will be a workshop on the topic, to take
place at IPAM UCLA, on January 18 – 21, 2011.
“Efficiency of the Simplex Method; Quo vadis Hirsch conjecture?”
http://www.ipam.ucla.edu/programs/sm2011/
I agree with Gil that there are plenty of interesting questions left and
Paco just put more wood in the fire!!
Congratulations!!! Very exciting news! As Jesus and others have said or implied, if anything, this very nice result will spur interest in discovering stronger worse examples and maybe even improved upper bounds on the diameter.
Hello everyone,
Several days have passed since my last post and I know some of you may be impatient to see the counter-example. I am sorry to say that last and this week are being extremely busy for me, not only because of Hirsch; I am right now at a conference in which I am one of the main organizers (http://www.ciem.unican.es/recio2010).
A draft of my paper already exists and has been circulated among some ten people, including Gil Kalai. The “public” preprint needs some time, not only because I am a slow writer but also because I am giving myself some time to receive comments from those beta-readers. I have put myself a hard deadline of May 24 for the release of the first public version.
Let me (partially) answer Imre Polik’s question “How small are the perturbations?”. The answer is “I don’t know”; my generalized d-step theorem says “there is a sufficiently small perturbation (after each wedge) that works”. For the first iterations I can (or could, I have not done it) control the size of them, but the perturbations will need to be smaller and smaller, probably exponentially so, as we go along the 38 steps that are needed to go from dim 5 to dim 43.
There is actually a group of young enthusiasts among my beta-readers who are trying to find coordinates for the 43-dim gadget, but the results they have so far are not very encouraging. The method they use is they perform the wedge+perturbations one by one, and after each step they check that the face lattice obtained so far is OK. Experimentally we observe that:
– the number of vertices basically doubles after each step, so the final example will have about 2^46 vertices (my “billion” estimate was a bit conservative, it seems).
– the computation time gets multiplied by about four at every iteration. At this rate the final answer would be obtained only after about 2^30 millenia.
Dear Paco,
Many thanks for this update. There is no reason for impatience, after all we waited 53 years, so we can wait a few more weeks.
The beta-version of the paper looks very good. Having constructions which depend on smaller and smaller perturbations may very well be necessary. For example, the necessity part of McMullen’s g-conjecture proved by Billera and Lee in 1980 also required such an argument and there are various other examples.
Commenting on joint research with J.C. Lagarias, N. Prabhu said something like: “if not true, Hirsch conjecture must be dramatically false”.
Are we now getting some new insight regarding the abundance of counterexamples?
Pingback: Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch | Gaussianos
Pingback: El Pensadero de Canek » We will meet in Paris
The preprint is finally out. I am sorry about the delay, but several things happened to me while I was busy making other plans…
See http://arxiv.org/abs/1006.2814
Pingback: mario.velucchi.EU – Blog & Hub Page » Blog Archive » Maths Problems solved recently (Hirsch conjecture) - Software Analyst and Developer _ Computer Mathematician _ WEB Developer _ Mathematics Chess
Cogratulations dear Francisco! I want to have a contact to you by phone or email. I am author of a new Theory in Economics Toward a Rational Theory for Micro and Macro Economics, you could read in Spanish at
wwwmonografias.com/…/teoria-racionalista-micro-y-macro-economia2. shtml or at http://www.ipaebooks.org/artículos destacados.
Your pentaspacial model, as I red in magazine Tiempo, Madrid (were I used to write for) is more important than you believe. I tell you when talk each other.
Mi email address cmedinarebolledo@yahoo.se
Carlos Medina de Rebolledo
Pingback: Budapest, Seattle, New Haven « Combinatorics and more
Pingback: Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? | Combinatorics and more
I wish you continued success and a very nice page
Pingback: Hirsch Conjecture 3 | Euclidean Ramsey Theory
Pingback: Hirsch Conjecture 2 | Euclidean Ramsey Theory
Pingback: Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch - Gaussianos