# A covering problem for the Hamming cube

Consider the set of all $k$-subsets of $\{1,\dots,n\}$, naturally identified with a subset $A$ of $\{0,1\}^n$ where each element has exactly $k$ ones. Is there a sharp bound known for $\epsilon$-covering of this set in the Hamming distance?

More specifically, suppose that $k = \gamma n$ where $\gamma \in(0,1/2)$ is fixed. The cardinality of $A$ is asymptotically $|A| \sim e^{n h(\gamma)}$ where $h(\cdot)$ is the binary entropy function. Is there an $\epsilon$-covering of $A$ in Hamming distance with $e^{ \frac{C n}{\log n}}$ elements and say $\epsilon \le \frac{n}{(\log n)^{2}}$? In other words, how large $\epsilon$ needs to be to be able to go from cardinality being exponential in $n$ to it being exponential in $n / \log n$.

-

On one hand, in order to cover all of $A$ with "balls" of radius $\epsilon$, you need to take at least $|A|/|B(\epsilon)|$ points, where $B(r)$ denotes the number of points in $A$ within Hamming distance $r$ of a fixed point in $A$.
On the other hand, suppose you greedily choose balls of radius $\epsilon/2$, so long as these balls are completely disjoint. Certainly you will not choose more than $|A|/|B(\epsilon/2)|$ balls. But having done so, if you double the radius of each ball, you will have covered all of $A$ (by the maximality of the set of balls you started with). So you see you get the right answer up to not worrying about a factor of $2$ on the radius.
@Ryan, thanks for your response. I agree that a volume argument is pretty tight. I had tried it and I guess you end up with a bound of the form $\binom{n}{k} / [ \sum_{i=0}^r \binom{k}{i} \binom{n-k}{i} ]$ on the number of points required for an $r$-covering. I am having some difficulty, evaluating this asymptotically. Some rather rough calculations seems to suggest that you cannot get reduce the number from being exponential in $n$ (say $e^{cn(1+o(1)}$) if you require $k = \gamma n$ and do want $r$ to grow sublienar in $n$. – passerby51 Jun 21 '12 at 23:02
... what I mean is I always seem to get the denominator to grow at most polynomially in $n$, hence the total number to be $e^{c n (1 - o(1)}$. Any tricks to get a $\log n$ drop in the exponent is appreciated. – passerby51 Jun 21 '12 at 23:09