Timeline for Puzzle on deleting k bits from binary vectors of length 3k
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2013 at 8:28 | comment | added | Adam P. Goucher | Oh, I see that $H(12,4) = 10$ has already been established in another answer, using almost the same construction. | |
| Sep 27, 2013 at 7:45 | comment | added | Adam P. Goucher | The bound can be slightly improved to $10^{n/12} \approxeq 1.21153^n$ by the following ten-element covering set for $n = 12$: ${00000000, 11111111, 11000011, 00110011, 11001100, 00111100, 00001111, 11110000, 01101001, 10010110}$ We seem to be observing diminishing returns. | |
| Sep 27, 2013 at 3:05 | comment | added | Thomas | Your covering set is actually very useful! I managed to extend it to the general H(2a+3,a) case (just adding digits to the left and right). | |
| Sep 25, 2013 at 5:45 | comment | added | Thomas | I've just done some more work on it, and in the a=2, b=4 case, 101011010 and 110000011 are incompatible with the substrings in the a=2, b=4 case, and are incompatible with each other. Also, 001100110 and 110000011 are incompatible with the a=b=3 case and each other. That is all the cases that need to be covered, the rest are covered by symmetry. Therefore, six is indeed the smallest size of the covering set. I will now work on the case n=12. | |
| Sep 25, 2013 at 5:13 | comment | added | Thomas | I found that 010000111, 011000011, 110000111, 110011100 do not have the substrings mentioned above for a=2, b=3. Also they are incompatible, there is no 6 bit substring of all of them simultaneously. That takes care of the case a=2, b=3. Also, two of the cases can be ruled out by swapping left and right, so that leaves only the a=2, b=4 case and the a=b=3 case. | |
| Sep 25, 2013 at 4:23 | comment | added | Thomas | Woops, actually, there is another case: having the set 000000, 000001, 011111, (1^a)(0^(6-a)), 111111, for a=2, 3, or 4. Although, that case is covered by 101010101, so we're ok. | |
| Sep 25, 2013 at 4:14 | comment | added | Thomas | I am trying to prove that the covering set is optimal for n=9. The way I am doing this is to first consider the forced strings 000000, and 111111. Then the first length 9 strings that don't work are 000001111 and 111110000. This forces two more strings (0^a)(1^(6-a)) and (0^b)1^(6-b) for some a and b at least 2 and at most 4 (because of 000011111 and 111100000). For each of the 6 cases (3 are removed by symmetry), I then check for two other strings which don't have those as a substring and are incompatible with each other. a=b=2 has 010000111 and 101111000, and I am onto the a=2, b=3 case now. | |
| Sep 23, 2013 at 16:20 | comment | added | Simd | If we change the problem so that we delete $n/5$ bits instead of $n/3$ then we can get a simple exponential lower bound. We remove $n/5$ bits from each vector leaving $K$ distinct vectors. So we have $K\binom{n}{n/5}2^{n/5} \geq 2^n$. Therefore $K\geq \left(\frac{2^{1-1/5}}{(5e)^{1/5}}\right)^n > 1.033^n$. Maybe this approach can be improved to work for $n/3$ as well? | |
| Sep 22, 2013 at 21:01 | comment | added | Adam P. Goucher | Indeed, I haven't been able to establish a non-constant lower bound. Any covering set must necessarily contain the words $00\dots 0$ and $11 \dots 1$, and except in the case of $n=3$ these are insufficient. I suspect that we can asymptotically beat $(1 + \epsilon)^n$ for any $\epsilon > 0$. | |
| Sep 22, 2013 at 20:55 | comment | added | Simd | Thank you for this. At this point any lower bound would be interesting. | |
| Sep 22, 2013 at 20:02 | history | answered | Adam P. Goucher | CC BY-SA 3.0 |