The polynomial Hirsch conjecture

From Polymath Wiki
Revision as of 12:07, 22 October 2010 by KristalCantwell (talk | contribs) (addition of material)
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.

I think we have the values of f(1),f(2),f(3) and f(4). Now I am looking at f(5) we have it is greater than or equal to 10 and less than or equal to f(4) + f(2) + f(2) -1 = 8+4+4-1=15.

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}] So f(5) is between 11 and 15.

Lemma: Suppose that a convex sequence of families of sets on [n] has an F_i containing [n-1] as one of its sets. Then, for every S\in F_j in the sequence we have |i-j| \le n-|S|+1.

Proof: Suppose wlog that j < i. Convexity implies that F_{j+1} has a set S' containing S\cap [n-1]= S\setminus n. Such an S' can only be obtained by either removing n from S or adding one (or more) elements of [n-1] to S, or both. Repeating this we get a sequence of sets each contained in one of the families F_j, F_{j+1}, …, F_i which is increasing except at some point a decreasing step (removing n) is allowed. But convexity also implies that the “removing step can be taken only once in this sequence. QED

Corollary: The length of such a sequence is at most 2n+2.

Proof: By the Lemma, for every F_j containing a non-empty set we have |i-j|\le n. Thus, all those F_j‘s are within an interval of length 2n+1 centered at i. Counting for the empty set gives 2n+2. QED

So for the cases 13 to 15 for f(5) we need only look at triples since they are greater then 2n+2 for n=5.


I think I can show the following: if an (n-1)-tuple arises in a convex sequence of subsets of [n], then the sequence must have length at most 2n. (I mean this for every n, not only n=5). I have to leave now but will post the argument this afternoon. This means that to find f(5) we should concentrate on sequences using sets of at most three elements.

From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.

0

    • 5
      • 5
    • 5
  • 5

The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it



f(d,n)

Let [math]\displaystyle{ f(d,n) }[/math] denote the maximum possible length of a convex $d$-uniform sequence of families of subsets of [math]\displaystyle{ [n] }[/math]. Let [math]\displaystyle{ f^*(d,n) }[/math] denote the maximum possible length of a convex $d$-uniform sequence of families of multi-subsets of [math]\displaystyle{ [n] }[/math].

That [math]\displaystyle{ f^*(d,n) }[/math] is at least equal to the conjectured [math]\displaystyle{ d(n-1)+1 }[/math] is shown by two examples:

[math]\displaystyle{ F_i := \{ \{a_1,a_2,\dots,a_d\}: \sum a_i = i+d-1\} }[/math] for [math]\displaystyle{ i=1,\ldots,d(n-1)+1 }[/math].
[math]\displaystyle{ F_1 := \{11\dots11\}, F_2 := \{11\dots12\}, \dots F_d := \{12\dots22\}, :\lt math\gt F_{d+1} := \{22\dots22\}, F_{d+2} := \{22\dots23\}, \dots F_{2d} := \{23\dots33\}, : \dots :\lt math\gt F_{(n-2)d+1} := \{n-1,n-1,\dots,n-1,n-1\}, \dots, F_{(n-1)d} := \{n-1,n,\dots,n,n\}, F_{(n-1)d+1} := \{n,n,\dots,n,n\}. : Question: Can one eradicate the multisets and get a true example of comparable size, say for d=3? The answer seems to be ''yes'': \lt math\gt f(2,n)\ge 2n-O(\log n) }[/math], [math]\displaystyle{ f(d,n)\ge dn-O(d \log n) }[/math], ...

As for upper bounds, to show that [math]\displaystyle{ f^*(d,n) \le 2^{d-1}(n-1) + 1 }[/math] and [math]\displaystyle{ f(d,n) \le 2^{d-1}(n-d) + 1 }[/math], we use the following lemma:

Lemma 1: Let [math]\displaystyle{ \{F_i\}_{i=1}^t }[/math] be a convex and [math]\displaystyle{ d }[/math]-uniform sequence of families of multisets in the alphabet [math]\displaystyle{ [n] }[/math]. Then, there is a partition of [math]\displaystyle{ \{1,\dots,t\} }[/math] into disjoint intervals [math]\displaystyle{ I_1=\{1,\dots,t_1\} }[/math], [math]\displaystyle{ I_2=\{t_1+1,\dots,t_2\} }[/math], ..., [math]\displaystyle{ I_m=\{t_{m-1}+1,\dots,t\} }[/math] with the following properties:
1) For every [math]\displaystyle{ k }[/math], [math]\displaystyle{ \cap_{i\in I_k} support(F_i) }[/math] is not empty.
2) Each [math]\displaystyle{ a\in [n] }[/math] is in the support of at most two of the [math]\displaystyle{ I_k }[/math]'s.
3) If [math]\displaystyle{ a\in support(F_1) }[/math] then [math]\displaystyle{ a }[/math] is not in the support of any [math]\displaystyle{ I_k }[/math] other than [math]\displaystyle{ I_1 }[/math].

In parts (2) and (3) we call support of [math]\displaystyle{ I_k }[/math] the union [math]\displaystyle{ \cup_{i\in I_k} support(F_i) }[/math].


Proof We consider the supports [math]\displaystyle{ U_1, U_2, \dots, U_t }[/math] of [math]\displaystyle{ F_1, \ldots, F_t }[/math]. Set [math]\displaystyle{ t_0=0 }[/math]; let [math]\displaystyle{ t_1 }[/math] be the last label for which [math]\displaystyle{ U_{t_1} }[/math] is not disjoint from [math]\displaystyle{ U_{t_0+1}=U_1 }[/math], let [math]\displaystyle{ t_2 }[/math] be the last label for which [math]\displaystyle{ U_{t_2} }[/math] is not disjoint from [math]\displaystyle{ U_{t_1+1} }[/math], and so forth until one reaches [math]\displaystyle{ t_m = t }[/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_{t_{i-1}+1} \cup \ldots \cup U_{t_{i}} }[/math], then the [math]\displaystyle{ S_i }[/math] and [math]\displaystyle{ S_j }[/math] are disjoint for [math]\displaystyle{ |j-i| \geq 2 }[/math] (condition 2). By construction and convexity, all the supports [math]\displaystyle{ U_{t_{i-1}+1},\ldots,U_{t_{i}} }[/math] have a common element (condition 1). Condition 3 holds by choice of [math]\displaystyle{ t_1 }[/math]. QED

Corollary 1: [math]\displaystyle{ f^*(d,n)\le 2^{d-1} (n-1) + 1 }[/math].

Proof: For [math]\displaystyle{ d=1 }[/math] this is obvious, for [math]\displaystyle{ d\gt 1 }[/math] we use induction on [math]\displaystyle{ d }[/math].

Consider the partition in the lemma above. Let [math]\displaystyle{ S_k }[/math] be the support of [math]\displaystyle{ I_k }[/math], that is, the union of the supports of the [math]\displaystyle{ F_i }[/math]'s with [math]\displaystyle{ i\in I_k }[/math]. Let [math]\displaystyle{ a_k }[/math] be an element that is active in the whole of [math]\displaystyle{ I_k }[/math]. Restricting [math]\displaystyle{ \{F_i\}_{i\in I_k} }[/math] to the multisets that contain [math]\displaystyle{ a_k }[/math] (and then deleting one copy of [math]\displaystyle{ a_k }[/math] from each) gives a convex [math]\displaystyle{ (d-1) }[/math]-uniform sequence of families of multisets of length [math]\displaystyle{ | I_k | }[/math] on [math]\displaystyle{ |S_k| }[/math] elements, so:

[math]\displaystyle{ t= \sum_{i=1}^m |I_k| \le \sum_{i=1}^m f^*(d-1, |S_k|) \le 2^{d-2} (\sum_{i=1}^m|S_k| -m) +m }[/math].

Now, conditions (2) and (3) in the lemma imply that [math]\displaystyle{ \sum|S_k| \le 2n -1 }[/math], (with equality only possible if the support of [math]\displaystyle{ F_1 }[/math] is a single element, that is if [math]\displaystyle{ F_1=\{aaa\dots aa\} }[/math]). Hence:

[math]\displaystyle{ 2^{d-2} (\sum|S_k| -m) +m \le 2^{d-1}(n-1) -(m-1)2^{d-2} +m }[/math],

so to finish the proof we only need to show that [math]\displaystyle{ 1\ge m-(m-1)2^{d-2} }[/math], or, equivalently, that [math]\displaystyle{ (m-1)(2^{d-2} -1) \ge 0 }[/math]. This holds trivially. QED

Observe that in the last step equality can only be obtained only if [math]\displaystyle{ d=2 }[/math], in which case we indeed know that the bound is tight. (The factor [math]\displaystyle{ m-1 }[/math] is always positive since [math]\displaystyle{ m=1 }[/math] implies there is an element in the support of every [math]\displaystyle{ F_i }[/math] and we could then conclude [math]\displaystyle{ t\le f^*(d-1,n) }[/math].


Corollary 2: [math]\displaystyle{ f(d,n)\le 2^{d-1} (n-d) + 1 }[/math].

Proof: basically the same except now the length of each [math]\displaystyle{ I_k }[/math] is bounded by [math]\displaystyle{ f(d-1,|S_k|-1) }[/math] (the deleted element [math]\displaystyle{ a_k }[/math] can no longer appear in the [math]\displaystyle{ (d-1) }[/math]-uniform subsequences).

[math]\displaystyle{ t= \sum_{i=1}^m |I_k| \le \sum_{i=1}^m f(d-1, |S_k|-1) \le 2^{d-2} (\sum_{i=1}^m|S_k| -md) +m }[/math].

Now the support of [math]\displaystyle{ F_1 }[/math] has at least [math]\displaystyle{ d }[/math] elements, so we have [math]\displaystyle{ \sum|S_k| \le 2n -d }[/math], (with equality again only possible if the support of [math]\displaystyle{ F_1 }[/math] is a single element). Hence:

[math]\displaystyle{ 2^{d-2} (\sum|S_k| -md) +m \le 2^{d-2}(2n -d-md) +m = 2^{d-1}(n-d) - 2^{d-2}(m-1)d + m }[/math].

So to finish the proof we only need to show that [math]\displaystyle{ 1\ge m-d(m-1)2^{d-2} }[/math], or, equivalently, that [math]\displaystyle{ (m-1)(d2^{d-2} -1) \ge 0 }[/math]. QED


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