Longest Common Subsequences in Sets of Permutations

2009/04/10 by Paul Beame, Beame, Paul, Eric Blais +3 · 1 citation
Computer Science · Engineering · Mathematics · #05D99 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0904.1615

openalex publication_date 2009/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The sequence a₁,...,a_m is a common subsequence in the set of permutations S = p₁,...,p_k on [n] if it is a subsequence of p_i(1),...,p_i(n) and p_j(1),...,p_j(n) for some distinct p_i, p_j in S. Recently, Beame and Huynh-Ngoc (2008) showed that when k>=3, every set of k permutations on [n] has a common subsequence of length at least n^1/3. We show that, surprisingly, this lower bound is asymptotically optimal for all constant values of k. Specifically, we show that for any k>=3 and n>=k² there exists a set of k permutations on [n] in which the longest common subsequence has length at most 32(kn)^1/3. The proof of the upper bound is constructive, and uses elementary algebraic techniques.

Cited by

• Twins in words and long common subsequences in permutations

Related

• A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
• Average length of the longest k-alternating subsequence
• Longest common subsequences in sets of words
• Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations