You are given three permutations of $\langle 1,\dotsc, 28 \rangle$. Show that two of them have common sub-sequence of length four.
I tried saying that every permutation has $\binom{28}{4}$ subsequences of length four, so there are $\ 3*{28 \choose 4}$ pigeons, and that there are 28*27*26*25 sequences of length 4 in general - the holes. But, $\ 3*{28 \choose 4}$ is less than 28*27*26*25. So how can I show that? thanks
We can prove this via lemma $5.9$ of the following paper:
Paul Beame and Dang-Trinh Huynh-Ngoc. On the value of mul tiple read/write streams for approximating frequency moments.
Lemma 5.9: Let $\phi_1,\phi_2,\phi_3$ be permutations on $[m]$, then we can select two permutations, $\phi_a,\phi_b$ so that they share a subsequence of size at least $m^{1/3}$.
Proof (note the similarity to the proof of the Erdös Szekeres theorem) : Suppose not, then for every $i\in [m]$ let $l_i\in [m']^3$, where $m'=\lceil m^{1/3}-1\rceil$, be defined as follows: $l_i[1]$ is the longest common subsequence of $\phi_1(1),\phi_1(2),\dots \phi_1(s)$ and $\phi_2(1),\phi_2(2)\dots \phi_2(t)$, where $\phi_1(s)=\phi_2(t)=i$. Notice this number is less than $m^{1/3}$ by hypothesis, and therefore belongs to $[m']$
We define $l_i[2],l_i[3]$ analogously for the other two pairs of permutations. Now (as in the proof of Erdös-Szekeres) we notice $l_i\neq l_j$ for $i\neq j$.
Notice for each permutation, $i$ must appear before or after $j$ (two options), so therefore there must be two permutations such that $i$ appears before $j$ in both ( or $j$ before $i$). In the first case it is clear that $l_i[x]<l_j[x]$ (where $x$ is the integer corresponding to the pair of those two permutations).
This is a contradiction, since there are $m'^3<m$ options for $l_i$, and there are $m$ possible values for $i$.
We conclude there must be two permutations sharing a subsequence of length at least $m^{1/3}$.
In our case there must be two permutations sharing a subsequence of length at least $28^{1/3}\approx3.036$, since the length of a sequence is an integer, our result follows.