Difference between revisions of "The polynomial Hirsch conjecture"
(→Threads) |
|||
Line 127: | Line 127: | ||
'''Claim''': f(4)=8. | '''Claim''': f(4)=8. | ||
− | '''Proof''': to be | + | '''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 15:56, 3 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.
Contents
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]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.
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.
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].
- 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”