The Abstract Polynomial Hirsch Conjecture
A convex polytope 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 is the intersection of with a supporting hyperplane. (A hyperplane is a supporting hyperplane of if is contained in a closed halfspace bounded by , and the intersection of and is not empty.) We regard the empty face and the entire polytope as trivial faces. The extreme points of a polytope are called its vertices. The one-dimensional faces of are called edges. The edges are line intervals connecting a pair of vertices. The graph of a polytope is a graph whose vertices are the vertices of and two vertices are adjacent in if there is an edge of connecting them. The -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 of graphs whose vertices are labeled by -subsets of an element set.
The only condition we will require is that if is a vertex labeled by and is a vertex labeled by the set , then there is a path between and so that all labels of its vertices are sets containing .
Abstract Polynomial Hirsch Conjecture (APHC): Let then the diameter of is bounded above by a polynomial in and .
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 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