Longest Common Subsequences in Sets of Permutations

Details Longest Common Subsequences in Sets of Permutations Longest Common Subsequences in Sets of Permutations

2009-04-10

arxiv.org/abs/0904.1615v1

Mathematics

Combinatorics

9 pages

Scientific paper

The sequence a_1,...,a_m is a common subsequence in the set of permutations S = {p_1,...,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^2 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.

Affiliated with

Also associated with

No associations

Rating

Longest Common Subsequences in Sets of Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Longest Common Subsequences in Sets of Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest Common Subsequences in Sets of Permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-673298