Let $m = n^3 + 1$ and let $\sigma_1, \sigma_2, \sigma_3$ 3 permutations of $\{{1,2,...m}\}$. Prove that two of these permutations have same subsequence which are $n+1$ long.
I have tried to use the Erdos-Szekeres theorem (every permutation of $n^3+1$ has monotonically increasing subsequence in $n^2+1$ long or monotonically decreasing subsequence in $n+1$) but I didn't have any idea to proceed.
Any help will be appreciated.
On
My argument relies on an understanding of posets and Mirsky's theorem, which can be used to prove Erdos-Szekeres. I'm don't know how to prove it with Erdos-Szekeres, if that's what you want. Also, I realize that it's really long. The first paragraph explain poset ideas and how they apply to these posets.
We define posets $P_{1,2}, P_{1,3}, P_{2,3}$ on our set $\{1,2,\ldots,m\}$ where $i<j$ in $P_{1,2}$ if $i$ appears before $j$ in both $\sigma_1$ and $\sigma_2$, and we define the ordering on the other two posets similarly. In order theory, a chain is a set of elements $\{x_1,x_2,\ldots, x_i\}$ satisfying $x_1<x_2<\ldots x_i$, and an antichain is a set $A$ where we have neither $a<b$ nor $b<a$ for $a,b\in A$. In this language, we want to show that one of these posets contains a chain of size at least $n+1$. Two elements $x$ and $y$ in $P_{1,2}$ are incomparable (meaning neither is greater than the other) if $x$ appears before $y$ in $\sigma_1$ and $y$ appears before $x$ in $\sigma_2$, or vice versa. Hence, if $A=\{x_1,x_2,\ldots,x_n\}$ is an antichain in $P_{1,2}$, and $\sigma_1$ contains $x_1x_2\ldots x_n$ as a subsequence, then $\sigma_2$ contains $x_nx_{n-1}\ldots x_1$ as a subsequence. In other words, if $A$ is an antichain in $P_{1,2}$, then $\sigma_1$ and $\sigma_2$ contain $A$ in opposite orders.
Mirsky's theorem states that for a finite poset, the size of the longest chain is equal to the size of the smallest antichain decomposition, or a partition of our set into blocks where no two elements in the same block are comparable by our ordering. We first look at $P_{1,2}$: if we have a chain of size at least $n+1$, we're done. Otherwise, our longest chain has size at most $n$, so by Mirsky's theorem, our smallest antichain decomposition has at most $n$ antichains. By the pigeonhole principle, one of those $n$ antichains must contain at least $n^2+1$ elements. Let's call this antichain $A=\{x_1,x_2,\ldots, x_{n^2+1}\}$. Without loss of generality, say they appear in that order in $\sigma_1$, and hence in the opposite order in $\sigma_2$.
Now we look at $P_{1,3}$ restricted to $A$. If we have a chain of size at least $n+1$, we're done. Otherwise, the longest chain has size at most $n$, and our smallest antichain decomposition has at most $n$ antichains. Since $|A|\geq n^2+1$, the pigeonhole principle tells us that we must have an antichain in $A$ with at least $n+1$ elements. Call this antichain $A'$, which is a subset of $A$. Say $A'=\{x'_1,x'_2,\ldots, x'_{n+1}\}$, where $x'_1,x'_2,\ldots,x'_{n+1}$ is a subsequence of $x_1,x_2,\ldots,x_{n^2+1}$. Hence, where the elements of $A'$ appear in the given order in $\sigma_1$, they must appear in the opposite order in $\sigma_3$. But since we said that the elements of $A$, which include $A'$, appear in $\sigma_2$ also in the opposite of $\sigma_1$'s order, then $A'$ appears in the same order in $\sigma_2$ as in $\sigma_3$, so they have a common subsequence of size $n+1$.
I think you want to imitate the proof of the Erdos-Szekeres theorem, not apply it directly. Label each $1\le j\le m$ with the triple $(a,b,c)$ where $a$ is the length of the longest common subsequence of $\sigma_1$ and $\sigma_2$ that ends in $j,$ $b$ is the longest common subsequence of $\sigma_1$ and $\sigma_3$ that ends in $j,$ and $c$ is the longest common subsequence of $\sigma_2$ and $\sigma_3$ that ends in $j.$
I claim that no two elements get the same label, for suppose $1\le j,k \le m,$ with $j\ne k$ and that both $j$ and $k$ get the same label. If $j$ precedes $k$ in both $\sigma_1$ and $\sigma_2$ then $k$ has a larger $a-$label than $j$, since we can append $k$ to the largest common subsequence ending in $j$. Similarly, $k$ cannot precede $j$ in both $\sigma_1$ and $\sigma_2$ so we can assume $j$ precedes $k$ in $\sigma_1$ and $k$ precedes $j$ in $\sigma_2$. Then $j$ and $k$ must come in the same order in $\sigma_3$ as either $\sigma_1$ or $\sigma_2$ so that they have different $b-$labels or different $c-$labels.
If the longest commons subsequence is of length $n$ or less, then there are at most $n^3$ different labels, but we have $n^3+1$ different labels, contradiction.
EDIT It's just occurred to me that there are many proof of the Erdos-Szekeres theorem known. I'm referring to the one here