The polynomial Hirsch conjecture
From Polymath1Wiki
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 of that are disjoint (i.e. no set S can belong to two of the families F_{i},F_{j}). Suppose that
- For every i < j < k, and every and , there exists such that . (*)
- 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 F_{i} 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.
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) 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 X is a sequence of non-empty families of subsets of X which are disjoint ( for all i < j) and obey the convexity condition (*). We call t the length of the convex family. Thus, f(n) is the largest length of a convex sequence of families on [n].
The support or 1-shadow of a family F_{i} of subsets of X is defined as
- .
If is a convex sequence of families, then the supports obey the convexity condition for all i < j < k.
More generally, given any , define the r-shadow as
- .
Then the r-shadows are also convex: whenever i < j < k.
Suppose an interval of families contains a common element in the supports . (By convexity, this occurs whenever m belongs to both U_{i} and U_{k}.) Then one can define the restriction of these families by m by the formula
one can verify that this is also a convex family. More generally, if the r-shadows and (and hence all intermediate r-shadows for i < j < k) contain a common element ), then the restriction
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 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 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 n > 1, . ([EHRR], adapting a proof from [KK])
Proof Consider t families obeying (*). Consider the largest s so that the cumulative support is at most n/2. Clearly, . Consider the largest r so that the cumulative support is at most n/2. Clearly, .
If then we are done, so suppose that t > s + r. By construction, the sets U_{[1,s + 1]} and U_{[n − r,n]} both have cardinality more than n / 2 and thus have a common element, say m. By (*), each of the t − r − s supports must thus contain this element m. The restriction of is then a convex family on , hence , and the claim follows. QED
Note: the same argument gives for any positive integers a, b with . In particular we have the slight refinement
In fact we can boost this a bit to
- (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 for (in fact I think we can sharpen this a bit to ).
f(n) for small n
We trivially have . 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, as 0, etc.
On the other hand, for every n we have , 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 , f(n) = 2n.
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 , 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 is not used and two subsets A, B of cardinality n-1 appear in families F_i, F_j then , 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 f(5)
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 f(d,n) denote the maximum possible length of a convex $d$-uniform sequence of families of subsets of [n]. Let f^{ * }(d,n) denote the maximum possible length of a convex $d$-uniform sequence of families of multi-subsets of [n].
That f^{ * }(d,n) is at least equal to the conjectured d(n − 1) + 1 is shown by two examples:
- for .
- , , ...
As for upper bounds, to show that and , we use the following lemma:
- Lemma 1: Let be a convex and d-uniform sequence of families of multisets in the alphabet [n]. Then, there is a partition of into disjoint intervals , , ..., with the following properties:
- 1) For every k, is not empty.
- 2) Each is in the support of at most two of the I_{k}'s.
- 3) If then a is not in the support of any I_{k} other than I_{1}.
In parts (2) and (3) we call support of I_{k} the union .
Proof
We consider the supports
of .
Set t_{0} = 0; let t_{1} be the last label for which is not disjoint from , let t_{2} be the last label for which is not disjoint from , and so forth until one reaches t_{m} = t (by convention we set U_{t + 1} to be empty).
From (*) we have the convexity condition for i < j < k, which implies that if we set , then the S_{i} and S_{j} are disjoint for (condition 2). By construction and convexity, all the supports have a common element (condition 1). Condition 3 holds by choice of t_{1}. QED
- Corollary 1: .
Proof: For d = 1 this is obvious, for d > 1 we use induction on d.
Consider the partition in the lemma above. Let S_{k} be the support of I_{k}, that is, the union of the supports of the F_{i}'s with . Let a_{k} be an element that is active in the whole of I_{k}. Restricting to the multisets that contain a_{k} (and then deleting one copy of a_{k} from each) gives a convex (d − 1)-uniform sequence of families of multisets of length | I_{k} | on | S_{k} | elements, so:
- .
Now, conditions (2) and (3) in the lemma imply that , (with equality only possible if the support of F_{1} is a single element, that is if ). Hence:
- ,
so to finish the proof we only need to show that , or, equivalently, that . This holds trivially. QED
Observe that in the last step equality can only be obtained only if d = 2, in which case we indeed know that the bound is tight. (The factor m − 1 is always positive since m = 1 implies there is an element in the support of every F_{i} and we could then conclude .
- Corollary 2: .
Proof: basically the same except now the length of each I_{k} is bounded by f(d − 1, | S_{k} | − 1) (the deleted element a_{k} can no longer appear in the (d − 1)-uniform subsequences).
- .
Now the support of F_{1} has at least d elements, so we have , (with equality again only possible if the support of F_{1} is a single element). Hence:
- .
So to finish the proof we only need to show that , or, equivalently, that . QED
Here is a proof of a weaker upper bound in the d=2 case. Suppose for contradiction that we have t = 100nlogn + O(1) families. Consider the supports U_i of the i^th family F_i. We claim that for at least one i between 45n / logn and 55n / logn, because otherwise each F_i would need to have at least 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 . 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
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 S_{v} of facets containing . Starting with a vertex w, we can consider F_{i} 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 . 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”