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
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2022 at 18:44 | comment | added | Saúl RM | You are right, I edited that. I wanted to use the "normal" distance but I guess if someone reaches that point of the proof they won't be scared of an $L1$ norm | |
| May 6, 2022 at 18:43 | history | edited | Saúl RM | CC BY-SA 4.0 |
deleted 65 characters in body
|
| May 6, 2022 at 14:40 | comment | added | a3nm | Yeah my point is that you can consider the balls for Manhattan distance, which seems to make more intuitive sense given that the polynomino lengths follow the Manhattan distance. But I agree that this works no matter the distance up to changing the constants. Thanks a lot again for the insights! | |
| May 6, 2022 at 14:38 | comment | added | Saúl RM | The $\pi$ appears because I am considering the balls (in Euclidean norm) of centers $p_i$ and radius $\frac{3k}{2\sqrt{l}}$. Each of the balls intersects the square in area at least $\frac{1}{4}\pi\left(\frac{3k}{2\sqrt{l}}\right)^2$. Some similar argument can be made using taxi distance instead of euclidean one to avoid the $\pi$ | |
| May 6, 2022 at 14:07 | comment | added | a3nm | Thanks! I'm not sure why $\pi$ appears in the lemma proof, is this a typo? For the last point, OK, I see that when $x < y$ then $(x-i)/(y-i) \leq x/y$, by taking the difference, putting to the same denominator, and expanding. OK, this makes sense, thanks a lot for clarifying. About what the growth is, I would also have expected $O(n^2)$ but I agree the more you think about it the less believable it seems. :) | |
| May 6, 2022 at 13:26 | history | edited | Saúl RM | CC BY-SA 4.0 |
added 19 characters in body
|
| May 6, 2022 at 12:30 | comment | added | Saúl RM | In the last part I noticed that you don't need $n$ to be big (just enough so that $\lfloor\frac{\#B}{100}\rfloor>\lfloor\log(n)\rfloor$ so the binomial coefficients are defined). I hope the edits clarify the parts you mention! (Especially the last one). Also, I really wonder if the growth is $O(n^2)$. When I tried to prove it first I was sure it would be $O(n^2)$ but now I'm not so sure | |
| May 6, 2022 at 12:27 | history | edited | Saúl RM | CC BY-SA 4.0 |
added 771 characters in body
|
| May 6, 2022 at 12:15 | history | edited | Saúl RM | CC BY-SA 4.0 |
added 771 characters in body
|
| May 6, 2022 at 11:44 | comment | added | Saúl RM | You are welcome! I will edit the things you mention with a bit more detail. | |
| May 6, 2022 at 9:26 | comment | added | a3nm | (iii) The "Thus $P_{A-a}$" is because, if a polyomino is in $P_{A-a}$, then its intersection with B is a subset of $(A-a) \cap B$. (iv) unfortunately I didn't get the very last step; after the "As when $n$ is big" I don't see why this can derive the bound that follows and gives the contradiction? Other than that I was able to follow the argument at a high level (I didn't check the precise calculations), I think I got the idea. This is very elegant and not at all the kind of techniques I would be used to. Thanks again. :) | |
| May 6, 2022 at 9:24 | comment | added | a3nm | Thanks a lot! Points that confused me: (i) "two of them must be" in the lemma is by the pigeonhole principle on squares of side sqrt(l). (ii) The lemma says that the polyomino contains all points $x_i, y_i$, but you use it to get polyominos $p_C$ whose intersection with the set $B$ is exactly some subset $C$. For this you need to ensure that the polyomino given by the lemma doesn't contain other points from $B$. I guess this is doable without increasing the length too much: none of the neighbors of squares in $B$ are in $B$ by the "even" requirement so you can work around them. | |
| Apr 27, 2022 at 9:35 | history | edited | Saúl RM | CC BY-SA 4.0 |
added 535 characters in body
|
| Apr 26, 2022 at 22:45 | history | answered | Saúl RM | CC BY-SA 4.0 |