Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)? - MathOverflow

Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-06-18T12:18:21Z

(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.

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.)

Answer by Ben Green for Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-06-18T15:16:44Z

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.

Answer by Seva for Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-07-16T10:21:09Z

Striped out of the coding-theory notation, Theorem 12.5.10 of "Covering Codes" by Cohen, Honkala, Litsyn, and Lobstein reads as follows:

If every element of ${\mathbb F}_2^n$ is at most Hamming distance $r$ away from an element of a set $A\subset{\mathbb F}_2^n$ , then $$ r\ge n/2-12\sqrt{|A|}. $$

(A remark on page 352 indicates that this theorem originates from a year 1986 paper of Lovasz, Spencer, and Vesztergombi.)

An immediate corollary is that in order to cover the whole space with balls of radius $r=n/2-c\sqrt n$, one needs at least $(c^2/144)n=\Omega(n)$ balls.

Answer by Oded Regev for Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-12-14T14:11:42Z

Spencer's famous "Six Standard Deviations Suffice" is essentially equivalent to what you're asking (for a statement and proof see, e.g., the Alon-Spencer book or the new proof by Lovett and Meka). It shows, e.g., that with balls of radius $n/2-6\sqrt{n}$ you need n balls to cover the cube. It also gives $\Omega(n)$ for any radius $n/2-c\sqrt{n}$.