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.
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 can be found in this 3-page note by Rasborov. A merged paper by Eisenbrand, Hahnle, Razborov, and Rothvoss is coming soon. The short paper of Eisenbrand, Hahnle, and Rothvoss contains also short proofs in the most abstract setting of the known upper bounds for the diameter.
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 whose vertices are labeled by -subsets of an element set. The only condition is that if is a vertex labeled by and is a vertex labelled by the set , then there is a path between and so that all labelling of its vertices are sets containing .
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 elements then these two vertices are adjacent.