Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ball of radius $R$.

I would greatly appreciate any references to literature or ideas on how to approach the problem. I strongly suspect that a solution for any $R$ comes from placing the center of the ball at $(\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},0,\ldots,0)$ with the number of nonzero coordinates being $\lfloor 4R^2 \rfloor=\lfloor D^2 \rfloor $, where $D$ is the diameter (for $D \leq n$).

Any references or ideas are welcome.

Thanks!

share|improve this question
1  
That seems like a good guess to me. You could try using the fact that any set of more than $2^k$ vertices of $H^n$ cannot be contained in a $k$-dimensional affine subspace of $\mathbb R^n$. –  Greg Martin May 9 '13 at 0:52
    
This is not always true. Already if n=2 (we have a square), then if R is a little less than $\sqrt(2)/2$, then the best we can do is to cover 3 vertices. –  domotorp Jun 25 '13 at 15:12
    
@domotorp Indeed, it is not always true. However, if one can cover 3 vertices then one can cover the whole square. I believe the conjecture first breaks down at dimension 16 –  user21277 Jun 26 '13 at 19:42
    
I think you are mistaken, in my example with the given radius we can cover 3 vertices but not the whole square. –  domotorp Jun 27 '13 at 15:14
    
@domotorp Consider 3 vertices of a square. These form an isosceles right triangle. The circumcenter of this triangle is the midpoint of the hypotenuse, which is also the center of the square. –  user21277 Jun 28 '13 at 2:10
show 2 more comments

1 Answer 1

Sometimes it is better to place the ball "in the corner". For example:

Let $n=8$ and $R=\sqrt{\frac{7}{8}}$. Then the ball with center $(\frac{1}{8}, \frac{1}{8}, \dots, \frac{1}{8})$ and radius $R$ covers exactly $9$ vertices (those with at most one coordinate equal to $1$), but a ball with radius $R$ cannot cover a $4$-dimensional unit hypercube, which requires radius at least $1$.

There is even no upper bound on the number of points a ball with radius $1$ can cover, provided the dimension is not bounded. Generalizing previous construction, a ball with center $(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n})$ and radius $\sqrt{\frac{n-1}{n}}$ covers $n+1$ vertices of the $n$-dimensional hypercube. As user21277 points out, for $n=16$ this is better than placing the ball in the center of a $4$-dimensional face.

In general, for $n>2i$, a ball with center $(\frac{i}{n}, \frac{i}{n}, \dots, \frac{i}{n})$ and radius $\sqrt{\frac{i(n-i)}{n}}$ covers ${n \choose i} + {n \choose i-1} + \cdots +{n \choose 0}$ vertices: those with at most $i$ coordinates equal to $1$. A ball with the same radius cannot cover all $2^{4i}$ vertices of a $4i$-dimensional unit hypercube.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.