The polynomial Hirsch conjecture

From Polymath Wiki
Revision as of 11:36, 14 October 2010 by Pacosantos (talk | contribs)
Jump to navigationJump to search

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


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.

For small n>=1 (at least up to f(4)) the formula f(n)=2n holds. 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.



f(d,n)

Let [math]\displaystyle{ f(d,n) }[/math] be the largest number of families obeying (*) in which all families consist only of [math]\displaystyle{ d }[/math]-element sets. Thus, for instance, [math]\displaystyle{ f(0,n)=1 }[/math] and [math]\displaystyle{ f(1,n)=n }[/math].

Theorem [math]\displaystyle{ f(d,n) \leq 2^{d-1} n }[/math] for [math]\displaystyle{ d=1,2,3,\ldots }[/math]. ([EHRR], adapting a proof from [L])

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

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

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

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

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

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

[math]\displaystyle{ F_i := \{ \{a_1,\ldots,a_d\}: a_1+\ldots+a_d = i+d-1\} }[/math] for [math]\displaystyle{ i=1,\ldots,dn-d+1 }[/math].
Question: Can one eradicate the multisets and get a true example of comparable size, say for d=3?


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

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

which gives a contradiction.

The combinatorial conjecture implies the polynomial Hirsch conjecture

The following result is from [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].

Bibliography

(Expand this biblio!)

  • [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.

Other links

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=The_polynomial_Hirsch_conjecture&oldid=3711"