(where c>0 and the balls need not be disjoint?)


This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some time googling the literature on [covering codes](http://en.wikipedia.org/wiki/Covering_code). 


A simple probabilistic argument shows that you can cover the Boolean cube with O(n) Hamming balls of radius $n/2-c\sqrt n$ each, for any $c>0$. My *guess* would be that you can't do it with (much) fewer---O(1) Hamming balls seems aggressively optimistic---but I don't know if it's known how to prove that.


(In the language of coding theory, I want to know whether $K\_2(n,n/2-c\sqrt n)$, the minimum size of a binary covering code with radius $n/2-c\sqrt n$, can be upper-bounded by a constant depending only on c, not on n, at least for some c>0.)



Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt{n}$?
I think the answer to this is no. Suppose you can cover the cube with $m$ translates of the Hamming ball of radius $\frac{n}{2} - c\sqrt{n}$. Restrict this to a covering of the sets of size $k := \frac{n}{2} - \frac{1}{10} c \sqrt{n}$. This gives an $m$-colouring of these sets in a natural way. Now if two sets have the same colour then they intersect, and therefore we have an $m$-colouring of the Kneser graph $KG\_{n,k}$. But Lovasz famously proved that the chormatic number of the Kneser graph is $n - 2k + 2 = \Omega(\sqrt{n})$.


I'm not sure whether one can use similar methods to get $\Omega(n)$, which is likely the sharp bound. Searching in the literature for "Borsuk graph" may yield results. With thanks to Benny Sudakov.


