Longest Common Subsequences in Sets of Permutations
| dc.creator | Beame, Paul | |
| dc.creator | Blais, Eric | |
| dc.creator | Huynh-Ngoc, Dang-Trinh | |
| dc.date | 2009-04-10 | |
| dc.date.accessioned | 2026-07-07T13:02:23Z | |
| dc.date.available | 2026-07-07T13:02:23Z | |
| dc.description | 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. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/0904.1615 | |
| dc.identifier | http://arxiv.org/abs/0904.1615 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226431 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D99 | |
| dc.title | Longest Common Subsequences in Sets of Permutations | |
| dc.type | text |