Timeline for A covering problem for the Hamming cube

4 events

when toggle format	what		by	license	comment
Jun 25, 2012 at 17:18	vote	accept	passerby51
Jun 21, 2012 at 23:09	comment	added	passerby51		... 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.
Jun 21, 2012 at 23:02	comment	added	passerby51		@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$.
Jun 21, 2012 at 20:17	history	answered	Ryan O'Donnell	CC BY-SA 3.0