The polynomial Hirsch conjecture

From Polymath Wiki
Revision as of 21:45, 30 September 2010 by Teorth (talk | contribs) (→‎f(n) for small n: added the AHRR argument deducing the polynomial Hirsch conjecture from the combinatorial one)
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]

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 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?

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.

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