I can see three main avenues toward making progress on the Polynomial Hirsch conjecture.
One direction is trying to improve the upper bounds, for example, by looking at the current proof and trying to see if it is wasteful and if so where it can be pushed further.
Another direction is trying to improve the lower-bound constructions for the abstract setting, perhaps by trying to model an abstract construction on the ideas of the upper bound proof.
The third direction is to talk about entirely different avenues to the problem: new approaches for upper bounds, related problems, special classes of polytopes, expansion properties of graphs of polytopes, the relevance of shellability, can metric properties come to play, is the connection with toric varieties relevant, continuous analogs, and other things I cannot even imagine.
Reading the short recent paper by Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss will get you started both for the upper bounds and for the lower bounds.
I want to discuss here very briefly how the upper bounds could be improved. (Several people had ideas in this direction and it would be nice to discuss them as well as new ideas.) First, as an appetizer, the very basic argument described for polytopes. Here 
(Click on the picture to get it readable.)
The main observation here (and also in the abstract versions of the proof) is that
if we walk from a vertex 
But it stands to reason that we can do better.
Suppose that 
The main observation we just mentioned implies that with paths of this length starting with the vertex 
Combinatorics and more 
I found the following on the web:
Click to access 12-08.pdf
It is paper in which the author claims a proof of the Hirsch conjecture in the general bounded case.
Hmm, the proof is very short but I cannot follow it. (I like the conclusion starting with “Long awaited, this proof is ultimately satisfying to the author.”)
I read this preprint in detail when it came out in January, as the ideas are similar to my thesis work on Hirsch.
The proof contains a basic error early on that is identified in a later version of the paper. As a result, the author no longer claims to prove the Hirsch conjecture.
I do think the overall proof strategy may have merit. When polymath3 launches, I’ll make the case for this category of approaches to Hirsch, as an alternative to abstract diameter bounds.
If there’s interest, I’ll have a short paper out later this week that should be much easier to follow.
I would be interested in this. Is there a copy of the later version of the paper somewhere?
The last error-free version I can find seems to have disappeared from the web, but if you email me (anand at berkeley.edu) I’ll pass along the copy I have.
Just checking now, the author has put up a recent version on his site, but it still seems to have the same problem:
Click to access Hirsch.pdf
I think that if I think about the problem, it would be the third direction which would concern me most, because it’s more fun to find new ways of looking at things…
The problem is Tao’s “conservation of difficulty” principle, which suggests that a direct attack on the Hirsch conjecture might be very difficult (although it might be much easier for the analogues you are suggesting to consider), if there are no deep results in close proximity with the Hirsch conjecture to help us along.
On think I’m wondering is whether there aren’t diameter-preserving (or mildly diameter increasing) local moves on polytopes- whether we can’t “flow the polytope” to simplify it (perhaps using some version of a shelling). Do you know of any ideas along these lines?
The paper that was mentioned in the comments seems to use this “local moves” approach, even though I can’t really follow it, possibly because of the error in it. To me personally, it seems like this kind of approach is what was used very early and lead to the low-dimensional bounds (Klee, Walkup). The difficulty I have with this kind of argument is that it is very easy to be mislead by low-dimensional intuition.
On the other hand, maybe this approach is worth reviving simply because more recent results don’t use it.
This discussion also reminds me of a continuous variant of an abstraction of the problem that I came up with some time ago. It’s a curious problem of which I really have no idea how difficult it is, but maybe I’ll just throw it out there.
Gil: I also wonder if the algebraic shifting techniques you used in analyzing polars of neighbourly polytopes can be of use? I have to admit that I never fully understood that article…
Pingback: Polymath on other blogs « The polymath blog
I had indeed a proof of polynomial upper bound for the diameter for dual-to-neighborly polytopes. It used a certain mild expansion properties of their graphs which indeed relies on algebraic shifting. At the time I convinced myself that these methods cannot be useful in the general case. But maybe we should give it another thought.
As for local moves. There are the famous “Pachner moves” which allow you to move between any simplicial polytope to any other (and between PL spheres) but somehow I do not see how to control the diameter.
Here’s another random thought about abstractions. While the final goal is obviously to get general results, it could potentially be instructive to think about low-dimensional cases.
In the abstract setting of our paper, only the cases d=1 and d=2 are essentially closed, with the maximum diameter being n-1 for d=1 and 2n (modulo lower order terms) for d=2.
The case d=3 is open. On the one hand, we can get “essentially” 3n as a lower bound from our construction. On the other hand, the best upper bound I know is 4n (from 2^(d-1)n).
Settling the case d=3 for the abstraction would already be quite impressive, in my opinion, and should be easier than going for the full general abstract case.
(Of course, the case d=3 for polytopes has long been solved, by very geometric techniques; the kind of geometry used to settle d=3 for polytopes simply disappears in the abstraction)
Dear nh, this is certainly good problem. One thing that bothers me is that all these abstractions does not see to contain the case of non simple polytopes (and polyhedra). We know that the diameter upper bounds can be reduced to the simple case, yet it will be more elegant if we have an abstract setting that include the non simple case as well. (Maybe your setting includes the non simple case, I just do not see it.)
Indeed we do not consider the non-simple case.
I remember that in a significantly older version we wanted to also consider the non-simple case simply by allowing sets that are larger than d. If I remember correctly, it did work but we eventually decided to drop this possibilty to make the exposition simpler, and it was also more in line with abstractions that had been considered earlier.
I would have to think more on it to be certain, but I’m going to be offline for the next few weeks.
Pingback: The Polynomial Hirsch Conjecture: Discussion Thread, Continued « Combinatorics and more
Pingback: Polymath again « What Is Research?