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, but will leave the case of polytopes open. (One of the most active areas of convex polytope theory is methods for constructing polytopes, and there may be several ways to move from an abstract combinatorial example to a geometric example.)

If indeed we will decide to go for a polymath3, the concrete problem which I propose attacking is the APHC. However, we can discuss possible arguments regarding diameter of polytopes which use geometry, and we can be open to even more general abstract forms of the problem. (Or other things that people suggest.)

Reading the recent very short paper by Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss and the 3-pages paper by Sasha Razborov (the merged journal paper of these two contributions will become available soon, ) will get you right to the front lines. (There is an argument from the first paper that uses the Hall-marriage theorem, and an argument from the second paper that uses the “Lovasz local lemma”.)

I will try to repeat in later posts the simple arguments from these papers – I plan to devote one post to the upper bounds, another post to the lower bounds, and yet another post to general background, motivation and cheerleading for the problem. I will try to make the different posts self-contained.

Questions and remarks about polytopes, the problem, or these papers are welcome.

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

Pingback: The Polynomial Hirsch Conjecture: A proposal for Polymath3 « Combinatorics and more
Kristal Cantwell says:

July 29, 2009 at 2:26 am

I look forward to hearing more about this.

Gil Kalai says:

July 31, 2009 at 12:47 pm

Thanks Kristal. Let me make one additional remark on the abstract setting. The condition is that if we have two vertices $v$ with lebel $S$ and $w$ with label $T$ there is a path between them with vertices labelled by sets containing $S \cap T$ . We do not make the dual assumption that we can move between $v$ to latex $w$ by sets all whose labels are included in $S \cup T$ . (Indeed, this is not the case for simple polytopes when we labeled a vertex by the set of facets containing it. If we could guarantee that the labels are always inside $S \cup S$ and containing $S \cap T$ then the diameter would be $d$ .

Pingback: Polymath on other blogs « The polymath blog
Pingback: The Polynomial Hirsch Conjecture: Discussion Thread, Continued « Combinatorics and more

	My First Paper with… on Nostalgia corner: John Riordan…
	jamesmessig on My Notices AMS Paper on Quantu…
	Gil Kalai on My Notices AMS Paper on Quantu…
	jamesmessig on My Notices AMS Paper on Quantu…
	Gil Kalai on Physics Related News: Israel J…
	My Notices AMS Paper… on Three Remarkable Quantum Event…
	My Notices AMS Paper… on The Quantum Computer Puzzle @…
	My Notices AMS Paper… on Random Circuit Sampling: Fouri…
	My Notices AMS Paper… on Photonic Huge Quantum Advantag…
	My Notices AMS Paper… on Ordinary computers can beat Go…
	My Notices AMS Paper… on Amazing: Feng Pan and Pan Zhan…
	Gil Kalai on Three Remarkable Quantum Event…