Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

Given positive integers n and d, let A₂(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₂(n,d)≥2ⁿ/V(n,d-l), where V(n,d) = σ_i=0^d(_iⁿ) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A₂(n, d)≥c2ⁿ/V(n,d-1)log₂V(n, d-1) whenever d/n≤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.