The polynomial Hirsch conjecture

From Polymath Wiki
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,\ldots,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.

Threads


Here is a list of Wordpress posts on the Hirsch conjecture

Possible strategies

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{ supp(F_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].

Proof Consider t families [math]\displaystyle{ F_1,\ldots,F_t \subset \{1,\ldots,n\} }[/math] obeying (*). Consider the largest s so that the union of all sets in [math]\displaystyle{ F_1 \cup \ldots \cup F_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 union [math]\displaystyle{ \bigcup (F_{n-r+1} \cup \ldots \cup F_n) }[/math] of all sets in [math]\displaystyle{ F_{n-r+1} \cup \ldots \cup F_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{ \bigcup(F_1 \cup \ldots \cup F_{s+1}) }[/math] and [math]\displaystyle{ \bigcup(F_{n-r} \cup \ldots \cup F_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] families [math]\displaystyle{ F_{s+1},\ldots,F_{n-r} }[/math] must thus contain a set with this element m. If we then throw away all the sets that don't contain m, and then delete m, we obtain t-r-s non-empty families of an n-1-element set that obey (*), 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 [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

  • 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]\displaystyle{ \emptyset }[/math] as 0, etc.

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

More generally, the example

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

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

Claim: f(4)=8.

Proof: to be filled in...


f(d,n)

Let f(d,n) be the largest number of families obeying (*) in which all families consist only of d-element sets. We claim that [math]\displaystyle{ f(d,n) \leq 2^{d-1} n }[/math] for d=1,2,3,...

We prove this by induction on d. The case d=1 is trivial, so now suppose d>1. We consider the supports U_1, U_2, ..., U_t of F_1, ..., F_t. Set a_1 = 1, set a_2 to be the first label for which U_{a_2} is disjoint from U_{a_1}, let a_3 be the first label for which U_{a_3} is disjoint from U_{a_2}, and so forth until one reaches a_m = t+1 (by convention we set U_{t+1} 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 S_i and S_j are disjoint for |j-i| > 2. In particular, [math]\displaystyle{ \sum_i |S_i| \leq 2n }[/math]. On the other hand, by induction, we have [math]\displaystyle{ a_{i+1}-a_i \leq 2^{d-2} |S_i| }[/math] for each i. Summing in i we obtain the claim.

To obtain the lower bound [math]\displaystyle{ f(2,n) \gg n \log n }[/math], we use the following recursive construction (for even n): place f(2,n/2) families in {1,...,n/2}, then n/2 perfect matchings between {1,...,n/2} and {n/2+1,...,n}, and then f(2,n/2) families in {n/2+1,...,n}, giving the recursion

[math]\displaystyle{ f(2,n) \geq 2 f(2,n/2) + n/2 }[/math]

which gives the n log n behaviour.

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 [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]\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 and terminology

(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

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