Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes
<|reference_start|>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) \geq 2^n/V(n,d-1)$, where $V(n,d) = \sum_{i=0}^{d} {n \choose 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_2(n,d) \geq 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.<|reference_end|>
@article{jiang2004asymptotic,
    title={Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of
  Binary Codes},
    author={Tao Jiang and Alexander Vardy},
    journal={IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 50, No. 8, pp.
  1655-1664, August 2004
  (http://www.ieeexplore.ieee.org/iel5/18/29198/01317112.pdf)},
    year={2004},
    doi={10.1109/TIT.2004.831751},
    archivePrefix={arXiv},
    eprint={math/0404325},
    primaryClass={math.CO cs.IT math.AC math.IT}
}