Exact bounds on the sizes of covering codes
A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c(r)(X). Answering a question of Hamalainen et al.[ 10], we show further connections between Turan theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n(0)(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}(n). We prove that c(r)(B-n(0, r + 2)) = Sigma(1less than or equal toiless than or equal tor+1) (([n+i-1)/(r+1)])(2)) + [n/(r + 1)] and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.
supersaturated hypergraphs binary codes covering radius turan theorem