The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture


A convex polytope P is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have a facial structure: A (proper) face of a polytope P is the intersection of  P with a supporting hyperplane. (A hyperplane H is a supporting hyperplane of P if P is contained in a closed halfspace bounded by H, and the intersection of H and P is not empty.) We regard the empty face and the entire polytope as trivial faces. The extreme points of a polytope P are called its vertices. The one-dimensional faces of P are called edges. The edges are line intervals connecting a pair of vertices. The graph G(P) of a polytope P  is a graph whose vertices are the vertices of P and two vertices are adjacent in G(P) if there is an edge of P connecting them. The (d-1)-dimensional faces of a polytop are called facets.  

The Hirsch conjecture: The graph of a d-polytope with n  facets has diameter at most n-d.

A weaker conjecture which is also open is:

Polynomial Hirsch Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial in d and n.

The avenue which I consider most promising (but I may be wrong) is to replace “graphs of polytopes” by a larger class of graphs. Most known upper bound on the diameter of graphs of polytopes apply in much larger generality. Recently, interesting lower bounds were discovered and we can wonder what they mean for the geometric problem.    

Here is the (most recent) abstract setting:

Consider the collection {\cal G}(d,n) of graphs G whose vertices are labeled by d-subsets of an n element set.

The only condition we will require is that if  v is a vertex labeled by S and u is a vertex labeled by the set T, then there is a path between u and v so that all labels of its vertices are sets containing S \cap T.

Abstract Polynomial Hirsch Conjecture (APHC): Let G \in {\cal G}(d,n)  then the diameter of G is bounded above by a polynomial in d and n.

Everything that is known about the APHC can be described in a few pages. It requires only rather elementary combinatorics; No knowledge about convex polytopes is needed.

A positive answer to APHC (and some friends of mine believe that n^2 is the right upper bound) will apply automatically to convex polytopes.

A negative answer to APHC will be (in my opinion) extremely interesting as well, Continue reading

The Polynomial Hirsch Conjecture: A proposal for Polymath3


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 n^{3/2}.

Update (July 20) An improved lower bound of \Omega(n^2/\log n) 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: Continue reading