Longest Common Subsequences in Sets of Words

Given a set of t ≥ k + 2 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 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.