  Given a set of $t$ words of length $n$ over a $k$-letter alphabet, it is
proved that there exists a common subsequence among two of them of length at
least $\frac{n}{k}+cn^{1-1/(t-k-2)}$, for some $c>0$ depending on $k$ and $t$.
This is sharp up to the value of $c$.

Combinatorics