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

Given positive integers $n$ and $d$, let $A_2(n,d)$ denote the maximum size of a binary code of length $n$ and minimum distance $d$. The well-known Gilbert-Varshamov bound asserts that $A_2(n,d)\ge 2^n\mathrm{/}V(n,d-1)$, where $V(n,d)={\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$ is the volume of a Hamming sphere of radius $d$. We show that, in fact, there exists a positive constant $c$ such that $$A_2(n,d)\ge c\frac{2^n}{V(n,d-1)}{\log }_{2}V(n,d-1)$$ whenever $d/n \le 0.499$. The result follows by recasting the Gilbert- Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.