Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:New Upper Bounds for the Size of Permutation Codes via Linear Programming. | New Upper Bounds for the Size of Permutation Codes via Linear Programming Mathieu Bogaerts Universite Libre de Bruxelles Service de Mathematiques Faculte des Sciences Appliquees CP 165 11 avenue Roosevelt 50 B-1050 Brussels Belgium mbogaert@ Submitted Jan 2 2010 Accepted Sep 30 2010 Published Oct 15 2010 Mathematics Subject Classification 05B15 Abstract An n d -permutation code of size s is a subset C of Sn with s elements such that the Hamming distance dH between any two distinct elements of C is at least equal to d. In this paper we give new upper bounds for the maximal size g n d of an n d -permutation code of degree n with 11 n 14. In order to obtain these bounds we use the structure of association scheme of the permutation group Sn and the irreducible characters of Sn. The upper bounds for g n d are determined solving an optimization problem with linear inequalities. 1 Permutation arrays and permutation codes An n d -permutation code of distance d size s and degree n is a non-empty subset C of the symmetric group Sn acting on the set 1 . n such that the Hamming distance between any two distinct elements of C is at least equal to d. The Hamming distance between two permutations ộpộ G Sn is defined as dH a i G 1 --- n ộ i i . The weight of a permutation ộ G Sn if the number of non fixed points of ộ. The s X n array A associated to a n d -permutation code C ội . ộs of size s by Aij ội j has the following properties every symbol 1 to n occurs exactly in one cell of any row and any two rows disagree in at least d columns. Such an array is called a permutation array PA of distance d size s and degree n. Permutation codes have first been proposed by Ian Blake in 1974 as error-correcting codes for powerline communications 3 . This application motivates the study of the largest possible size that a permutation code can have. Upper bounds for the maximal size p n d of a permutation code with fixed parameters n and d have been studied by THE ELECTRONIC JOURNAL .
