  The sequence a_1,...,a_m is a common subsequence in the set of permutations S
= {p_1,...,p_k} on [n] if it is a subsequence of p_i(1),...,p_i(n) and
p_j(1),...,p_j(n) for some distinct p_i, p_j in S. Recently, Beame and
Huynh-Ngoc (2008) showed that when k>=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>=3 and n>=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.
