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

{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.
Ideally we would want to show that for $r=d-1$ we have $\sum_k |S_k|\le d(n-1)+1$.