Looking for construction related to Erdos-Szekeres theorem - MathOverflow

Looking for construction related to Erdos-Szekeres theorem

2012-11-01T20:24:48Z

The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is $p(i_1) < p(i_2) < \cdots < p(i_m)$ for $i_1 < i_2 < \cdots < i_m$, and a decreasing run is defined similarly. Call $i_m-i_1+1$ the"width" of the run. It is easy to construct examples showing that the theorem is tight. For example, for $n=16$, $4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13.$ Here no run has length more than $4$. However, in this construction there are runs of very small width. I'm looking for a construction for general $n$ in which: (a) there are no increasing or decreasing runs of length larger than $O(\sqrt n)$; and (b) every run of length $\Omega(\sqrt n)$ has large width (as large as possible).

Answer by domotorp for Looking for construction related to Erdos-Szekeres theorem

2012-11-01T21:04:16Z

These runs are strongly related to Young tableaux. So it is the best to first make a tableau that has the corresponding property. This we can construct by induction: Start with 1, then make a copy of it +1 and put it below, then copy it +2 and put it right from it. So you should get: $\begin{array}{cc} 1&3\cr 2&4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&3&9&11\cr 2&4&10&12\cr 5&7&13&15\cr 6&8&14&16\cr \end{array}$ and so on.

To make a sequence of this, first take the last row of the tableau, then the last but one and so on, so you should get $6, 8, 14, 16, 5, 7, 13, 15, 2, 4, 10, 12, 1, 3, 9, 11$. Now, without giving a formal proof, any long enough run must skip over two correspondingly big "breaks" in the matrix which will make it have a large width. Unless I am mistaken, a run of length $c\sqrt n$ should have width $\Omega(c n)$.

Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.

Answer by Aaron Meyerowitz for Looking for construction related to Erdos-Szekeres theorem

2012-11-02T05:00:38Z

The strongest result is that a sequence of $(m-1)^2+1$ distinct values has a monotonic subsequence of length $m$ (proof below). So this is the best possible width. If we want a sequence of length $m^2$, which is as far as we can go without forcing a monotonic sequence of length $m+1$, We can acheive this width by allowing longer monotonic subsequences anyway. For $m=4$ we can use $3,2,1,6,5,4,9,8,7,12,11,10,15,14,13,16$ This enforces the maximum possible width of $10$ at the expense of having an increasing sequence of length $6$. The general construction is clear.

So perhaps the question is this:

Consider a sequence of length $m^2$ with no monotonic subsequences of length $m+1.$ We know that any subsequence of $m^2-2m+2$ has a monotonic subsequence of length $m.$ What bounds can we give on the width of these length $m$ subsequences?

An upper bound is $\frac{m^2}{2}$ but I am not sure how close we can come. Here is a start:

It is better to think of a sequence of distinct rationals $x_1,x_2,\cdots,x_n$ which can be normalized to a permutation of the first $n$ integers later. The result is that a sequence of length $n=(s-1)(t-1)+1$ has an increasing subsequence of length $s$ or a decreasing subsequence of length $t$. Following the proof leads to ideas for a construction. Given a sequence, define the profile of a member $x$ to be $[d,u]$ where $d=d(x)$ is the length of the longest decreasing subsequence ending with $x$ and $u=u(x)$ the longest increasing. I claim that no two members have the same profile and hence there can be at most $(s-1)(t-1)$ members with both $d(x) \lt s$ and $u(x) \lt t. $ The claim follows from the observation that for $i \lt j$, $x_i \lt x_j$ implies $d(x_i) \gt d(x_j)$ while $x_i \gt x_j$ implies $u(x_i) \gt u(x_j).$

A sequence of profiles is possible if profiles $[d-1,u]$ and $[u-1,d]$ occur before $[u,d]$ (When $d=1$ and/or $u=1$, skip the appropriate restriction). So we should start with a possible sequence of profiles which looks promising and then work our way through to a rational sequence with those profiles. When we have assigned $x_1,x_2,\cdots,x_{i-1}$ then we have a list of lower bounds for $x_i$ (those already chosen with $d(x) \ge d(x_i)$) and another list of upper bounds. We then pick $x_i$ between the least upper bound and the greatest lower bound (avoiding any value already chose). All this does not completely determine the permutation

With the revised question above, we know that the profiles are all $[d,u]$ with $1 \le d,u,\le m.$ We certainly start with profile $[1,1]$ and end with $[m,m].$ Identifying a value in the sequence by its profile we know that $[1,1],[1,2],\cdots,[1,m]$ is increasing and $[1,m],[2,m],\cdots,[m,m]$ is decreasing. So one of those is no longer than $\frac{m^2}{2}.$ Approaching this will require putting $[1,m]$ and $[m,1]$ near the middle. In general, each sequence $[d,j]$ for $1 \le j \le m$ is monotonic as is each sequence $[j,u].$ so we need the ends far apart.