The sequence $a_1,\ldots,a_m$ is a common subsequence in the set of permutations $S = \{p_1,\ldots,p_k\}$ on $[n]$ if it is a subsequence of $p_i(1),\ldots,p_i(n)$ and $p_j(1),\ldots,p_j(n)$ for some distinct $p_i$, $p_j$ in $S$. Recently, Beame and Huynh-Ngoc (2008) showed that when $k \ge 3$, every set of $k$ permutations on $[n]$ has a common subsequence of length at least $n^{1/3}$.
We show that, surprisingly, this lower bound is asymptotically optimal for all constant values of $k$. Specifically, we show that for any $k \ge 3$ and $n \ge k^2$ there exists a set of $k$ permutations on $[n]$ in which the longest common subsequence has length at most $32(kn)^{1/3}$. The proof of the upper bound is constructive, and uses elementary algebraic techniques.