Upper Bounds on Permutation Codes via Linear Programming

✍ Scribed by H. Tarnanen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 140 KB
• Volume: 20
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1998.0272

✦ Synopsis

An upper bound on permutation codes of length n is given. This bound is a solution of a certain linear programming problem and is based on the well-developed theory of association schemes. Several examples are presented. For instance, the 255 values of the bound for n ≤ 8 are tabulated. It turns out that, for n ≤ 8, the Kiyota bound for group codes also holds for unrestricted codes at least in 178 cases. Also an easier (but weaker) polynomial version of the bound is given. It is obtained by showing that the mappings F k (θ) (0 ≤ k ≤ n/2), where F k is the Charlier polynomial of degree k and θ the natural character of the symmetric group S n , are mutually orthogonal characters of S n .