Twins in words and long common subsequences in permutations

2013/06/29 by Lidong Zhou, Bukh, Boris, Zhou, Lidong · 3 citations
Computer Science · #05D40 #05D99 #68R15 #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1307.0088

openalex publication_date 2013/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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. Many problems are left open.

Citations

• Longest Common Subsequences in Sets of Permutations
• A regularity lemma and twins in words

Cited by

• Asymptotically half of binary words are shuffle squares
• Results on long twins in random words and permutations
• Most frequent subsequences in a word

Related

• Longest common subsequences in sets of words
• A regularity lemma and twins in words
• Long twins in random words
• Results on long twins in random words and permutations
• Tight multiple twins in permutations