Timeline for What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2022 at 9:56 | comment | added | a3nm | I see, this makes sense, thanks a lot for explaining. And thanks for clarifying that the connection to sparse rulers is only for k=2 -- I don't know if there is an analogous notion for all k-tuples with maximal separation $\leq n$. (Here as in your post "maximal separation" is the maximal total span, i.e., the difference between the min and max) | |
| Apr 25, 2022 at 7:17 | comment | added | AnttiP | @a3nm Yes, it seems that for $k=2$ the sparse rulers are the optimal embedding. But anyways, the bound can be derived from the fact that for a fixed $k$, ${n \choose k}$ is a polynomial of degree $k$. Thus $\frac{{n \choose k}}{n}$ is approximately a polynomial of degree $k-1$. Now we want to find some function $f(n)$ so that ${f(n) \choose k}$ grows like a polynomial of degree $k-1$. This means that $f(n)$ has to grow like a polynomial of degree ${1-\frac{1}{k}}$ since if you multiply that by $k$ you get the desired growth rate of $k-1$ | |
| Apr 24, 2022 at 15:10 | comment | added | a3nm | Thanks for the proof! this looks convincing to me except that I don't get how $x≈n^{1−1/k}$ is derived from the previous inequality (which property of the binomial coefficient do you use for this?). Other than that, the one-dimensional non-connected case looks already interesting, it looks like the problem of sparse rulers which is already studied en.wikipedia.org/wiki/Sparse_ruler (and for which we may get more precise asymptotics) | |
| S Apr 23, 2022 at 15:52 | review | First answers | |||
| Apr 23, 2022 at 17:15 | |||||
| S Apr 23, 2022 at 15:52 | history | answered | AnttiP | CC BY-SA 4.0 |