2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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$. $\endgroup$
    – passerby51
    Commented Jun 21, 2012 at 23:02
  • $\begingroup$ ... 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. $\endgroup$
    – passerby51
    Commented Jun 21, 2012 at 23:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .