  The Cayley distance between two permutations $\pi, \sigma \in S_n$ is the
minimum number of \textit{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 $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) \geq \Omega_t\left(\frac{n!\log n}{n^{2t}}\right) \text{ and }
K(n,t) \geq \Omega_t\left(\frac{n! \log n}{n^t}\right).\] Our proof is based on
graph theory techniques.
