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

The Cayley distance between two permutations $\pi ,\sigma \in S_n$ is the minimum number of $\mathit{\text{transpositions}}$ required to obtain the permutation $\sigma$ from $\pi$. When we only allow adjacent transpositions, the minimum number of such transpositions to obtain $\sigma$ from $\pi$ is referred to the Kendall $\tau$-distance. A set $C$ of permutation words of length $n$ is called a $d$-Cayley permutation code if every pair of distinct permutations in $C$ has Cayley distance at least $d$. A $d$-Kendall permutation code is defined similarly. Let $C(n,d)$ and $K(n,d)$ be the maximum size of a $d$-Cayley and a $d$-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,d+1)\ge {\mathrm{\Omega }}_d\left(\frac{n!\log n}{n^{2d}}\right)\text{ and }K(n,d+1)\ge {\mathrm{\Omega }}_d\left(\frac{n!\log n}{n^d}\right)\mathrm{.}$$ Our proof is based on graph theory techniques.