Timeline for Puzzle on deleting k bits from binary vectors of length 3k
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2013 at 12:01 | comment | added | Thomas | I think that H(2a+3,a)=6 for all a>=1. We can use a construction of similar type to Goucher's, 0^(a+3), 0^((a+3)/2)1^((a+3)/2), 0^((a+1)/2)110^((a+1)/2), and their complements when a is odd, and 0^(a+3), 0^((a+4)/2)1^((a+2)/2), 0^((a+2)/2)110^(a/2), and their complements when a is even. I will work on the H(2a+4,a) case now, though I think it will be a lot harder. | |
| Sep 26, 2013 at 10:01 | comment | added | Thomas | I have calculated a few values of H(n,j), and I discovered that H(2a+1,a)=2, and H(2a+2,a)=4. I am trying to figure out H(2a+3,a) now. | |
| Sep 25, 2013 at 21:04 | comment | added | Lucia | Our last comments crossed, but at least they are in agreement. Note that the lower bound for $g$ is also convex, so that it is at least plausibly the right answer. | |
| Sep 25, 2013 at 20:48 | comment | added | Lucia | Your $g(x)$ is my $(\log H(n,nx))/n$ as $n$ goes to infinity. The upper bound on $H(n,k)$ noted above I think gives that $g$ is convex, and therefore continuous. | |
| Sep 25, 2013 at 20:47 | comment | added | Will Sawin | The reason I did that is that I want to consider asymptotics as $n$ goes to $\infty$. The most obvious way to do this was to fix $n/k$. But there might be other interesting things to do! Yes, this bound on $H(n,k)$ gives an upper bound on $g$, forcing it to be convex. So currently our curve bounding $g$ is the convex hull of just $3$ points. A search could presumably find more. | |
| Sep 25, 2013 at 20:09 | comment | added | Lucia | I think this is a good idea. But why not just consider $H(n,k)$ which is the number of strings needed if we are allowed to delete $k$ elements from an $n$ element string. As you note the methods of Yury and McKay giive lower bounds for $H(n,k)$. Note that $H(n,k) \le H(a,\ell)H(n-a,k-\ell)$ and so Goucher's example gives non-trivial upper bounds. | |
| Sep 25, 2013 at 19:36 | history | answered | Will Sawin | CC BY-SA 3.0 |