Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

Abstract

Given positive integers $n$ and $d$, let $M(n,d)$ denote the maximum size of a permutation code of length $n$ and minimum Hamming distance $d$. The Gilbert-Varshamov bound asserts that $M(n,d)\ge n!/V(n,d-1)$ where $V(n,d)$ is the volume of a Hamming sphere of radius $d$ in ${\S }_n$. Recently, Gao, Yang, and Ge showed that this bound can be improved by a factor $\Omega (\log n)$, when $d$ is fixed and $n\to \infty$. Herein, we consider the situation where the ratio $d/n$ is fixed and improve the Gilbert-Varshamov bound by a factor that is \emph{linear in $n$}. That is, we show that if $d/n<0.5$, then $$M(n,d)\ge cn\frac{n!}{V(n,d-1)}$$ where $c$ is a positive constant that depends only on $d/n$. To establish this result, we follow the method of Jiang and Vardy. Namely, we recast the problem of bounding $M(n,d)$ into a graph-theoretic framework and prove that the resulting graph is locally sparse.

Cited by in corpus (1)

• New bounds of permutation codes under Hamming metric and Kendall's $\tau$-metric