Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall $\tau$-Metric
<|reference_start|>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 \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 $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) \geq \Omega_d\left(\frac{n!\log n}{n^{2d}}\right) \text{ and } K(n,d+1) \geq \Omega_d\left(\frac{n! \log n}{n^d}\right).\] Our proof is based on graph theory techniques.<|reference_end|>
@article{nguyen2024improving,
    title={Improving the Gilbert-Varshamov bound for permutation Codes in the
  Cayley metric and Kendall $\tau$-Metric},
    author={The Nguyen},
    journal={arXiv preprint arXiv:2404.15126},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.15126},
    primaryClass={math.CO cs.DM cs.IT math.IT}
}