Vtgyjfy

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.

I think you want to imitate the proof of the Erdos-Szekeres theorem, not apply it directly. Label each $1le jle 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 $1le j,k le m,$ with $jne 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

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,bin 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_2ldots 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$.