  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) \geq 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)\geq 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.
