Upper Bounds on Permutation Codes via Linear Programming

Author: Tarnanen H.

Source: European Journal of Combinatorics, Volume 20, Number 1, January 1999 , pp. 101-114(14)

Publisher: Academic Press

Abstract:

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. Copyright 1999 Academic Press

Language: English

Document Type: Research article

Affiliations: Department of Mathematics, University of Turku, Turku, FIN-20014, Finland

Publication date: 1999-01-01

• In this: publication
• By this: publisher
• In this Subject: Mathematics and Statistics
• By this author: Tarnanen H.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers