combinatoricsdiscrete mathematics
As I understand, the Erdös-Szekeres theorem says that for every sequence $a_1$,$a_2$,…,$a_{n^2+1}$ of $n^2+1$ real numbers, there is a subsequence of length $n+1$ which is either increasing or decreasing.
If I set $n=2$ and select my sequence to be ${1,3,2,5,4}$
Then I should have a subsequence of length $3$ which is either increasing or decreasing right?
I can't really see it happening, what am I doing wrong? Thanks
The proof actually starts with a sequence of length $n\ge(r-1)(s-1)+1$ and shows that it has either an increasing subsequence of length $r$ or a decreasing subsequence of length $s$. (In other words, it shifts the $r$ and $s$ of the usual statement of the theorem by $1$.)
Suppose that there is no chain of length $r$ in the given partial order. Then the maximal length of any chain is at most $r-1$, and by the dual Dilworth theorem the partial order can be partitioned into at most $r-1$ antichains. The partial order has at least
$$(r-1)(s-1)+1=rs-r-s+2$$
elements; if you divide these into $r-1$ or fewer parts, the mean part size is at least
$$\frac{rs-r-s+2}{r-1}=\frac{(r-1)(s-1)+1}{r-1}=s-1+\frac1{r-1}\;,$$
so the largest part must be at least
$$\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=\left\lceil s-1+\frac1{r-1}\right\rceil=s-1+\left\lceil\frac1{r-1}\right\rceil=s-1+1=s\;.$$
The second part of the argument is virtually identical, with the rôles of $r$ and $s$ interchanged and using Dilworth’s theorem rather than its dual.
Maybe an easier way is to make an $n \times n$ grid, fill it in with numbers from $1$ to $n^2$ in lexicographic order, then read the rows from the bottom up. So it would be $3,4,1,2$ and $7,8,9,4,5,6,1,2,3$.
There is obviously no increasing sequence with more than $n$ terms since the numbers just go up in $n$ unit blocks before decreasing forever. And a decreasing subsequence could only use at most one number from each of those blocks, so it couldn't be longer than $n$ terms either.
Your method works too, but it's slightly harder to show that the increasing subsequences can't be too long. It's obvious if you write out the grid and track what an increasing sequence would have to look like.
Here is your sequence written in lexicographic form. Notice that to make a subsequence that is increasing you can only choose terms that are to the right or below the previous term, so you cannot have more terms than columns in an increasing subsequence.
Best Answer
Numberphile covered this theorem. By $n^2+1$ it's forced to escape all positive lattice points, in an n by n grid, since they need to be distinct in at least 1 coordinate, they are forced to $n+1$ in one of the coordinates. They also don't need to be consecutive as has been pointed out.