Let $φ_1$, $φ_2$, and $φ_3$ be permutations on $[m]$. Then there is some pair $1 ≤ a < b ≤ 3$ such that $φ_a(1), . . . , φ_a(m)$ and $φ_b(1), . . . , φ_b(m)$ have a common subsequence of length at least $m^{1/3}$.
I found a proof for this theorem here http://homes.cs.washington.edu/~beame/papers/freq.pdf (lemma 5.9) and I have been trying to prove that the lemma is tight. I would appreciate if someone could help me with an example.
To simplify things a bit, let us write $m = k^3$. We wish to construct a set of $3$ permutations such that no pair has a common subsequence of length $k+1$.
Let $\varphi_1$ be the identity permutation $1, 2, 3, ..., k^3$. (Note that there is no loss of generality here, since by permuting the symbols for all three permutations you can always assuming that one of the permutations is the identity.)
This means that the other two permutations cannot have any increasing sequences of length $k+1$. By Erdős-Szekeres, they must have decreasing sequences of length $k^2$. Let the second permutation be given by a chain of $k$ such decreasing sequences: $$\varphi_2 = k^2, k^2 - 1, ..., 2, 1, 2k^2, 2k^2 - 1, ..., k^2 + 2, k^2 + 1, \quad ... \quad , k^3, k^3 - 1, ..., k^3 - k^2 + 1.$$ Note that the only increasing subsequences involve at most one term from each of these $k$ consecutive decreasing subsequences, and hence have length at most $k$, as required.
We now have to create $\varphi_3$. First consider the subintervals of symbols $I_i = \{(i-1)k^2 + 1, (i-1)k^2 + 2, ..., ik^2 \}$ for $1 \le i \le k$. For each $i$, $\varphi_1|_{I_i}$ is increasing, while $\varphi_1|_{I_i}$ is decreasing. However, note that in both permutations, these intervals appear contiguously, and in increasing order. That is, in both $\varphi_1$ and $\varphi_2$, the elements from $I_1$ come first, then those from $I_2$, and so on, with the elements from $I_k$ coming last.
For $\varphi_3$, we will invert this order, so the elements from $I_k$ will come first, followed by the elements from $I_{k-1}$, and so on, until we end with the elements from $I_1$.
Now within each of these intervals of size $k^2$, $\varphi_3|_{I_i}$ cannot have any increasing (because of $\varphi_1$) or decreasing (because of $\varphi_2$) subsequences of length $k$. This can be achieved by taking a chain of $k$ decreasing subsequences of length $k$, i.e. $$ \varphi_3|_{I_i} = (i-1)k^2 + k , (i-1)k^2 + k-1, ..., (i-1)k^2 + 1, (i-1)k^2 + 2k, (i-1)k^2 + 2k - 1, ..., (i-1)k^2 + k + 1, \quad ... \quad, ik^2, ik^2 - 1, ..., ik^2 - k + 1. $$
Concatenating these subsequences in decreasing order of $i$ thus gives the desired third sequence.
Remark: I am sorry to give such a long exposition for should be, according to the authors of the paper, "not hard" - I just like to type a lot. Note that they observe that you can in fact add a fourth sequence without creating a longer common subsequence. To see how you might do this, you might like to consider the elements of the permutation in base $k$, and think about how each $\varphi_i$ can be described in terms of the base-$k$ digits.