The polynomial Hirsch conjecture

The polynomial Hirsch conjecture (or polynomial diameter conjecture) states the following:

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 approach to this problem is purely combinatorial. It is known that this conjecture follows from

Combinatorial polynomial Hirsch conjecture: Consider t disjoint families of subsets [math]\displaystyle{ F_1,\ldots,F_t }[/math] of [math]\displaystyle{ \{1,\ldots,n\} }[/math]. Suppose that

For every [math]\displaystyle{ i \lt j \lt k }[/math], and every [math]\displaystyle{ S \in F_i }[/math] and [math]\displaystyle{ T \in F_k }[/math], there exists [math]\displaystyle{ R \in F_j }[/math] such that [math]\displaystyle{ S \cap T \subset R }[/math].

Let f(n) be the largest value of t for which this is possible.

Conjecture: f(n) is of polynomial size in n.

Threads

• The polynomial Hirsch conjecture, a proposal for Polymath 3 (July 17, 2009)
• The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. (July 28, 2009)
• The polynomial Hirsch conjecture - how to improve the upper bounds (July 30, 2009)
• The Polynomial Hirsch Conjecture: Discussion Thread (Aug 9, 2009)
• The Polynomial Hirsch Conjecture: Discussion Thread, Continued (Oct 6, 2009)
• Plans for polymath3 (Dec 8, 2009)
• The Polynomial Hirsch Conjecture: The Crux of the Matter. (Jun 19, 2010)
• Polynomial Hirsch Conjecture (Sep 29, 2010)

• Wordpress posts on the Hirsch conjecture

Partial results and remarks

In the setting of the combinatorial Hirsch conjecture, one can obtain the bound [math]\displaystyle{ f(n) \leq n^{\log n + 1} }[/math] by an elementary argument, given here.

In [EHRR] it is noted that f(n) is at least quadratic in n.

What are the best upper and lower bounds on f(n) for small n?

Background and terminology

(Maybe some history of the Hirsch conjecture here?)

The disproof of the Hirsch conjecture

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

This conjecture was recently disproven by Francisco Santos [S].

• Santos's page on the Hirsch conjecture
• Francisco Santos Disproves the Hirsch Conjecture (May 10, 2010)
• “A Counterexample to the Hirsch Conjecture,” is Now Out (Jun 15, 2010)

Bibliography

(Expand this biblio!)

• [EHRR] Freidrich Eisenbrand, Nicolai Hahnle, Sasha Razborov, and Thomas Rothvoss, "Diameter of Polyhedra: The Limits of Abstraction", preprint.
• [S] Francisco Santos, "A counterexample to the Hirsch conjecture", preprint.

Other links

• Math Overflow thread: A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”