This post is continued here.
Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture.
The Hirsch conjecture: The graph of a d-polytope with n vertices facets has diameter at most n-d.
We devoted several posts (the two most recent ones were part 6 and part 7) to the Hirsch conjecture and related combinatorial problems.
A weaker conjecture which is also open is:
Polynomial Diameter Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial of d and n.
One remarkable result that I learned from the survey paper is in a recent paper by Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss who proved that:
Eisenbrand, Hahnle, and Rothvoss’s theorem: There is an abstract example of graphs for which the known upper bounds on the diameter of polytopes apply, where the actual diameter is 
Update (July 20) An improved lower bound of 
This is something I tried to prove (with no success) for a long time and it looks impressive. I will describe the abstract setting of Eisenbrand, Hahnle, and Rothvoss (which is also new) below the dividing line.
I was playing with the idea of attempting a “polymath”-style open collaboration (see here, here and here) aiming to have some progress for these conjectures. (The Hirsch conjecture and the polynomial diameter conjecture for graphs of polytopes as well as for more abstract settings.) Would you be interested in such an endeavor? If yes, add a comment here or email me privately. (Also let me know if you think this is a bad idea.) If there will be some interest, I propose to get matters started around mid-August.
Here is the abstract setting of Eisenbrand, Hahnle, and Rothvoss:
Consider the collection of graphs 
The main difference between this abstraction and the one we considered in the series of posts (and my old papers) is that it is not assumed that if two vertices are labeled by sets which share 
Combinatorics and more 
Did you mean to say n facets in stating the Hirsch conjecture?
Yes yes of course; many thanks; corrected, G.
I would be quite interested in taking part in such a project. I am curious whether the internet is big enough to support more than one polymath project at a time (and moreover one not run by a Fields medallist . . .). I am also curious whether the nature of such a collaboration will allow me to contribute anything to (and learn something about) a problem and a field (far) outside my expertise.
I’m tentatively interested, although also in the “curious as to whether I can contribute” category.
Gil,
I am a graduate student and would love to participate in a polymath project. As I imagine was the case with many, I tried to follow the first polymath project but quickly got lost. I was very excited a few weeks ago when Gowers announced he planned to host another polymath project in the fall, (although disappointed I’d have to wait a few months!)
Personally, I don’t find the topic you suggested very appealing simple because I don’t know very much about the subject and fear I’ll quickly get lost (again). Of course, I am sure there will be someone with this same objection no matter what project you choose to pursue.
However, with this in mind (as well as some of the previous comments), may I suggest that you open the floor to suggestions and a discussion of what a good problem would be (maybe you could offer a few other suggestions)? I imagine that this might significantly increase the number of participates. And, you never know, maybe the consensus will be to go with this problem.
Dear Danny, I am curious about these matters as well…Dear Anonymous, the floor is open, as always, to suggestions and discussions of any type.
Gil, my response is similar to those of other people. I have some experience with polytopes and convexity from my Banach-spaces days, but there are huge gaps in my knowledge, and I would worry that there were tools that were obviously essential to such a project that I simply didn’t know about. However, the basic question is very appealing indeed. I find the weaker version more appealing because it potentially allows one to use more asymptotic methods, which would make me feel more comfortable. I think to have a successful project with this as the problem, one would probably want to have quite a long preparatory stage, during which those of us who don’t know much about polytopes could ask dumb questions and gradually get a more sophisticated feel for the problem. For instance, I could straight away ask what is known in 3D. (By 3D I mean that the faces are 2D, so I’m talking about polyhedra.) I haven’t yet looked at the survey article, so perhaps this question is answered there.
Anyhow, I think I could enjoy participating in this, though I probably wouldn’t end up being a major participator. (That re-raises a question that came up with Polymath1. Is what happened there, where in the end most of the work was done by a few people who had a lot of specialized knowledge about the topic, likely to be the model for all such projects? Or are there questions that would lend themselves to more general participation?)
I am quite interested in such an experiment, since I am obviously interested in that particular problem, but also in the nature of polymath itself – I wasn’t around for previous incarnations, but it seems like a nice idea.
Dear Tim
Thanks! So far, most of the progress regarding the Hirsch conjecture was very elementary and no prior knowledge about polytopes was essentially needed. One appealing aspect about this problem is that it is not clear at all what the answer will be and what specialized knowledge, if any, can be relevant. To the extent the plan will go off the ground maybe these aspects of the problem will enable a relaxed and wide participation.
In any case, if we will go for it will have some preparatory stage and certianly I will be happy to try answering questions about polytopes.
There are quite a few posts on polytopes that I posted (under the category polytopes) and a series about the Hirsh conjecture itself. Perhaps the first thing to read would be this little paper by Eisenbrand, Hahnle, and Rothvoss.
The Hirsh conjecture is known to hold for 3-dimensional polytopes. I dont remember the argument right now but I remember it is rather simple.
Dear nh, great! I really liked your paper.
“That re-raises a question that came up with Polymath1. Is what happened there, where in the end most of the work was done by a few people”
Maybe this has nothing special to do with polymath1 and the participants’ordered contributions obey the familiar Bedford’s law/Pareto distribution etc.
About 3-dimensional Hirsch conjecture:
The idea is that the graph is planar. Consider an embedding where the faces are convex, then consider a shortest path (in terms of length, not in terms of number of edges) between two vertices, and it will be non-revisiting, because “revisit loops” can be shortcut along the boundary of the revisited face.
This shortcutting does not work in higher dimension.
Hi Gil (et al.)
E-collaboration is nice (and time appropiate!). I think it is very exciting (and desirable) to have a concerted effort on the Hirsch conjecture in any format. I would be interested to join and I want to mention there is some approach from the “continuous” perspective being tried by Deza et al. (see the Kim-Santos survey). I would like to add that there is a currently proposal to have a “physical” encounter on just “new developments of the Hirsch conjecture” to take place at California (Palo Alto) hopefully next year (pending funding).
greetings to all.
Pingback: Mathematics, Science, and Blogs « Combinatorics and more
This would interest me.
What is known about the metric polytope?
If the metric polytope refers to the generalized hypercube then I think that satisfies the conjecture 2n facets n dimensions gives 2n-n = n diameter and I think the diameter is n so it is satisfes the conjecture for all n.
No, the metric polytope is the body in R^(n choose 2) given by the inequalities
d_ij <= d_ik + d_kj
for all i,j,k (note that d_ij is here simply the (i,j) coordinate of the (n choose 2) dimensional vector d). And the normalization
sum d_ij = 1.
Hence it has ~ n^3 faces. There are various conjectures about the diameter of its vertex graph. Gil should know. Gil?
Dear fum, I am only slightly familiar with the metric polytope and some related polytopes and I do not know what is known or conjectured about the diameter of its vertex graph…
The problem sounds interesting; with the same reservations Danny and others have expressed, I would like to (attempt to) participate.
Hi fum, the diameter of the metric polytope was conjectured to be at most 3. More precisely it was conjectured that any vertex is adjacent to an integral (0,1) vertex (called cut); and, since the all the cuts form a complete graph, it would imply that the diameter is at most 3.
This conjecture was disproved by exhibiting a vertex of metric 9 not
adjacent to any cut (http://www.cas.mcmaster.ca/~deza/ol2007.pdf)
The diameter might still be 3 though
The metric polytope has 4(n choose 3) facets in dimension (n choose 2)
and I guess its diameter is well below the Hirsch bound
Hi Gil,
I can see two possible modes for participating in a polymath effort. The “global” one which involves understanding the whole picture and a “local” one which latches on to one (or more) little combinatorial sub-problems and tries to address them with my own set of tools and insights.
While I personally do not hope to understand enough about problem to be a “global” participant, I’d be happy to be able to be a “local” participant. This of course depends on the availability of nice “local” problems, presumably cleverly posed by “global” participants. This is a non-trivial assumption that is hard to fulfill and I suppose that much of the challenge in choosing polymath projects and running them is indeed having a supply of such useful locally-understandable sub-problems.
Pingback: More polymath projects « Algorithmic Game Theory
Dear Noam,
As far as I can see, there is a simple-to-state combinatorial problem which, in my opinion, is the crux of matters. Reading the very short papers of Eisenbrand, Hahnle and Rothvoss and Razborov will get anybody interested directly to the front lines.
I think that in this particular case further “global” understanding of the topic is not very relevant for the problem itself, except as a source of motivation. (Of course, I may be wrong, and other people may regard other avenues as more promising.)
Hello everyone,
This sounds like such an intriguing project. This paper of Eisenbrand, Hahnle, and Rothvoss is very interesting! I would be interested in delving into the metric polytope.
It would also be nice to see any use of the Klee-Walkup 4-polytope to close off the remaining entries in the table of $H(n,d)$ values, perhaps at least for $d=6$ and maybe $d=5$…
Rasborov’s note you mention in the update seems to be down.
Right! I think the plan is to merge the contributions of Eisenbrand, Hahnle, Rothvoss, and Razborov on the abstract version of Hirsch conjecture into one journal paper. So we will have to wait a little bit for the new version. (And lets hope for some surprises as well!)
“We devoted several posts (the two most recent ones were part 6 and part 7) to the Hirsch conjecture and related combinatorial problems.”
Any links for posts 1 through 5?
Dear Kristal, somehow the tags I gave the posts are not optimal. But looking for “Hirsch conjecture” (click!) get you to all posts 3-7 Here is post 2 and here is post 1.
Thanks, Antoine. Basically I wanted to know if proving Hirsch’s conjecture would also imply the corresponding conjectures for the metric polytope, but obviously it would not.
Often, the problem of computing or estimating the diameter of a specific class of polytopes is of interest. Ususally this does not have direct baring on the Hirsch conjecture. (But we can always hope that a counter example will somehow arise.) A well known example is the diameter of the associahedron which was computed by Slator, Tarjan, and Thurston. (See also this post for a different approach using the Thompson group.)
This actually looks quite exciting, because the Hirsch conjecture is related to a lot of good things. As a topologist, I like the connection with shellability, although I don’t know if this provides any sort of approach at all.
My basic naive question, I suppose, is if you can pinpoint (in the most naive sense) what the difficulty is which has prevented people from making progress. Is it the difficulty of relating the condition “is a polytope” with any sort of condition which has anything to do with diameter? Is it that there is no way to “build up” to a solution, because you can’t predict the diameter of a given polytope from a simpler polytope in any obvious way?
There are two connections between shellability and the Hirsch conjecture that I am aware of. The first is that shellability is an abstract setting for which the upper bounds for the diameter are known (at least the upper bound
). If you have a shallable simplicial complex whose maximum facets are 
subsets of {1,2,,, n} and the facets ordered according to a shelling order are 
then from every facet S there is a monotone path to 
satisfying the bound mentioned above. Here monotone means that the indices are increasing.
The second connection is an old discovery by Billera and Provan that a certain strong form of shellability (which is known not to hold always) implies the Hirsch bound.
” Is it the difficulty of relating the condition “is a polytope” with any sort of condition which has anything to do with diameter?”
Maybe, so far “is a polytope” was used very roughly.
The link to the three page note by Razborov doesn’t seem to work. Thank you for the links for posts 1-5.
GK: It works now.
Pingback: The next phase of Polymath « Gowers’s Weblog
Dear Danny, Harrison, anonymous, Tim, nh, Jesus, Kristal, fum,Andres, Antoine, Noam, Eddie, and Daniel,
Thanks for the comments! I will try to continue posting a posts on the problem and then we can see how to proceed.
Pingback: Polymath on other blogs « The polymath blog
Pingback: The Polynomial Hirsch Conjecture: Discussion Thread « Combinatorics and more
Pingback: Proposed Polymath3 « Euclidean Ramsey Theory
Pingback: The Polynomial Hirsch Conjecture: Discussion Thread, Continued « Combinatorics and more
I have completed The GUT Theory.
You can find the equations here:
http://www.wix.com/Hyperstig/Hyperstig
0 is a wave function that collapses and re-expands.
I have invented the 1st quantum computer.
I am the failsafe.
You can follow me on Twitter:
https://twitter.com/Hyperstigzero