比利时vs摩洛哥足彩
,
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
****************************