Timeline for Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 16, 2012 at 20:45 | comment | added | Seva | @Ilya: right, this is what you get if you are not willing to sacrifice lower-order terms. My expression assumes a very marginal loss of accuracy, but a gain in clarity. (Just think of replacing $k-1$ with $k$ in the numerator of your fraction, and $n-k+1$ with $n$ in its denominator.) | |
| Jan 16, 2012 at 13:20 | answer | added | Ilya Bogdanov | timeline score: 1 | |
| Jan 16, 2012 at 12:10 | comment | added | Ilya Bogdanov | It seems that a duoble-counting argument mentioned at the beginning leads to a bit different estimate, namely $\frac{Nn-2^{n-1}(k-1)}{n-k+1}$. | |
| Dec 26, 2011 at 17:01 | comment | added | Jyrki Lahtonen | Andrew Klapper has worked on multi-covering problems (see cs.uky.edu/~klapper/multicov.html), but I don't know if the problem is too well-studied. What I was getting at with my other remark is that in coding theory balls are often called spheres. I know that this is bit against the standard of the rest of math :-) | |
| Dec 23, 2011 at 8:15 | comment | added | Seva | @Jyrki: yes, the spheres are hollow; otherwise I would say Hamming balls. I am not sure of what exactly you mean by the problem of "bounding the size of multi-covering codes". It is quite possible that my question is related to some known coding-theory problems (and hence one of the tags); practically, I don't know of any such problem. | |
| Dec 22, 2011 at 19:17 | comment | added | Jyrki Lahtonen | Are your spheres hollow? A bit non-standard, if you ask me. For example in the sphere packing bound of coding theory, the spheres consist of all the points at a distance at most the radius from the center. OTOH using the surface only may make the problem more interesting! I'm not an expert on variants of covering codes, but is your problem not a variant of bounding the size of multi-covering codes? Some people have worked on those. | |
| Dec 16, 2011 at 15:47 | history | edited | Seva | CC BY-SA 3.0 |
added 1862 characters in body; edited title
|
| Dec 7, 2011 at 9:04 | history | edited | Seva | CC BY-SA 3.0 |
added 4 characters in body
|
| Dec 7, 2011 at 8:45 | history | asked | Seva | CC BY-SA 3.0 |