Twins in words and long common subsequences in permutations (Q314398): Difference between revisions

Two subsequences of a word \(w\) are said to be twins if they are equal as words, and they do not contain a letter from the same position in \(w\). Let \(\mathrm{LT}(w) \) be the length of the longest twins contained in a word \(w\) and \(\mathrm{LT}(k,n) \) be the minimum of the values \(\mathrm{LT}(w) \) for words \(w\) over a \(k\)-letter alphabet. The twin problem of Axenovich-Person-Puzynina is to determine how large \(\mathrm{LT}(k,n)\) is. The authors show that \(\mathrm{LT}(k,n)\geq3^{-4/3}k^{-2/3}n-3^{-1/3}k^{1/3}\) and, for \(k\geq3\), \(\mathrm{LT}(k,n)\geq\frac{1.02}{k}n-o\left( n\right)\), the former being a better lower bound for large values of \(k\). Further they prove that \(\mathrm{LT}(k,n)\leq\alpha n\) for a constant \(\alpha\) depending on \(k\). They use in their proofs a generalization of the result of Beame and Huynh-Ngoc, which asserts that for any three words being permutations of the letters of a \(k\)-letter alphabet, the longest common subsequence of any two of them is of length at least \(k^{1/3}\).