A bound on permutation codes (Q396801): Difference between revisions

Summary: Consider the symmetric group \(S_n\) with the Hamming metric. A permutation code on \(n\) symbols is a subset \(C\subseteq S_n.\) If \(C\) has minimum distance \(\geq n-1,\) then \(| C|\leq n^2-n.\) Equality can be reached if and only if a projective plane of order \(n\) exists. Call \(C\) embeddable if it is contained in a permutation code of minimum distance \(n-1\) and cardinality \(n^2-n.\) Let \(\delta =\delta (C)=n^2-n-| C|\) be the deficiency of the permutation code \(C\subseteq S_n\) of minimum distance \(\geq n-1.\)We prove that \(C\) is embeddable if either \(\delta\leq 2\) or if \((\delta^2-1)(\delta +1)^2<27(n+2)/16.\) The main part of the proof is an adaptation of the method used to obtain the famous Bruck completion theorem for mutually orthogonal Latin squares.