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

Here is a list of Wordpress posts on the Hirsch conjecture

Possible strategies

(some list here?)

Terminology

A convex sequence of families on a domain [math]\displaystyle{ X }[/math] is a sequence [math]\displaystyle{ F_1,\ldots,F_t }[/math] of non-empty families of subsets of [math]\displaystyle{ X }[/math] which are disjoint ([math]\displaystyle{ F_i \cap F_j = \emptyset }[/math] for all [math]\displaystyle{ i\lt j }[/math]) and obey the convexity condition (*). We call [math]\displaystyle{ t }[/math] the length of the convex family. Thus, [math]\displaystyle{ f(n) }[/math] is the largest length of a convex sequence of families on [math]\displaystyle{ [n] }[/math].

The support or 1-shadow [math]\displaystyle{ U_i \subset X }[/math] of a family [math]\displaystyle{ F_i }[/math] of subsets of X is defined as

[math]\displaystyle{ U_i := \bigcup_{E \in F_i} E = \{ x \in X: x \in E \hbox{ for some } E \in F_i \} }[/math].

If [math]\displaystyle{ F_1,\ldots,F_t }[/math] is a convex sequence of families, then the supports obey the convexity condition [math]\displaystyle{ U_i \cap U_k \subset U_j }[/math] for all [math]\displaystyle{ i \lt j \lt k }[/math].

More generally, given any [math]\displaystyle{ r \geq 1 }[/math], define the r-shadow [math]\displaystyle{ U_i^{(k)} \subset \binom{X}{r} := \{ A \subset X: |A|=r\} }[/math] as

[math]\displaystyle{ U_i^{(r)} := \bigcup_{E \in F_i} \binom{E}{r} = \{ A \in \binom{X}{r}: A \subset E \hbox{ for some } E \in F_i \} }[/math].

Then the r-shadows are also convex: [math]\displaystyle{ U_i^{(r)} \cap U_k^{(r)} \subset U_j^{(r)} }[/math] whenever [math]\displaystyle{ i \lt j \lt k }[/math].

Suppose an interval [math]\displaystyle{ F_i,\ldots,F_k }[/math] of families contains a common element [math]\displaystyle{ m\in X }[/math] in the supports [math]\displaystyle{ U_i,\ldots,U_k }[/math]. (By convexity, this occurs whenever [math]\displaystyle{ m }[/math] belongs to both [math]\displaystyle{ U_i }[/math] and [math]\displaystyle{ U_k }[/math].) Then one can define the restriction [math]\displaystyle{ F_i^{-m},\ldots,F_k^{-m} }[/math] of these families by m by the formula

[math]\displaystyle{ F_j^{-m} := \{ A \subset X \backslash \{m\}: A \cup \{m\} \in F_j \}; }[/math]

one can verify that this is also a convex family. More generally, if the r-shadows [math]\displaystyle{ U^{(r)}_i }[/math] and [math]\displaystyle{ U^{(r)}_k }[/math] (and hence all intermediate r-shadows [math]\displaystyle{ U^{(r)}_j }[/math] for [math]\displaystyle{ i \lt j \lt k }[/math]) contain a common element [math]\displaystyle{ B \in \binom{X}{r} }[/math]), then the restriction

[math]\displaystyle{ F_j^{-B} := \{ A \subset X \backslash B: A \cup B \in F_j \} }[/math]

is also a convex family.

Partial results and remarks

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

Trivially, f(n) is non-decreasing in n.

Without loss of generality, we may assume that one of the extreme families consists only of the empty set. We may then delete that family, at the cost of decreasing the number of families by 1, and work under the assumption that the empty set is not present. (But for inductive purposes it seems to be convenient to have the empty set around.)

Even after the empty set is removed, we may assume without loss of generality that the two extreme families are singleton sets, since we can throw out all but one element from each extreme family.

We may assume that all families are antichains, since we can throw out any member of a family that is contained in another member of the same family.

The support [math]\displaystyle{ U_i := \bigcup_{E \in F_i} E }[/math] of a family can only change at most 2n times (adopting the convention that F_i is empty for i<1 or i>t. Indeed, as i increases, once an element is deleted from the support, it cannot be reinstated. This already gives the bound [math]\displaystyle{ t \leq 2n }[/math] in the case when all the F_i are singleton sets.

In particular, this shows that by paying a factor of 2n at worst in t, one can assume without loss of generality that all families have maximum support.

Theorem 1 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 cumulative support [math]\displaystyle{ U_{[1,s]} := U_1 \cup \ldots \cup U_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 cumulative support [math]\displaystyle{ U_{[n-r+1,n]} := U_{n-r+1} \cup \ldots \cup U_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{ U_{[1,s+1]} }[/math] and [math]\displaystyle{ U_{[n-r,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] supports [math]\displaystyle{ U_{s+1},\ldots,U_{n-r} }[/math] must thus contain this element m. The restriction of [math]\displaystyle{ F_{s+1},\ldots,F_{n-r} }[/math] is then a convex family on [math]\displaystyle{ [n]\backslash \{m\} }[/math], 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]

In fact we can boost this a bit to

[math]\displaystyle{ f(n) \leq f(n-1) + f(\lfloor n/2\rfloor) + f(\lfloor (n-1)/2\rfloor)-1 }[/math] (1)

by noting that at most one of the left and right chains of families can contain the empty set (and we can always assume without loss of generality that the empty set is on one side).

Iterating this gives [math]\displaystyle{ f(n) \leq n^{\log_2 n+1} }[/math] for [math]\displaystyle{ n \geq 2 }[/math] (in fact I think we can sharpen this a bit to [math]\displaystyle{ O( n^{\log_2 n / 2 - c \log\log n} ) }[/math]).

f(n) for small n

• f(0)=1
• f(1)=2
• f(2)=4
• f(3)=6
• 8 <= f(4) <= 11.

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

More generally, the example

{0}, {1}, {12}, {123}, ..., {123...n}, {23...n}, {3...n}, ..., {n} (2)

shows that [math]\displaystyle{ f(n) \geq 2n }[/math] for any n >= 1.

For instance this gives f(3) > =6. (But there are other 6-family examples that work here, e.g. {0}, {1}, {12}, {2}, {23}, {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.

For f(4), the example (2) gives a lower bound of 8, while the bound (1) gives an upper bound of 6+4+2-1 = 11. Can we do better?

If a sequence of families obeying (*) contains [math]\displaystyle{ 12\ldots n }[/math], then it contains an ascending chain to the left of this set and a descending chain to the right, and thus has length at most 2n. In particular, any sequence of families in [4] of length greater than 8 cannot contain 1234.

So we may assume without loss of generality that 1234 does not appear. This implies that if two sets A, B appear in families F_i, F_j and [math]\displaystyle{ |A \cap B| \geq 2 }[/math], then [math]\displaystyle{ |i-j| \leq 2 }[/math], because there can be at most three families that contain [math]\displaystyle{ A \cap B }[/math] if the full set 1234 is excluded.

f(d,n)

Let [math]\displaystyle{ f(d,n) }[/math] be the largest number of families obeying (*) in which all families consist only of [math]\displaystyle{ d }[/math]-element sets. Thus, for instance, [math]\displaystyle{ f(0,n)=1 }[/math] and [math]\displaystyle{ f(1,n)=n }[/math]. We claim that [math]\displaystyle{ f(d,n) \leq 2^{d-1} n }[/math] for [math]\displaystyle{ d=1,2,3,\ldots }[/math]. (This argument is from [AHRR].)

We prove this by induction on [math]\displaystyle{ d }[/math]. The case [math]\displaystyle{ d=1 }[/math] is trivial, so now suppose [math]\displaystyle{ d\gt 1 }[/math]. We consider the supports [math]\displaystyle{ U_1, U_2, \ldots, U_t }[/math] of [math]\displaystyle{ F_1, \ldots, F_t }[/math]. Set [math]\displaystyle{ a_1 := 1 }[/math], set [math]\displaystyle{ a_2 }[/math] to be the first label for which [math]\displaystyle{ U_{a_2} }[/math] is disjoint from [math]\displaystyle{ U_{a_1} }[/math], let [math]\displaystyle{ a_3 }[/math] be the first label for which [math]\displaystyle{ U_{a_3} }[/math] is disjoint from [math]\displaystyle{ U_{a_2} }[/math], and so forth until one reaches [math]\displaystyle{ a_m = t+1 }[/math] (by convention we set [math]\displaystyle{ U_{t+1} }[/math] to be empty).

From (*) we have the convexity condition [math]\displaystyle{ U_i \cap U_k \subset U_j }[/math] for [math]\displaystyle{ i \lt j \lt k }[/math], which implies that if we set [math]\displaystyle{ S_i := U_{a_i} \cup \ldots \cup U_{a_{i+1}-1} }[/math], then the [math]\displaystyle{ S_i }[/math] and [math]\displaystyle{ S_j }[/math] are disjoint for [math]\displaystyle{ |j-i| \geq 2 }[/math]. In particular, [math]\displaystyle{ \sum_i |S_i| \leq 2n }[/math]. On the other hand, by construction and convexity, all the supports [math]\displaystyle{ U_{a_i},\ldots,U_{a_{i+1}-1} }[/math] have a common element. Restricting by this element and using the induction hypothesis, we conclude that [math]\displaystyle{ a_{i+1}-a_i \leq 2^{d-2} |S_i| }[/math] for each [math]\displaystyle{ i }[/math]. Summing in [math]\displaystyle{ i }[/math] we obtain the claim.

In fact we get a slight refinement [math]\displaystyle{ f(d,n) \leq 2^{d-1} n-2^{d-1}+1 }[/math], since [math]\displaystyle{ U_1 }[/math] is contained in [math]\displaystyle{ S_1 }[/math] but is disjoint from all the other [math]\displaystyle{ S_i }[/math], allowing one to get the improved bound [math]\displaystyle{ \sum_i |S_i| \leq 2n-1 }[/math].

The above argument works for multisets (in which the d-element sets [math]\displaystyle{ \{x_1,\ldots,x_d\} }[/math] in the families [math]\displaystyle{ F_i }[/math] are allowed to have multiplicity). In that case, the bound [math]\displaystyle{ 2n-1 }[/math] on [math]\displaystyle{ f(2,n) }[/math] is actually attained, as can be seen by the example

[math]\displaystyle{ F_i := \{ \{a,b\}: a+b = i+1\} }[/math] for [math]\displaystyle{ i=1,\ldots,2n-1 }[/math].

More generally, one has a lower bound [math]\displaystyle{ f(d,n) \geq dn-d+1 }[/math] in the multiset case from the example

[math]\displaystyle{ F_i := \{ \{a_1,\ldots,a_d\}: a_1+\ldots+a_d = i+d-1\} }[/math] for [math]\displaystyle{ i=1,\ldots,dn-d+1 }[/math].

Question: Can one eradicate the multisets and get a true example of comparable size, say for d=3?

Here is a proof of a weaker upper bound [math]\displaystyle{ f(2,n) \leq 100 n \log n }[/math] in the d=2 case. Suppose for contradiction that we have [math]\displaystyle{ t = 100 n \log n + O(1) }[/math] families. Consider the supports U_i of the i^th family F_i. We claim that [math]\displaystyle{ |U_i| \leq n / (5 \log n) }[/math] for at least one i between [math]\displaystyle{ 45 n/\log n }[/math] and [math]\displaystyle{ 55 n/\log n }[/math], because otherwise each F_i would need to have at least [math]\displaystyle{ \binom{n/(5\log n)}{2} }[/math] edges, and there are not enough edges for this. But then the families F_1,...,F_i are supported in a set of size m and F_{i+1},...,F_n are supported in a set of size k with [math]\displaystyle{ m+k \leq n+|U_i| \leq n + n/(5 \log n) }[/math]. On the other hand, from the induction hypothesis we see that k, m have to be at least 0.4 n, and thus at most 0.6 n. We conclude that

[math]\displaystyle{ 100 n \log n + O(1) \leq 100 k \log (0.6n) + 100 m \log (0.6 n) \leq 100 (n + n/(5 \log n)) (\log 0.6 n) }[/math]

which gives a contradiction.

The combinatorial conjecture implies the polynomial Hirsch conjecture

The following result is from [AHRR]:

Theorem 2 A simple polytope with n faces has at a diameter of at most f(n).

Proof Start with a d-dimensional polytope with n facets. To every vertex v of the polytope associate the set [math]\displaystyle{ S_v }[/math] of facets containing . Starting with a vertex w, we can consider [math]\displaystyle{ F_i }[/math] as the family of sets which correspond to vertices of distance i+1 from $w$. So the number of such families (for an appropriate w is as large as the diameter of the graph of the polytope.

Why the families of graphs of simple polytopes satisfy (*)? Suppose you have a vertex v of distance i from w, and a vertex u at distance k>i. Then consider the shortest path from v to u in the smallest face containing both v and u. The sets S_z for every vertex z in (and hence on this path) satisfies [math]\displaystyle{ S_v \cap S_u \subset S_z }[/math]. The distances from w of adjacent vertices in the shortest path from u to v differs by at most 1. So one vertex on the path must be at distance j from w. QED

Background

(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”