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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.