Permutation codes
Permutation codes are a family of error correction codes that were introduced first by Slepian in 1965. and have been widely studied both in Combinatorics and Information theory due to their applications related to Flash memory and Power-line communication. Definition and properties 
A permutation code  is defined as a subset of the Symmetric Group in  endowed with the usual Hamming distance between strings of length . More precisely, if  are permutations in , then 

The minimum distance of a permutation code  is defined to be the minimum positive integer  such that there exist   , distinct, such that . One of the reasons why permutation codes are suitable for certain channels is that the alphabet symbols only appear once in each codeword, which for example makes the errors occurring in the context of powerline communication less impactful on codewords

Gilbert-Varshamov bound 

A main problem in permutation codes is to determine the value of , where  is defined to be the maximum number of codewords in a permutation code of length  and minimum distance . There has been little progress made for , except for small lengths. We can define  with  to denote the set of all permutations in  which have distance exactly  from the identity. Let  with , where  is the number of derangements of order . The Gilbert-Varshamov bound is a very well known upper bound, and so far outperforms other bounds for small values of . Theorem 1: 

There has been improvements on it for the case where   as the next theorem shows. Theorem 2: If  for some integer , then

. For small values of  and , researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed automorphisms

Other Bounds 
There are numerous bounds on permutation codes, we list two here

Gilbert-Varshamov Bound Improvement 
An Improvement is done to the Gilbert-Varshamov bound already discussed above. Using the connection between permutation codes and independent sets in certain graphs one can improve the Gilbert–Varshamov bound asymptotically by a factor , when the code length goes to infinity. Let  denote the subgraph induced by the neighbourhood of identity in , the Cayley graph   and . Let  denotes the maximum degree in 

Theorem 3: Let  and 

Then, 

where . The Gilbert-Varshamov bound is,  

Theorem 4: when  is fixed and  does to infinity, we have

Lower bounds using linear codes 
Using a  linear block code, one can prove that there exists a permutation code in the symmetric group of degree , having minimum distance at least  and large cardinality. A lower bound for permutation codes that provides asymptotic improvements in certain regimes of length and distance of the permutation code is discussed below. For a given subset  of the symmetric group , we denote by  the maximum cardinality of a permutation code of minimum distance at least  entirely contained in , i.e. . Theorem 5: Let  be integers such that  and . Moreover let  be a prime power and  be positive integers such that  and . If there exists an  code  such that  has a codeword of Hamming weight , then

where 

Corollary 1: for every prime power  , for every ,

. Corollary 2: for every prime power  , for every ,

. References

Error detection and correction