Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T01:59:33Z http://mathoverflow.net/feeds/question/99893 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2 Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)? Scott Aaronson 2012-06-18T12:18:21Z 2012-12-14T14:11:42Z <p>(where c&gt;0 and the balls need not be disjoint?)</p> <p>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 <a href="http://en.wikipedia.org/wiki/Covering_code" rel="nofollow">covering codes</a>. </p> <p>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 <i>guess</i> 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.</p> <p>(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&gt;0.)</p> http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/99906#99906 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)? Ben Green 2012-06-18T15:16:44Z 2012-06-18T15:16:44Z <p>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})$.</p> <p>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.</p> http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/102340#102340 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)? Seva 2012-07-16T10:21:09Z 2012-07-16T10:21:09Z <p>Striped out of the coding-theory notation, Theorem 12.5.10 of "Covering Codes" by Cohen, Honkala, Litsyn, and Lobstein reads as follows:</p> <blockquote> <p>If every element of <code>${\mathbb F}_2^n$</code> is at most Hamming distance $r$ away from an element of a set <code>$A\subset{\mathbb F}_2^n$</code>, then <code>$$r\ge n/2-12\sqrt{|A|}.$$</code></p> </blockquote> <p>(A remark on page 352 indicates that this theorem originates from a year 1986 paper of Lovasz, Spencer, and Vesztergombi.) </p> <p>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 <code>$(c^2/144)n=\Omega(n)$</code> balls.</p> http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/116375#116375 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)? Oded Regev 2012-12-14T14:11:42Z 2012-12-14T14:11:42Z <p>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 <a href="http://arxiv.org/abs/1203.5747" rel="nofollow">new proof</a> 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}$.</p>