##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## A. Vardy

#### Dept. of Engineering and Computer Science, UCSD

## ASYMPTOTIC IMPROVEMENT OF THE GILBERT-VARSHAMOV BOUND

##### 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 {2n \\over (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 will be briefly discussed. *joint work with T. Jiang, Math Department, University of Miami

Host: Van Vu

### October 21, 2003

### 4:00 PM

### AP&M 7321

****************************