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,\dots,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.

Let f(d,n) be the largest value of t in the above conjecture for which all F_i have cardinality exactly d. Let f^*(d,n) be the largest value for which the F_i have cardinality t and the sets in the [math]\displaystyle{ F_i }[/math] are allowed to be multisets.

Nicolai's conjecture f^*(d,n) = d(n-1)+1.

This would imply the combinatorial polynomial Hirsch conjecture and hence the polynomial Hirsch conjecture.

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) Inactive
• Polymath3 : Polynomial Hirsch Conjecture 3 (Oct 10, 2010) Active
• Polymath3 : Polynomial Hirsch Conjecture 4 (Oct 21, 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]. ([EHRR], adapting a proof from [KK])

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

Corollary [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

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

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

On the other hand, for every n we have [math]\displaystyle{ f(n) \geq 2n }[/math], as any of the following two examples show.

{0}, {1}, {12}, {2}, {23}, {3}, ... , {n-1 n}, {n}

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

It is worth noting that in these two examples every F_i is a singleton. As mentioned above, in the singleton case the maximum length is in fact 2n.

Theorem For [math]\displaystyle{ n \leq 4 }[/math], [math]\displaystyle{ f(n) =2n }[/math].

Proof For f(1) and f(2) this is given by the "trivial" upper and lower bounds above. For f(3) and f(4) we first state the following two general properties:

• 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 (the maximal possible length in this case is the one achieved by example (2))

• If [math]\displaystyle{ 12\ldots n }[/math] is not used and two subsets A, B of cardinality n-1 appear in families F_i, F_j then [math]\displaystyle{ |i-j| \leq 2 }[/math], because every intermediate F_k contains A\cap B.

WIth these two properties we prove f(3)=6 and f(4)=8 as follows:

• For f(3), we have eight possible subsets of [n] but we can assume that 123 is not used, by the first argument above, which leaves only seven subsets to use. If the length was seven we would be in the singleton case, for which we know 2n is an upper bound: a contradiction. (A different argument is: if the three pairs {12}, {23} and {13} appear in three *different* F_i's, assume wlog that they do in precisely that order. Then the intermediate F_i must also contain {1}. So, the seven subsets give at most six F_i's).

• For f(4), as before, we can assume no F_i contains 1234. We do a case study according to how many of the triplets abc are used. That is, how many of the I(abc)'s are non-empty:

If three or four I(abc) are non-empty, then they are confined to an interval of length 3 by the second property above. It follows that the I(ab) are confined in an interval of length 5 (because any of them is contained in one of the used abc's), and the I(a) are confined in an interval of length 7. We are done because I(\emptyset) contains at most one more element.

The second case is when exactly two I(abc) are non-empty, I(123) and I(124) say. If their values differ by 2 (which is maximum possible), then I(13) and I(23) are confined in an interval E of length 3, I(14) and I(24) are confined in an interval F of length 3, and F intersects E in only one point (between I(123) and I(124)). Now I(34) can be empty, in which case the I(ab) are confined in an interval E\cup F of length 5, or I(34) is a singleton and we only have to show that it is in that same interval. But if it where, e.g., on the right of this interval, then I(3) would have at least 2 points not lying in any of I(13), I(23), I(123) nor I(34), a contradiction. If I(123) and I(124) are adjacent or equal, then all of I(ab) where ab is not 34 are confined in a interval G of length 4, which is a union of two intervals of length 3, the first one containing I(13) and I(23), the second one I(14) and I(24). A similar argument than above proves that I(34) must be adjacent to G, so that once again the I(ab) are confined in an interval of length 5.

The third case is when exactly one of the I(abc) is not empty, I(123) say. Then I(12), I(23) and I(13) are confined in a interval E of length 3 around I(123), and I(14), I(24), I(34) are either empty or singletons. Looking at I(1) shows that (if not empty) I(14) is in the 2-neighborhood of E. But looking at I(4) shows that all non-empty I(a4) are at distance at most 2, so that all I(ab) are confined in some interval of length 5. Some of them could be empty, but in any case it is easily checked that I(\emptyset) is confined in an interval of length 8.

For the fourth case, assume that all I(abc) are empty but some I(ab) are not. Any two I(ab), I(ac) must lie at distance at most 2 (look at I(a) ). If for example I(12) and I(34) where at distance 5 or more, then all other I(ab) would be empty (otherwise they should be close to both I(12) and I(34)), so that I(1), I(2) would be confined in an interval E and I(3), I(4) to an interval F, such that E and F are separated by a gap of length 2. We then get a contradiction by looking at I(\emptyset). We conclude that all non-empty I(ab) are confined in a length 5 interval if all 1234 are represented, or confined in an interval of length 3 otherwise. In both cases, we get the desired conclusion.

Last, consider the case when all I(ab) are empty. Then we have at most 4 points covered by the I(a), and at most 5 by I(\emptyset), and we are (finally) done. QED

Towards the value of [math]\displaystyle{ f(5) }[/math]

The following example shows that f(5) is at least 11: [{}, {1}, {15}, {14, 5}, {12, 35, 4}, {13, 25, 45}, {245, 3}, {24, 34}, {234}, {23}, {2}]

I can now show that f(5) is at most 12. Since we have the above example of length 11, f(5) must be 11 or 12. In fact, as a byproduct of my proof I have also found a second example of length 11: [{}, {1}, {12}, {125}, {15, 25}, {135, 245}, {145, 235}, {35, 45}, {345}, {34}, {4}].

Suppose we have a sequence of length 13 on 5 elements. Wlog the first or last level consists only of the empty set, so we have a sequence of length 12 with no empty sets. Then:

- F_1 \cup F_2 \cup F_3 already use at least three elements: if not, they form the unique sequence of length three with two elements and no empty set, namely [{1}, {12}, {2}]. But in this case the element {1} has already been abandoned in F_3, so it will not be used again. This means that F_3 … F_12 forms a convex sequence of length 10 in four elements, a contradiction.

- With the same argument, F_10 \cup F_11 \cup F_13 use at least three elements. In particular, F_3 and F_10 have a common element, say 5, so restricting F_3,…,F_10 to the sets using 5 we have a sequence of length 8 on the other four elements. So far so good, since f(4)=8.

- But this would imply that in the restriction we can assume wlog that F_3={\emptyset}. Put differently, F_3 contains the singleton {5}. Since F_3 is the first level using 5, this singleton could be deleted from F_3 without breaking convexity. This gets us back to the case where F_1\cupF_2\cup F_3 use only two elements, which we had discarded.

I have been looking at the various cases using the method outlined above. And it looks like all the cases work and f(5) is 11. Let me start going through the cases. It may take a while to work through all of them.

Suppose we have a counterexample that under restriction to sets containing the element 5 contains a set of length 7 which does not contain the set containing only the element 5 but contains a set which under restriction contains all 4 elements then we know that the original set must contain a set which contains all the elements and hence has length 10. So we can eliminate this case.

For the next case assume that in the restriction to sets containing the the element 5 we don’t have a set with four elements and the element 5 and we don’t have a set containing the element 5 only and we have three sets containing the element 5 and three other elements. We note 3 or more sets of three elements and the element 5 contains all combinations of two elements and the element 5.

Now the first family and the second family must contain a set containing at least a pair of elements. If not there are only single elements in the first two elements. Then one element will only appear in one single set which cause the entire case to have at most 9 families and we are done. And the last and the second to last family must also contain a set containing a pair of elements by similar reasoning.

And since all pairs are contained in the three sets containing three or more elements and the element 5 the pairs mentioned at the second and first families and those at the other end must be in the sets of three and the element 5. And this means that the third and third to last families must contain sets containing three or more elements. Now if either of these families doesn’t contain the element 5 then they will contain a common element and then we continue this proof with that element replacing the element 5. If it is a previous case we use the previous proof and if it one the cases to come we will deal with it then.

Next we note that the three sets of three elements and the element 5 must lie within three consecutive positions or else the extremal sets of three elements must contain a common pair which must appear four times which is not possible. Now all the sets of two elements and the element 5 which are contained in the sets of three elements and the element 5 which as we have noted are all the sets of two elements and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these which is a total of five positions. But we have two sets of three elements at both ends of the sequence which correspond to a set of two elements and the element 5 which lie on a span of 7 elements and we have a contradiction and we are done.

For the next case assume that in the restriction to sets containing the the element 5 we don’t have a set with four elements and the element 5 and we don’t have a set containing the element 5 only and we have two sets containing the element 5 and three other elements. We note 2 sets of three elements and the element 5 contains all combinations of two elements and the element 5 except one pair. In this case we will assume that this pair of elements together with the element 5 is present.

Now the first family and the second family must contain a set containing at least a pair of elements. If not there are only single elements in the first two elements. Then one element will only appear in one single set which cause the entire case to have at most 9 families and we are done. And the last and the second to last family must also contain a set containing a pair of elements by similar reasoning.

And since all pairs are contained in the 2 sets containing three or more elements and the element 5 or the set consisting of the remaining pair and the element 5 the pairs mentioned at the second and first families and those at the other end must be in the sets of three and the element 5. And this means that the third and third to last families must contain sets containing three or more elements. Now if either of these families doesn’t contain the element 5 then they will contain a common element and then we continue this proof with that element replacing the element 5. If it is a previous case we use the previous proof and if it one the cases to come we will deal with it then.

Next we note that the two sets of three elements and the element 5 must lie within three consecutive positions or else the extremal sets of three elements must contain a common pair which must appear four times which is not possible. Now all the sets of two elements and the element 5 which are contained in the sets of three elements and the element 5 which as we have noted are all the sets of two elements except 1 and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these which is a total of five positions. But we have two sets of three elements at both ends of the sequence which means that we have the set of two elements not in the two triples together with the element 5 at one end of the sequence.

Now at the other end of the sequence there is set of two or three elements together with the element 5. If there is a set of three elements there is one element in common with besides 5 in one set for each of the 7 elements and we get a contradiction.

So there must be a two element set plus the element 5 at both ends and at one end there must be the two elements in the intersection of the two three element sets plus the element 5 and at the other the two elements in neither set of 3 plus the element 5.

Then the two sets of three elements plus the element 5 must lie in the two spaces following the set of two elements plus the element 5 as there is no remaining element to fill the space between them.

Then the remaining sets of two elements plus the element 5 can only go in the next consecutive slot.

This means that the two slots preceding the set of two elements not in either triple plus the element 5 can only be single elements plus the element 5. But this means that the elements in these sets are disjoint which means that there can be no common elements on either side but either set of three elements plus the element 5 has an element besides the element 5 in common with the set of two elements not in either set of three elements and we have a contradiction and we are done.

f(d,n)

Let [math]\displaystyle{ f(d,n) }[/math] denote the maximum possible length of a convex $d$-uniform sequence of families of subsets of [math]\displaystyle{ [n] }[/math]. Let [math]\displaystyle{ f^*(d,n) }[/math] denote the maximum possible length of a convex $d$-uniform sequence of families of multi-subsets of [math]\displaystyle{ [n] }[/math].

That [math]\displaystyle{ f^*(d,n) }[/math] is at least equal to the conjectured [math]\displaystyle{ d(n-1)+1 }[/math] is shown by two examples:

[math]\displaystyle{ F_i := \{ \{a_1,a_2,\dots,a_d\}: \sum a_i = i+d-1\} }[/math] for [math]\displaystyle{ i=1,\ldots,d(n-1)+1 }[/math].

[math]\displaystyle{ F_1 := \{11\dots11\}, F_2 := \{11\dots12\}, \dots F_d := \{12\dots22\}, :\lt math\gt F_{d+1} := \{22\dots22\}, F_{d+2} := \{22\dots23\}, \dots F_{2d} := \{23\dots33\}, : \dots :\lt math\gt F_{(n-2)d+1} := \{n-1,n-1,\dots,n-1,n-1\}, \dots, F_{(n-1)d} := \{n-1,n,\dots,n,n\}, F_{(n-1)d+1} := \{n,n,\dots,n,n\}. : Question: Can one eradicate the multisets and get a true example of comparable size, say for d=3? The answer seems to be ''yes'': \lt math\gt f(2,n)\ge 2n-O(\log n) }[/math], [math]\displaystyle{ f(d,n)\ge dn-O(d \log n) }[/math], ...

As for upper bounds, to show that [math]\displaystyle{ f^*(d,n) \le 2^{d-1}(n-1) + 1 }[/math] and [math]\displaystyle{ f(d,n) \le 2^{d-1}(n-d) + 1 }[/math], we use the following lemma:

Lemma 1: Let [math]\displaystyle{ \{F_i\}_{i=1}^t }[/math] be a convex and [math]\displaystyle{ d }[/math]-uniform sequence of families of multisets in the alphabet [math]\displaystyle{ [n] }[/math]. Then, there is a partition of [math]\displaystyle{ \{1,\dots,t\} }[/math] into disjoint intervals [math]\displaystyle{ I_1=\{1,\dots,t_1\} }[/math], [math]\displaystyle{ I_2=\{t_1+1,\dots,t_2\} }[/math], ..., [math]\displaystyle{ I_m=\{t_{m-1}+1,\dots,t\} }[/math] with the following properties:

1) For every [math]\displaystyle{ k }[/math], [math]\displaystyle{ \cap_{i\in I_k} support(F_i) }[/math] is not empty.

2) Each [math]\displaystyle{ a\in [n] }[/math] is in the support of at most two of the [math]\displaystyle{ I_k }[/math]'s.

3) If [math]\displaystyle{ a\in support(F_1) }[/math] then [math]\displaystyle{ a }[/math] is not in the support of any [math]\displaystyle{ I_k }[/math] other than [math]\displaystyle{ I_1 }[/math].

In parts (2) and (3) we call support of [math]\displaystyle{ I_k }[/math] the union [math]\displaystyle{ \cup_{i\in I_k} support(F_i) }[/math].

Proof We consider the supports [math]\displaystyle{ U_1, U_2, \dots, U_t }[/math] of [math]\displaystyle{ F_1, \ldots, F_t }[/math]. Set [math]\displaystyle{ t_0=0 }[/math]; let [math]\displaystyle{ t_1 }[/math] be the last label for which [math]\displaystyle{ U_{t_1} }[/math] is not disjoint from [math]\displaystyle{ U_{t_0+1}=U_1 }[/math], let [math]\displaystyle{ t_2 }[/math] be the last label for which [math]\displaystyle{ U_{t_2} }[/math] is not disjoint from [math]\displaystyle{ U_{t_1+1} }[/math], and so forth until one reaches [math]\displaystyle{ t_m = t }[/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_{t_{i-1}+1} \cup \ldots \cup U_{t_{i}} }[/math], then the [math]\displaystyle{ S_i }[/math] and [math]\displaystyle{ S_j }[/math] are disjoint for [math]\displaystyle{ |j-i| \geq 2 }[/math] (condition 2). By construction and convexity, all the supports [math]\displaystyle{ U_{t_{i-1}+1},\ldots,U_{t_{i}} }[/math] have a common element (condition 1). Condition 3 holds by choice of [math]\displaystyle{ t_1 }[/math]. QED

Corollary 1: [math]\displaystyle{ f^*(d,n)\le 2^{d-1} (n-1) + 1 }[/math].

Proof: For [math]\displaystyle{ d=1 }[/math] this is obvious, for [math]\displaystyle{ d\gt 1 }[/math] we use induction on [math]\displaystyle{ d }[/math].

Consider the partition in the lemma above. Let [math]\displaystyle{ S_k }[/math] be the support of [math]\displaystyle{ I_k }[/math], that is, the union of the supports of the [math]\displaystyle{ F_i }[/math]'s with [math]\displaystyle{ i\in I_k }[/math]. Let [math]\displaystyle{ a_k }[/math] be an element that is active in the whole of [math]\displaystyle{ I_k }[/math]. Restricting [math]\displaystyle{ \{F_i\}_{i\in I_k} }[/math] to the multisets that contain [math]\displaystyle{ a_k }[/math] (and then deleting one copy of [math]\displaystyle{ a_k }[/math] from each) gives a convex [math]\displaystyle{ (d-1) }[/math]-uniform sequence of families of multisets of length [math]\displaystyle{ | I_k | }[/math] on [math]\displaystyle{ |S_k| }[/math] elements, so:

[math]\displaystyle{ t= \sum_{i=1}^m |I_k| \le \sum_{i=1}^m f^*(d-1, |S_k|) \le 2^{d-2} (\sum_{i=1}^m|S_k| -m) +m }[/math].

Now, conditions (2) and (3) in the lemma imply that [math]\displaystyle{ \sum|S_k| \le 2n -1 }[/math], (with equality only possible if the support of [math]\displaystyle{ F_1 }[/math] is a single element, that is if [math]\displaystyle{ F_1=\{aaa\dots aa\} }[/math]). Hence:

[math]\displaystyle{ 2^{d-2} (\sum|S_k| -m) +m \le 2^{d-1}(n-1) -(m-1)2^{d-2} +m }[/math],

so to finish the proof we only need to show that [math]\displaystyle{ 1\ge m-(m-1)2^{d-2} }[/math], or, equivalently, that [math]\displaystyle{ (m-1)(2^{d-2} -1) \ge 0 }[/math]. This holds trivially. QED

Observe that in the last step equality can only be obtained only if [math]\displaystyle{ d=2 }[/math], in which case we indeed know that the bound is tight. (The factor [math]\displaystyle{ m-1 }[/math] is always positive since [math]\displaystyle{ m=1 }[/math] implies there is an element in the support of every [math]\displaystyle{ F_i }[/math] and we could then conclude [math]\displaystyle{ t\le f^*(d-1,n) }[/math].

Corollary 2: [math]\displaystyle{ f(d,n)\le 2^{d-1} (n-d) + 1 }[/math].

Proof: basically the same except now the length of each [math]\displaystyle{ I_k }[/math] is bounded by [math]\displaystyle{ f(d-1,|S_k|-1) }[/math] (the deleted element [math]\displaystyle{ a_k }[/math] can no longer appear in the [math]\displaystyle{ (d-1) }[/math]-uniform subsequences).

[math]\displaystyle{ t= \sum_{i=1}^m |I_k| \le \sum_{i=1}^m f(d-1, |S_k|-1) \le 2^{d-2} (\sum_{i=1}^m|S_k| -md) +m }[/math].

Now the support of [math]\displaystyle{ F_1 }[/math] has at least [math]\displaystyle{ d }[/math] elements, so we have [math]\displaystyle{ \sum|S_k| \le 2n -d }[/math], (with equality again only possible if the support of [math]\displaystyle{ F_1 }[/math] is a single element). Hence:

[math]\displaystyle{ 2^{d-2} (\sum|S_k| -md) +m \le 2^{d-2}(2n -d-md) +m = 2^{d-1}(n-d) - 2^{d-2}(m-1)d + m }[/math].

So to finish the proof we only need to show that [math]\displaystyle{ 1\ge m-d(m-1)2^{d-2} }[/math], or, equivalently, that [math]\displaystyle{ (m-1)(d2^{d-2} -1) \ge 0 }[/math]. QED

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 [EHRR]:

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.

• [KK] Gil Kalai and Daniel J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Amer. Math. Soc., 26:315-316, 1992.

• [L] David G. Larman, Paths of polytopes, Proc. London Math. Soc., 20(3):161-178, 1970.

• [S] Francisco Santos, "A counterexample to the Hirsch conjecture", preprint.

Other links

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