Polynomial Hirsch Conjecture

There is a very interesting Polymath project going on right now: Polymath3. It is about the polynomial Hirsch conjecture.

As I feel like contributing, I am going to temporarily post my ideas as comments of this post before copying them over to the main blog (in order not to pollute the blog with half-baked ideas).

This entry was posted in Uncategorized. Bookmark the permalink.

11 Responses to Polynomial Hirsch Conjecture

  1. I have looked at the proof of the upper bound for f^*(d,n) (ie Lemma 1 and Corollary 1 of Polymath3) and I had the following idea which does not quite work but may inspire others:

    As usual, we start with a sequence of d-uniform multiset families F_1,\ldots,F_t.
    Let’s partition the sequence F_1,\ldots,F_t into intervals in the following way:
    We first pick a random element say x_1 of the support of F_1 and denote by I_1 the interval [1,i_1] where i_1 is the last index of an F_i containing x_1.
    Then we pick a new element x_2 in the support of F_{i_1+1} and denote by I_2 the interval [i_1+1,i_2] where i_2 is the last index of an F_i containing x_2. And so on until the end.
    By definition, after i_k, x_k cannot appear anymore since when one element is removed from the support it cannot be added again.
    This means that our sequence of intervals I_k can contain at most n elements.
    Also, if we restrict the F_i for i \in I_k by excluding x_k, we get a convex sequence of d-1-uniform multiset families.
    So we have as in the original proof f^*(d,n)\le \sum_{k} f^*(d-1,|S_k|).

    Now assume that we would be able to prove that \sum_{k} |S_k| \le 2n-1, then together with the fact that we have at most n intervals, and using the induction hypothesis of f^*(d-1,n)\le (d-1)(n-1)+1, then we would obtain
    f^*(d,n)\le (d-1)(\sum_k|S_k| - n) + n \le (d-1)(2n-1-n)+n = d(n-1)+1.

    So this would give exactly the right bound, but there are two things that do not exactly work:

    1. The first one is that this is valid only if we have exactly n intervals.
    2. The second one is that we need to prove that \sum_k |S_k|\le 2n-1 which is not as easy as in the original proof since we don’t have disjointness for non-consecutive intervals.

    But the interesting point that this illustrates is that if one can decompose the sequence into exactly n intervals with the property that each interval contains at least one common element and that \sum_k |S_k|\le 2n-1, then we can prove the bound f^*(d,n)\le d(n-1)+1. How realistic is such a construction?

  2. Another way to formulate the above is the following: if we can always decompose the sequence [1,t] into intervals such that \sum_k (|S_k|-1)\le n-1 and k\le n then we can prove Nikolai’s conjecture (I am using here the notation of Corollary 1 of Polymath3). Note that since the intervals satisfy the condition that the F_i in intervals I_k don’t contain the common element in I_\ell for any \ell < k, then k has to be smaller than n. So only the sum condition needs to be verified.

    It seems that this is the case (on some simple examples I looked at), provided one can construct the sequence without being forced to start at one end. So in other words, we need to find a decomposition which minimizes \sum_k (|S_k|-1), and on some examples this seems to be possible and yield the desired properties.

    • Thinking a bit more about this led me to this example:
      {11111, 11112, 11123, 11234, 12345, 23455, 34555, 45555, 55555}
      In this case, if you consider all the subsequences whose support contain one particular element, summing up Nikolai’s bound for them (ie if you consider that there length is bounded by f^*(d-1,k) for some appropriate k) gives a total length that is always larger than f^*(5,5), no matter how the sequence is decomposed. So this decomposition approach does not seem to allow to prove Nikolai’s conjecture but only a weaker upper bound.

  3. Gil Kalai says:

    Thanks for participating, Olivier

  4. Here is a different approach to the problem.
    I am considering the following equivalent formulation: given a down-set D\subset 2^{[n]} (which is nothing but the union of the F_i since one can always add subsets of the existing elements of F_i to complete it into a down-set), the convexity and disjointness condition corresponds to the existence of a labeling function \ell: D\to \mathbb{N} which is such that for any S\in D, \ell maps the set \{T \in D: S\subset T\} to an interval.
    In this formulation, the question is how large can the interval \ell(D) be?
    Let’s call this the diameter of D, denoted by d(D) and defined as \max_{\ell} \max_{S,T\in D} \ell(S) - \ell(T)+1.

    It seems that the maximal elements of D play a crucial role in controlling this diameter. Let’s call M(D) the set of maximal elements of D. A simple case is when M(D) is a singleton, say M(D)=\{S_0\}. Indeed in this case, one can easily prove that d(D)\le 2|S_0| (this corresponds to the case where one of the F_i contain [n] which gives t\le 2n in the standard formulation).

    Similarly, it seems that when M(D)=\{S_1, S_2\} one can prove M(D)\le |S_1|+|S_2|+|S_1\Delta S_2|.
    However, the situation becomes quickly tricky when one considers three elements.

    • One can further generalize this approach in the following way:
      The down-set we start with can be replaced by any arbitrary directed graph, and the goal is then to find a map \ell from this directed graph G_1 to some undirected graph G_2 with the following properties: if we consider the set R(x) of elements of G_1 that are reachable from x, then we want the induced subgraph G_2(\ell(R(x))) to be connected, and we want G_2 to be of maximum diameter.

  5. In the above formulation (diameter of down-sets), I am wondering whether there is always a way to order the elements of 2^{[n]} in a sequence S_1,\ldots, S_{2^n} such that each \{S_1,\ldots S_i\} forms a down-set, and such that the diameters of these sets are monotonously increasing from 1 up to f(n) and then monotonously decreasing to 2n.

    For example for n=2, this sequence does it: \emptyset, 1, 2, 12 (with diameters 1, 2, 3, 4). For n=3, this sequence \emptyset, 1, 2, 3, 12, 23, 13, 123 has diameters 1,  2, 3, 4, 5, 6, 6, 6.
    The case n=5 is where things are likely becoming interesting since we know that f(5)>10.

    • Following up on this idea, if one considers a down-set and looks at the effect on its diameter to add or remove one element (assuming this is done so that the resulting set is still a down-set), we can observe the following: when adding an element of size k, it connects to k elements of size k-1. If those elements of size k-1 were all maximal, this means we introduced the constraint that they all have to be at distance one of the new element which means we cannot increase the diameter (although we also allow them to space out a bit if they were within distance 1 of each other).

    • A related notion that is potentially interesting to study is the following: given a down-set D\subset 2^{[n]}, one can define the k-diameter of this down-set as the diameter restricted to its k sets:
      d(D,k)=\max_\ell \max_{S,T\in D,\, |S|=|T|=k} \ell(S)-\ell(T)+1.

      With this definition, we obviously have d(D,n)=1 and we can prove easily that d(D,n-1)\le 3 and it seems that d(D,n-2)\le 5 although I don’t have a proof for it yet.

      It would be interesting to study the function g(n,k) defined as the maximum k-diameter for down-sets over n elements.

  6. Regarding the proof of f^*(d,n)\le 2^{d-1}(n-1)+1, here are a few observations:

    1. For d=2, this gives a tight bound, which means that the decomposition with respect to 1-shadows is optimal for this value of d.
    2. One interesting aspect of the decomposition is that the supports of the segments, ie the sets S_k are in number at most n and satisfy \sum_k |S_k|\le 2n-1 which is effectively f^*(2,n).

    Can these be generalized somehow?
    In particular, can one decompose a convex sequence of 3-uniform multisets with respect to its 2-shadows?

    • The starting point of a r-shadow generalization of Corollary 1 of the wiki is to replace supports by r-shadows in Lemma 1.

      Note that if we consider, for each of the r-shadows, the indices at which they appear and then disappear in the sequence (they span intervals so this is well defined), and order them by the interval order (first by when they appear and then by when they disappear), then this forms a convex sequence of r-uniform singleton multiset families, whose length is thus bounded by f^*(r,n), which means that the number of intervals m in the partition is at most f^*(r,n).

      Then, if we use this generalized Lemma as in the proof of Corollary 1, we have to bound the sum of the supports \sum_k |S_k|. If we sum the number of r-shadows instead of the sum of the number of 1-shadows, because of the generalized Lemma 1, we know that this is upper bounded by 2f^*(r,n)-1, but the number of r-shadows is larger than the number of 1-shadows for r<n.
      Ideally we would want to show that for r=d-1 we have \sum_k |S_k|\le d(n-1)+1.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s