Twins in words and long common subsequences in permutations

A large family of words must contain two words that are similar. We investigate several problems where the measure of similarity is the length of a common subsequence.

We construct a family of n ^1/3 permutations on n letters, such that LCS of any two of them is only cn^1/3 , improving a construction of Beame, Blais, and Huynh-Ngoc. We relate the problem of constructing many permutations with small LCS to the twin word problem of Axenovich, Person and Puzynina. In particular, we show that every word of length n over a k-letter alphabet contains two disjoint equal subsequences of length cnk^−2/3 . Connections to other extremal questions on common subsequences are exhibited.

Many problems are left open.