{
  "id": "math/0404325",
  "version": "v1",
  "published": "2004-04-19T02:18:47.000Z",
  "updated": "2004-04-19T02:18:47.000Z",
  "title": "Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes",
  "authors": [
    "Tao Jiang",
    "Alexander Vardy"
  ],
  "comment": "10 pages, 3 figures; to appear in the IEEE Transactions on Information Theory, submitted August 12, 2003, revised March 28, 2004",
  "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)",
  "doi": "10.1109/TIT.2004.831751",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.AC",
    "math.IT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-04-19T02:18:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C90",
      "94B65",
      "05A16",
      "05C69"
    ],
    "keywords": [
      "binary code",
      "asymptotic improvement",
      "well-known gilbert-varshamov bound asserts",
      "minimum distance",
      "graph-theoretic framework"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......4325J"
    }
  }
}