Looking for construction related to Erdos-Szekeres theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:01:32Z http://mathoverflow.net/feeds/question/111207 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111207/looking-for-construction-related-to-erdos-szekeres-theorem Looking for construction related to Erdos-Szekeres theorem Gabriel Nivasch 2012-11-01T20:24:48Z 2012-11-04T08:26:55Z <p>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) &lt; p(i_2) &lt; \cdots &lt; p(i_m)$ for $i_1 &lt; i_2 &lt; \cdots &lt; 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).</p> http://mathoverflow.net/questions/111207/looking-for-construction-related-to-erdos-szekeres-theorem/111214#111214 Answer by domotorp for Looking for construction related to Erdos-Szekeres theorem domotorp 2012-11-01T21:04:16Z 2012-11-04T08:26:55Z <p>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&amp;3\cr 2&amp;4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&amp;3&amp;9&amp;11\cr 2&amp;4&amp;10&amp;12\cr 5&amp;7&amp;13&amp;15\cr 6&amp;8&amp;14&amp;16\cr \end{array}$ and so on.</p> <p>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)$.</p> <p>Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.</p> http://mathoverflow.net/questions/111207/looking-for-construction-related-to-erdos-szekeres-theorem/111248#111248 Answer by Aaron Meyerowitz for Looking for construction related to Erdos-Szekeres theorem Aaron Meyerowitz 2012-11-02T05:00:38Z 2012-11-03T14:04:02Z <p>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.</p> <p>So perhaps the question is this: </p> <blockquote> <p>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?</p> </blockquote> <p>An upper bound is $\frac{m^2}{2}$ but I am not sure how close we can come. Here is a start: </p> <p>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 <strong>profile</strong> 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).$</p> <p>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 </p> <p>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.</p>