Permutation subsequences

Question

Given three permutations $p_1,p_2,p_3$ of $\{1,2,\ldots,n^3+1\}$, prove that two of them have a common subsequence of length $n+1$.

I have tried to solve this using the pigenhole principle but I didnt progress too much, any help would be appreciated

edit: when I say subsequence I mean that there are $1<=r<q<=3$ and $1<=i(1)<i(2)<...<i(n+1)<=n^3+1$ and $1<=j(1)<j(2)<...<j(n+1)<=n^3+1$ so that $p_r(i1)=p_q(j1)$, $p_r(i2)=p_q(j2)$ and so on, not necessarily consecutive

Answer 1

I don't think that statement is true.

I am not shure what you think a permutation of a set is, so lets just assume we talk about sequences. Take $n=2$, so $n^3+1 = 9$, so our sequence is $l=(1,2,3,4,5,6,7,8,9)$. Now I have these three permutations:

• $p_1(l) = (1,2,3,4,5,6,7,8,9) = l$
• $p_2(l) = (9,8,7,6,5,4,3,2,1)$
• $p_3(l) = (1,3,5,7,9,2,4,6,8)$

Clearly, none of those have any common subsequence of length $n+1=3$ (or even of length $2$).

Answer 2

That's not true. Consider three permutations : $$p_1 = (1, \dots, n^3+ 1)$$ $$p_2 = (n^3+1, \dots, 1)$$ $$p_3 = (1, n^3, 3, n^3-2, \dots)$$ where $p_3[i] = p_{i \bmod 2}[i]$

Answer 3

You can prove this with ideas that are used in proving the Erdos-Szekeres theorem. Without loss of generality, we can assume $p_1$ is the identity permutation (otherwise just relabel numbers). Then, if either of $p_2$ or $p_3$ has an increasing subsequence of length $n + 1$, we are done. So assume their longest increasing subsequences are both at most $n$.

For each $k \in \{1, 2, \ldots , n^3 + 1\}$, define $f_i(k)$ to be the length of the longest increasing subsequence of $p_i$ whose last term is $k$. Our assumption says that $1 \le f_i(k) \le n$.

Note that there are only $n^2$ possible values for the pair $(f_2(k), f_3(k))$. Thus, by the pigeonhole principle, there must exist $n + 1$ integers

$$k_1 > k_2 > \cdots > k_{n + 1}$$

such that $(f_2(k_i), f_3(k_i)) = (f_2(k_j), f_3(k_j))$ for all $i$ and $j$.

We claim now that $(k_1, k_2, \ldots , k_{n + 1})$ is a subsequence of both $p_2$ and $p_3$. Indeed, suppose instead that for some $i$, $k_i$ appears after $k_{i + 1}$ in permutation $p_2$. Then, any increasing subsequence ending at $k_{i + 1}$ can be extended one longer by adding $k_i$, which contradicts the equality $f_2(k_i) = f_2(k_{i + 1})$. The same argument applies for $p_3$, so we have obtained our common subsequence of length $n + 1$.