Codes et tableaux de permutations, construction, énumération et automorphismes /Permutation codes and permutations arrays: construction, enumeration and automorphisms
A permutation code G(n,d) is a subset C of Sym(n) such that the Hamming distance D between two elements of C is larger than or equal to d. In this thesis, we characterize the isometry group of the metric space (Sym(n),D) and we prove that these isometries are automorphisms of the association scheme induced on Sym(n) by the conjugacy classes. This leads, by linear programming, to new upper bounds for the maximal size of G(n,d) codes for n and d fixed and n between 11 and 13. We develop generating algorithms with rejection of isomorphic objects. In order to classify the G(n,d) codes up to isometry, we construct invariants and study their efficiency. We generate all G(4,3) and G(4,5)codes up to isometry; there are respectively 61 and 9445 of them. Precisely 139 out of the latter codes are maximal and explicitly described. We also study other classes of G(n,d)codes.
Document Full Text
Advisor:Storme, Leo; Cara, Philippe; Doyen, Jean; Leemans, Dimitri; Delandtsheer, Anne; Doignon, Jean-Paul
School:Université libre de Bruxelles
Source Type:Master's Thesis
Schéma d'association/ Association Scheme
Date of Publication:06/22/2009