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 log(n), namely \[ C(n,t) ≥ Ω_t({n!log n}{n²ᵗ}) and K(n,t) ≥ Ω_t(n! log n/n^t).\] Our proof is based on graph theory techniques.