The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.


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 \Delta (d,n) is the maximum diameter of the graph of a d-dimensional polyhedron with n facets.



(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 v in all possible directions \Delta(d,k) steps we can reach vertices on at least k+1 facets.

But it stands to reason that we can do better.

Suppose that n is not too small (say n=d^2.). Suppose that we start from a vertex v and walk in all possible directions t steps for

t=\Delta (d,10d)+\Delta (d-1,10d)+\Delta(d-2,10d)+\dots +\Delta(2,10d).  (We can simply take the larget quantity t = d \Delta (d,11d).)

The main observation we just mentioned implies that with paths of this length starting with the vertex v we can reach vertices on 10d facets  and on every facet we reach we can reach vertices on 10d facets and in every facet of a facet we can reach vertices on 10d facets and so on. It seems that following all these paths we will be able to reach vertices on many many more than 10d facets. (Maybe a power greater than one of d or more.)  Unless, unless something very peculiar happens that perhaps we can analyze as well.