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].

Can one give a bound on t which 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{ t \leq n^{\log n + 1} }[/math] by an elementary argument, given here.

In [EHRR] it is noted that t can be of quadratic size in 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”