Timeline for Bicoloring of $\mathbb{N}^2$, avoiding set of patterns, is the maximal limit density rational?
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 8, 2015 at 18:30 | answer | added | Jason Siefken | timeline score: 3 | |
| Sep 10, 2015 at 20:12 | comment | added | Ilya Bogdanov | @Yoav: I was also stuck at this point for a while. Under your conditiions, the large pieces would appear quite often, which contradicts positive density of appearance of $B$. | |
| Sep 10, 2015 at 20:10 | comment | added | Ilya Bogdanov | @Noam: For $\mathbb Z$: From Anthony's comment, the optimal arrangement is periodic, so its density is rational. | |
| Sep 10, 2015 at 20:09 | comment | added | Yoav Kallus | @AnthonyQuas: Is it possible there are "pieces" of increasing density approaching the limit, but none that achieve it; or does iterating your argument inside of the pieces rule this out? | |
| Sep 10, 2015 at 19:50 | comment | added | Noam D. Elkies | I meant, is it obvious that the optimal density in $\bf Z$ is rational? | |
| Sep 10, 2015 at 19:43 | answer | added | Anthony Quas | timeline score: 2 | |
| Sep 10, 2015 at 17:32 | comment | added | Yoav Kallus | @PerAlexandersson: I don't see a significant difference, but for some reason I thought your setting the question on $\mathbb{N}^2$ weakly implied there was one. | |
| Sep 10, 2015 at 17:06 | history | edited | Per Alexandersson | CC BY-SA 3.0 |
updated with answers to question
|
| Sep 10, 2015 at 16:51 | comment | added | Ilya Bogdanov | But, due to the answer for Q2, this one becomes a separate question... | |
| Sep 10, 2015 at 16:50 | comment | added | Per Alexandersson | @IlyaBogdanov: Yes, an irrational supremum would be surprising, so that's why I asked in that way. | |
| Sep 10, 2015 at 16:49 | comment | added | Anthony Quas | @NoamD.Elkies: Yes in 1 dimension it's easy. Take a configuration of maximal density. Find a block $B$ of length $K$ that recurs with positive density. Cut up the original configuration into pieces, each starting with a $B$. Now you can produce a new sequence by cutting out lower densities pieces and replacing them with higher density pieces. | |
| Sep 10, 2015 at 16:49 | comment | added | Per Alexandersson | @YoavKallus: I was thinking about $\mathbb{Z}^2$ first, but I suspect there is no much difference. I would be very interested in an argument explaining a significant difference! | |
| Sep 10, 2015 at 16:43 | comment | added | Ilya Bogdanov | @Yoav: Yes, it may be reached by means of Koenig's lemma. The settings in $\mathbb N^2$ and $\mathbb Z^2$ seem to ve equivalent for the same reason. | |
| Sep 10, 2015 at 16:42 | comment | added | Noam D. Elkies | Is the answer obvious in one dimension? | |
| Sep 10, 2015 at 16:40 | comment | added | Yoav Kallus | Is there a good reason why you use $\mathbb{N}^2$ and not, to me more natural, $\mathbb{Z}^2$? | |
| Sep 10, 2015 at 16:35 | comment | added | Ilya Bogdanov | I think one of Q1 and Q2 was supposed to ask whether the maximal density can be irrational? | |
| Sep 10, 2015 at 16:33 | answer | added | Ilya Bogdanov | timeline score: 4 | |
| Sep 10, 2015 at 16:23 | comment | added | Yoav Kallus | For Q3: I think you can create a coloring that uses $c_1$ in a region around the origin, then uses $c_2$ in a larger region surrounding the first, then uses $c_3$ in an even larger region surrounding the second, and so on. You can pad the interregion space with whitespace wider than the largest pattern. If the sizes of the regions grow fast enough, the limit density should be the limit of the densities of $c_1,c_2,c_3,\ldots$. | |
| Sep 10, 2015 at 16:21 | comment | added | Gerhard Paseman | For finite sets of patterns, you might find some uniformity by assuming they are all kxk patterns for a signifcantly large k, and find out which "infinite strings" are allowed by (say left-right) concatenation. Then find out which strings are compatible by placing certain strings on top or on bottom of other strings. You might be able to show that a periodic density-maximal solution exists with this approach. Gerhard "Is This Related To MineCraft?" Paseman, 2015.09.10 | |
| Sep 10, 2015 at 16:17 | history | edited | Per Alexandersson | CC BY-SA 3.0 |
added 86 characters in body
|
| Sep 10, 2015 at 16:16 | comment | added | Per Alexandersson | A finite set in all of the questions. | |
| Sep 10, 2015 at 16:12 | comment | added | Ilya Bogdanov | In which questions you assume the set of patterns to be finite? Only in Q1, or in all of them? It seems to change everything substantially... | |
| Sep 10, 2015 at 14:53 | history | asked | Per Alexandersson | CC BY-SA 3.0 |