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



A covering problem for the Hamming cube
If you're not concerned with constant factors on the covering radius (and it looks like you're not), then you should be able to get the right answer on volume arguments alone.


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.


For more details, I think the keywords to search for are "covering codes" as well as "Johnson scheme" (the latter being the coding theory terminology for considering all binary strings of a fixed Hamming weight).


