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 non-empty families of subsets [math]\displaystyle{ F_1,\ldots,F_t }[/math] of [math]\displaystyle{ \{1,\ldots,n\} }[/math] that are disjoint (i.e. no set S can belong to two of the families [math]\displaystyle{ F_i, F_j }[/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?

Trivially, f(n) is non-decreasing in n, f(0)=1 (take [math]\displaystyle{ \{ \emptyset\} }[/math]), f(1)=2 (take e.g. [math]\displaystyle{ \{\emptyset\}, \{\{1\}\} }[/math]), and f(2)=4 (take e.g. [math]\displaystyle{ \{ \emptyset\}, \{ \{1 \}\}, \{ \{1,2\}\}, \{2\} }[/math]).

<bf>Theorem 1</bf> For any [math]\displaystyle{ n \gt 1 }[/math], [math]\displaystyle{ f(n) \leq f(n-1) + 2 f(\lfloor n/2\rfloor)\lt math\gt . '''Proof''' Consider t families \lt math\gt F_1,\ldots,F_t \subset \{1,\ldots,n\} }[/math] obeying (*). Consider the largest s so that the union of all sets in [math]\displaystyle{ F_1 \cup \ldots \cup F_s }[/math] is at most n/2. Clearly, [math]\displaystyle{ 0 \leq s \leq f(\lfloor n/2\rfloor) }[/math].

Consider the largest r so that the union [math]\displaystyle{ \bigcup (F_{n-r+1} \cup \ldots \cup F_n) }[/math] of all sets in [math]\displaystyle{ F_{n-r+1} \cup \ldots \cup F_n }[/math] is at most n/2. Clearly, [math]\displaystyle{ 0 \leq r \leq f(\lfloor n/2\rfloor) }[/math].

If [math]\displaystyle{ t \leq s+r }[/math] then we are done, so suppose that [math]\displaystyle{ t \gt s+r }[/math]. By construction, the sets [math]\displaystyle{ \bigcup(F_1 \cup \ldots \cup F_{s+1}) }[/math] and [math]\displaystyle{ \bigcup(F_{n-r} \cup \ldots \cup F_n) }[/math] both have cardinality more than [math]\displaystyle{ n/2 }[/math] and thus have a common element, say m. By (*), each of the [math]\displaystyle{ t-r-s }[/math] families [math]\displaystyle{ F_{s+1},\ldots,F_{n-r} }[/math] must thus contain a set with this element m. If we then throw away all the sets that don't contain m, and then delete m, we obtain t-r-s non-empty families of an n-1-element set that obey (*), hence [math]\displaystyle{ t-r-s \leq f(n-1) }[/math], and the claim follows. QED

Note: the same argument gives [math]\displaystyle{ f(n) \leq f(n-1) + f(a) + f(b) }[/math] for any positive integers a, b with [math]\displaystyle{ a+b+1 \geq n }[/math]. In particular we have the slight refinement

<math>f(n) \leq f(n-1) + f(\lfloor n/2\rfloor) + f(\lfloor (n-1)/2\rfloor).<math>

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”