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.
This paper gives a brief survey of binary single-deletion-correcting codes. The Varshamov-Tenengolts codes appear to be optimal, but many interesting unsolved problems remain. The connections with shift-register sequences also remain somewhat mysterious. Let us denote by R(k, ⩾ λ)[R(k, ⩽ λ)] the maximal number M such that there exist M different permutations of the set 1,…, k such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ⩽ λ) ⩽ kR(k − 1, ⩽ λ − 1), R(k, ⩾ λ) ⩾ R(k, ⩽ λ − 1) ⩽ k!, R(k, ⩾ λ) ⩽ kR(k − 1, ⩾ λ − 1). We show: R(k, ⩾ k − 2) = 2, R(k, ⩾ 1) = (k − 1)!, R(pm, ⩾ 2) = (pm − 2)!, R(pm + 1, ⩾ 3) = (pm − 2)!, R(k, ⩽ k − 3) = k!2, R(k, ⩽ 0) = k, R(pm, ⩽ 1) = pm(pm − 1), R(pm + 1, ⩽ 2) = (pm + 1)pm(pm − 1). The exact value of R(k, ⩾ λ) is determined whenever k ⩾ k0(k − λ); we conjecture that R(k, ⩾ λ) = (k − λ)! for k ⩾ k0(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ⩾ λ) − R(k, ⩽ λ)| is attained for λ = (k2) + O(klog k).   We present simple, polynomial time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve exponential error probability in a stochastic model of insertion-deletion. A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.  An (n,c,l,r) erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r l packets. We describe erasure codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.