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

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.

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] (1)

Iterating this gives [math]\displaystyle{ f(n) \leq O(n^{\log_2 n}) }[/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?

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=3678"