“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 17376  


Abstract:  
We give two methods that are based on the representation theory of symmetric groups to study the largest size P(n,d) of permutation codes of length n, i.e., subsets of the set Sn of all permutations on {1, . . . , n} with the minimum distance (at least) d under the Kendall Ã?metric. The first method is an integer programming problem obtained from the transitive actions of Sn. The second method can be applied to refute the existence of perfect codes in Sn . Applying these methods, we reduce the known upper bound (n Ã¢?? 1)! Ã¢?? 1 for P (n, 3) to ( n Ã¢?? 1 ) ! Ã¢?? Ã¢?? n/3 Ã¢?? + 2 Ã¢?Â¤ ( n Ã¢?? 1 ) ! Ã¢?? 2 , whenever n Ã¢?Â¥ 11 is prime. If n = 6 , 7 , 1 1 , 1 3 , 1 4 , 1 5 , 17, the known upper bound for P(n, 3) is decreased by 3, 3, 9, 11, 1, 1, 4, respectively.
Download TeX format 

back to top 