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) }[/math].

Proof Consider t families [math]\displaystyle{ 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]\displaystyle{ f(n) \leq f(n-1) + f(\lfloor n/2\rfloor) + f(\lfloor (n-1)/2\rfloor). }[/math]

f(n) for small n

Notation: we abbreviate {1} as 1, {1,2} as 12, [math]\displaystyle{ \emptyset }[/math] as 0, etc.

We trivially have [math]\displaystyle{ f(n) \leq 2^n }[/math]. This bound is attained for n=0,1,2, by considering the following families:

(n=0) {0}

(n=1) {0}, {1}

(n=2) {0}, {1}, {12}, {2}.

However it is not attained for n=3. Here we have f(3)=6. The lower bound f(3) >= 6 is established using the example

{0}, {2}, {12}, {1}, {13}, {3}.

To show that f(3) <= 6, assume for contradiction that we have seven families obeying (*). Suppose that one of these families, say F_i, contained 123. Then by (*), for any set R in F_j for j < i, there is a set in F_{j+1} that contains R. Thus there is an ascending chain of sets in [math]\displaystyle{ F_1, F_2, ..., F_{i-1} }[/math], and similarly for [math]\displaystyle{ F_7, F_6, \ldots, F_{i+1} }[/math]. Also, at most one of these chains can contain the empty set, and neither of them can contain 123. Thus one of the chains has length at most 3 and the other has length at most 2, giving rise to just 6 families instead of 7, contradiction.

So the only remaining possibility is if the remaining 7 sets 0, 1, 2, 3, 12, 23, 31 are distributed among the 7 families so that each family consists of a single set. Without loss of generality we may assume that 1 appears to the left of 2, which appears to the left of 3. By (*), this means that none of the families to the left of 2 can contain a set with a 3 in it, and none of the families to the right of 2 can contain a set with a 1 in it. But then there is no place for 13 to go, a contradiction.

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”