Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall -Metric

The Cayley distance between two permutations, Sₙ is the minimum number of transpositions required to obtain the permutation from. When we only allow adjacent transpositions, the minimum number of such transpositions to obtain from is referred to the Kendall -distance. A set C of permutation words of length n is called a t-Cayley permutation code if every pair of distinct permutations in C has Cayley distance greater than t. A t-Kendall permutation code is defined similarly. Let C (n, t) and K (n, t) be the maximum size of a t-Cayley and a t-Kendall permutation code of length n, respectively. In this paper, we improve the Gilbert-Varshamov bound asymptotically by a factor (n), namely \ C (n, t) ₜ (n! nn^{2t}) and K (n, t) ₜ (n! nnᵗ). \ Our proof is based on graph theory techniques.