Difference between revisions of "The polynomial Hirsch conjecture"

From Polymath1Wiki
Jump to: navigation, search
Line 125: Line 125:
 
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>|A \cap B| \geq 2</math>, then <math>|i-j| \leq 2</math>, because there can be at most three families that contain <math>A \cap B</math> if the full set 1234 is excluded.
 
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>|A \cap B| \geq 2</math>, then <math>|i-j| \leq 2</math>, because there can be at most three families that contain <math>A \cap B</math> if the full set 1234 is excluded.
  
'''Claim''': f(4)=8.
 
  
'''Proof''': Assume we have 9 or more elements then there are 8 types of
 
sets in terms of which of the the first three elements are
 
in the set. We must have a repetition of the same type in
 
sets in two different families A and B.
 
Then every set must contain an element
 
that contains the 3 elements of the repetition.
 
Now if the repetition is not null there can be
 
at most 8 elements that contain the repetition
 
but we have 2 in A and B
 
but we have 7 families besides A and B which each must contain one
 
and so there is a contradiction.
 
 
Now we can repeat this argument for each set of
 
four elements. so we have at most 5 families containing the
 
null set and each single element.
 
 
And we have adding
 
one element not in a set in a family to that set and having the resulting
 
augmented set in another family is forbidden.
 
 
so we have at most 5 families containing the
 
null set and each single element. And we have adding
 
one element not in a set in a family and having the resulting
 
augmented set outside the family is forbidden.
 
so outside of the 5 sets that contain
 
the singleton elements and the null set there are no
 
two element sets, no single element sets and no null set. but if there are eleven sets that leaves 5 sets for 6
 
families which gives a contradiction. So f(4) cannot be 11.
 
 
If there are 10 families there then by the above there are 5 families
 
which have only sets of three and four elements. This means that each of these
 
families must contain one of the
 
sets with more than two elements. In particular one must
 
contain the set with four elements and one a set with three
 
elements. Then since their intersection will have three elements
 
every family must have a set with three elements but there are not
 
enough sets with three elements to go around.
 
sets which gives a contradiction. So f(4) cannot be 10.
 
 
If there are 9 families there then by the above there are 4 families
 
which have only sets of three and four elements. We divide the proof into
 
two cases In the first case one family must
 
contain the set with four elements and one a set with three
 
elements. Then since their intersection will have three elements
 
every family must have a set with three elements but there are not
 
enough sets with three elements to go around.
 
sets which gives a contradiction. The second case
 
is when the four element set is not in one of these four families. Then These
 
sets must consist of four families each containing one of the three element sets.
 
But then the families containing 123 and 124 will contain sets whose intersection
 
is 12 but the family containing 134 will not contain a set which contains the
 
elements 1 and 2 so in this case we have a contradiction. So in both cases we
 
have a contradiction and So f(4) cannot be 9. However since f(4) must
 
be 8,9,10 or 11 from the above in fact it must be 8.
 
  
  

Revision as of 11:20, 5 October 2010

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]F_1,\ldots,F_t[/math] of [math]\{1,\ldots,n\}[/math] that are disjoint (i.e. no set S can belong to two of the families [math]F_i, F_j[/math]). Suppose that
For every [math]i \lt j \lt k[/math], and every [math]S \in F_i[/math] and [math]T \in F_k[/math], there exists [math]R \in F_j[/math] such that [math]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


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]X[/math] is a sequence [math]F_1,\ldots,F_t[/math] of non-empty families of subsets of [math]X[/math] which are disjoint ([math]F_i \cap F_j = \emptyset[/math] for all [math]i\ltj[/math]) and obey the convexity condition (*). We call [math]t[/math] the length of the convex family. Thus, [math]f(n)[/math] is the largest length of a convex sequence of families on [math][n][/math].

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

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

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

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

[math]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]U_i^{(r)} \cap U_k^{(r)} \subset U_j^{(r)}[/math] whenever [math]i \lt j \lt k[/math].

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

[math]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]U^{(r)}_i[/math] and [math]U^{(r)}_k[/math] (and hence all intermediate r-shadows [math]U^{(r)}_j[/math] for [math]i \lt j \lt k[/math]) contain a common element [math]B \in \binom{X}{r}[/math]), then the restriction

[math]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]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]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]n \gt 1[/math], [math]f(n) \leq f(n-1) + 2 f(\lfloor n/2\rfloor)[/math].

Proof Consider t families [math]F_1,\ldots,F_t \subset \{1,\ldots,n\}[/math] obeying (*). Consider the largest s so that the cumulative support [math]U_{[1,s]} := U_1 \cup \ldots \cup U_s[/math] is at most n/2. Clearly, [math]0 \leq s \leq f(\lfloor n/2\rfloor)[/math]. Consider the largest r so that the cumulative support [math]U_{[n-r+1,n]} := U_{n-r+1} \cup \ldots \cup U_n[/math] is at most n/2. Clearly, [math]0 \leq r \leq f(\lfloor n/2\rfloor)[/math].

If [math]t \leq s+r[/math] then we are done, so suppose that [math]t \gt s+r[/math]. By construction, the sets [math]U_{[1,s+1]}[/math] and [math]U_{[n-r,n]}[/math] both have cardinality more than [math]n/2[/math] and thus have a common element, say m. By (*), each of the [math]t-r-s[/math] supports [math]U_{s+1},\ldots,U_{n-r}[/math] must thus contain this element m. The restriction of [math]F_{s+1},\ldots,F_{n-r}[/math] is then a convex family on [math][n]\backslash \{m\}[/math], hence [math]t-r-s \leq f(n-1)[/math], and the claim follows. QED

Note: the same argument gives [math]f(n) \leq f(n-1) + f(a) + f(b)[/math] for any positive integers a, b with [math]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]

In fact we can boost this a bit to

[math]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]f(n) \leq n^{\log_2 n+1}[/math] for [math]n \geq 2[/math] (in fact I think we can sharpen this a bit to [math]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]\emptyset[/math] as 0, etc.

We trivially have [math]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]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]F_1, F_2, ..., F_{i-1}[/math], and similarly for [math]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]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]|A \cap B| \geq 2[/math], then [math]|i-j| \leq 2[/math], because there can be at most three families that contain [math]A \cap B[/math] if the full set 1234 is excluded.



f(d,n)

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

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

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

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

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

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

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

[math]F_i := \{ \{a_1,\ldots,a_d\}: a_1+\ldots+a_d = i+d-1\}[/math] for [math]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] f(2,n) \leq 100 n \log n [/math] in the d=2 case. Suppose for contradiction that we have [math]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]|U_i| \leq n / (5 \log n)[/math] for at least one i between [math]45 n/\log n[/math] and [math]55 n/\log n[/math], because otherwise each F_i would need to have at least [math]\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]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] 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]S_v[/math] of facets containing . Starting with a vertex w, we can consider [math]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]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].

Bibliography

(Expand this biblio!)

Other links