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).
2 Answers
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.
-
$\begingroup$ If you take the last row of your tableau as the beginning of your sequence, wouldn't that automatically give a run of length $\sqrt{n}$ and width $\sqrt{n}$ just from the first $\sqrt{n}$ numbers? $\endgroup$ Nov 1, 2012 at 22:53
-
-
$\begingroup$ No, it ends with n and starts with 1+1+4+16.. If we suppose n=1024, then it starts with 338. Anyhow, it certainly starts with something smaller than n/2, so its width is at least n/2. My construction gives a sequence for every $n=4^k$ such that for all c, any run of length $c\sqrt(n)$ has width at least cn/10. $\endgroup$– domotorpNov 2, 2012 at 8:06
-
1$\begingroup$ I did indeed, however, these problems should be equivalent because you can take the inverse of the permutation. So my construction would give 13, 9, 14, 10, 5, 1, 6, 2, 15, 11, 16, 12, 7, 3, 8, 4. $\endgroup$– domotorpNov 2, 2012 at 11:10
-
1$\begingroup$ Any two consequtive elements is a run one way or the other so I don't see your $cn/10$ claim for $c=\frac{2}{\sqrt{n}}$. I probably am missing something or being too literal. $\endgroup$ Nov 4, 2012 at 2:24
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.
-
$\begingroup$ Hi Aaron, I agree that if you delay large $u$ and $d$ for as long as possible, then every long run must end "late". But how do you know that every long run must start "early"? Can't you have a long run that starts "late" and ends "late"? $\endgroup$ Nov 2, 2012 at 7:45