Polymath16, seventeenth thread: Declaring victory

Posted on by Dustin G. Mixon

This is the seventeenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

At this point, we are finalizing a draft of a paper by D.H.J. Polymath. Like Aubrey’s original paper, this will be submitted for publication in Geombinatorics.

This post concludes the Polymath16 project. Of course, we anticipate that folks will continue to make progress on this problem on their own. If you’d like to update the Polymath16 community about your progress, feel free to comment on this post.

I asked Aubrey to offer a few words to reflect on our project:

The Polymath 16 project recently celebrated 1000 days of age. It had two main initial goals: to find 5-chromatic unit-distance graphs in the plane with fewer vertices than the 1581-vertex example that I had published in early 2018, and to identify proofs of \mathrm{CNP} \geq 5 that required less computer assistance than my construction needed (ideally none at all). Many ancillary goals were also mentioned at the outset.

By all standards, the project has been an immense success. The record for the smallest graph was progressively improved, including several times by Marijn Heule, and the present record is 509, achieved by Jaan Parts. Jaan also has the distinction of cracking the other main challenge: a few months ago he unveiled a proof of \mathrm{CNP} \geq 5 that he described only as “human-verifiable,” but that is too modest, because his method is certainly usable to create a proof from scratch without any computational assistance in no more than a week or two (for someone sufficiently diligent and non-error-prone!). Jaan has, in fact, been the most prolific of the contributors to the project over the years, having made numerous other contributions, some on his own and some in Polymath-esque rapid-fire collaboration with others.

Perhaps the most satisfying aspect of the project, to me, is its quite remarkable success in attracting amateur mathematicians like myself (of whom Jaan is one). At least half a dozen of us have been significant contributors over these three years, working side by side with numerous professionals including Terry Tao himself.

Given the diversity of Hadwiger-Nelson-type problems that we have investigated, it was always implausible that all our results would be gathered into a single publication. This was especially the case in view of the proportion (more than half) of our advances that were achieved by a single individual with little or no collaboration at the blog, and which were thus more properly published under that person’s name alone. However, one clear exception emerged: the set of questions concerning bounds on the sizes of circular disks and infinite strips of different chromatic number. It has turned out that at least five of us made major contributions to one or more such question, so this was the natural focus of what has just become the first (and, we must now anticipate, only) paper arising from Polymath 16 whose sole listed author is the canonical, fictional D.H.J. Polymath. Like several of the other reports, and like my original proof of \mathrm{CNP} \geq 5, it will appear in the journal Geombinatorics, whose editor-in-chief Alexander Soifer was, via his timeless 2009 book, responsible for inspiring me to work on the Hadwiger-Nelson problem in the first place.

The energy that Polymath 16 has evoked will not dissipate easily. We plan to leave this blog open for further discussions and reports – which will surely emerge as time passes, since many fascinating Hadwiger-Nelson-type questions remain wide open in spite of our efforts. Let us hope that the merry band who have progressed this far will continue to grow and to make yet further inroads into this truly captivating family of questions.

355 thoughts on “Polymath16, seventeenth thread: Declaring victory”

    1. Yes, that’s it, and then here is the new version reposted from the previous thread: Call a coloring scalable, if there is some small positive number eps such that the coloring remains unit-distance-free after you enlarge/shrink some of the tiles by at most eps. This is equivalent to the fact that the coloring avoids all distances in [1-eps,1+eps]. The classic hexagonal tiling of the plane is scalable, but the new 7-coloring of large enough spheres by Tom Sirgedas is not. Indeed, a scalable coloring needs at least 8 colors, as shown by Peter Agoston.

      Anyhow, suppose there is a scalable coloring for the width 1 strip. It follows by some continuity argument that there is a point X such that in its arbitrarily small vicinity you can find at least 3 colors; let these points be X1,X2,X3. Take an equilateral unit triangle X,Y,Z in the strip. Then X1,X2,X3,Y,Z need 5 colors.

      By wording you mean as it could go to the paper?

      Reply

      1. Thanks. Yes, I meant as it could go in the paper. But first let’s see if we can extend the proof to unscaleable tilings. I’m initially imagining something about the tiles adjoining the unit-radius circles centred on X, Y and Z, but I don’t have a fully-formed idea yet.

      2. The reason why I don’t think that some trick like Tom’s for the sphere could work here, is that he uses more than three tiles meeting in a vertex. So as a starting point, can we rule this out, that is, prove that in each vertex at most 3 tiles meet?

      3. Oooh, that’s a very good point. Ingenious. I bet we can indeed get something from there.

        More generally, though, and whether or not we can do that, I’m now thinking that actually we should not add this material to the paper after all, because it will more appropriately be the starting-point of a whole new topic that is likely to become another paper (maybe a DHJ Polymath one, maybe not). Before I came along there was a nice sequence for the lower bound on the CNP, i.e. 4 unconditionally, 5 if measurable, 6 if tile-based, 7 if scaleable-non-Siamese-tile-based. I am still unclear as to quite what distinguishes measurable from tile-based, but regardless, it seems to me that all the questions we are addressing in the current paper can be extended/adapted to questions involving these constraints on the type of colouring. What do you think?

      4. I’ve realized that ruling out 4 tiles meeting at a point is hard because one of the four tiles might be very tiny. In this case we need to show that it can be absorbed by its neighbors somehow. But I agree with you that it might be simpler to omit it from the paper, or just mention it (without proof) that for scalable tilings this holds.

  2. Separately: in the course of putting the paper together I stumbled on a very nice recent paper from our friend Marijn Heule and colleagues:

    Click to access lpar20-coloring.pdf

    One minor feature of it is that they thought the value of 9/Sqrt[28] for the 5-strip was original with them; I have let Marijn know that we had already discussed it, but clearly the discoveries were independent so I have added a reference to their paper. (In fact, it looks like he was just unlucky: he does cite a post (tenth thread, post 5488) from Jaan that gives the best numbers for k-strips, but unfortunately Jaan seems to have miscalculated the width of the 5-strip in that post so Marijn thought his design was a genuine improvement.)

    But the main reason I’m highlighting the paper now is that the method discussed in their paper is (of course) SAT-based. They reached the same general finding as us, namely that the simplistic approach of dividing the region into monochromatic cells can only discover scaleable tilings. They then took a different approach that the one I proposed back when we were looking at this: they stuck with looking at pairs of cells, just that they made the cells not cover the entire region. (Recall that my approach involved looking only at grid points, but looking at triples of them in which two of the three are neighbours in the grid.) So I told Marijn about my approach and he likes it and will put it on his list of future directions.

    But that got me thinking: Tom, you used SAT to find the tiling that became the record-breaking 5-disk, and that tiling is certainly not scaleable. Did we just get lucky somehow, or was your approach different from the simplistic one with which others have failed to find unscaleable tilings?

    Reply

    1. Wow, you can embed a pdf like that? Cool!

      Anyhow, I think that is a serious drawback of a long polymath project – others might publish the results. If I have seen well in their table 1, they don’t have anything better than in the D. H. J. Polymath paper. BTW, the initials shouldn’t be D. H. J., as that stands for Density Hales-Jewett. On this paper it should be C. N. P. or H. N. or something like that, no?

      Reply

      1. I didn’t know about the embedding either – I just included the link. Now we know!

        As for the initials, you are righter than you know: Polymath1 solved the Density Hales-Jewett problem, and that’s why those initials were chosen. But they have been retained for all subsequent Polymath papers, so we should continue the tradition.

    2. Re “But that got me thinking: Tom, you used SAT to find the tiling that became the record-breaking 5-disk, and that tiling is certainly not scaleable.”:

      I have used SAT to generate graphs on a grid. But the 5-disk was found with a different approach (building up a planar graph).

      Reply

  3. @Dustin, it would be nice to add links to threads 16 and 17 from the Polymath16 start page.

    I keep looking for a 5-chromatic graph of minimum radius. The current result is 1.05 and I’ll get back to the details a little later when I hit the wall.
    Here I would like to note that such a wall is very likely, that is, the series of minimum radii for a sequence of graphs built according to some chosen scheme may not converge to the actual value of the minimum radius. And this must be borne in mind saying that “the bound could be improved with more intensive calculations”. This is not necessarily the case.
    I have done some additional research on a tricolor disc for which we know the exact radius. Gradually adding new rotations by next multiple of \arcsin\frac{1}{\sqrt{12}}, and Minkowski sums, at some point I get a disk of diameter 1.25, but no further increase of the graph allows me to get a disk of diameter 1.24.

    Reply

    2. Hey Jaan – sorry for the slow reply. Thank you; I agree. I will change the wording to indicate that we realise that there will be an asymptotic limit to what radius can be reached and that it may be quite close to what we already HAVE reached, rather than being only the lower bound that we have demonstrated with tilings.

      When you’re ready, please write down exactly which small graphs you are combining as a Minkowski sum before you start deleting vertices. Also please do that for your strip of width 1.4 – I tried to understand your description but I’m not sure I do.

      Everyone: I think I have implemented all other changes that have been suggested. Please re-read the latest version with a strong microscope and let me know of any further comments.

      Reply

      1. In the abstract, the first quotation mark is the bad way, in latex it should be “.

        I see that you wrote “Since tilings are merely a subset of all possible colorings, the bounds thereby obtained apply to the chromatic number in the general case” The trouble is that this only holds for bounds from one direction. So I mean that if we show that the tile-chromatic number of a strip is at least 5, that does not imply that the chromatic number is also at least 5. I would completely remove these last two sentences from the intro, or would just write something like in our constructions, all colorings are tile-based. Wouldn’t that be more accurate?

      2. Thanks Domotor. I’m not seeing any latex when I mouseover your ” but no problem, I have gon the low-tech route and just removed the quotes entirely.

        For the other sentence, hm, I’m trying to remember why I put it in! (And why.) I’m sure it was at someone’s suggestion but I can’t fnd it. I think it is strictly OK, since “thereby” refers to tilings, but I agree it could be confusing so I think I’ll delete it.

    3. I propose the following compact notation for graphs formed by Minkowski sums and rotations. (I mentioned it earlier, here I will repeat it.)
      The graph is denoted as nGm, where G is some base graph, n is the number of identical terms Gm in the Minkowski sum, Gm is a graph composed of 2m-1 copies of the graph G rotated around the center by angles \frac{-m\dots m}{2}\arccos\frac56.
      In most cases, the graph G is a 7-vertex wheel graph H (hexagon), or a 13-vertex 2-wheel graph D (dodecagon or double-hexagon), where the wheels are rotated around the common center by an angle \arccos\frac78.
      The “+” sign indicates the Minkowski sum. The union of graphs is denoted by “\cup” or “|“. If the constraint of the Euclidean radius or width of the graph is used, then the trimming parameters are indicated explicitly in brackets or separated by commas, for example, 4D2 (r =1.1). So, in most cases, one can avoid LaTeX formulas.
      For example, the 31-vertex Aubrey’s unit radius 5-wheel graph V can be written as 1H2 or just H2, the graph V\oplus V\oplus H as 2H2+H0, the 6937-vertex Tamas’s graph V_A\oplus V_A\oplus V_A as 3D1.
      The system of notation can be extended, but in our case these extensions are not needed, since we are not trying to minimize the order of the graph, and we only need to outline its main structure.

      Reply

      1. Many thanks Jaan. I’m happy with this notation – I think it is clear, and it’s concise enough for the paper. Please remind me what graph you used for the strip of width 1.4 – was it one of this form?

      4. Jaan, I am still not completely understanding. How many 4H4 graphs did you combine in your 5-chromatic graph, and what where the coordinates of all their mono pairs? I understand that one of the 4H4 graphs had a mono pair at 0,0 and 8/3,0 but I can’t see any mention of where the other 4H4 graphs’ mono pairs are. Please explain.

      5. I’m sorry the explanation was not clear enough. But I thought the rest was obvious. Everything is exactly the same as in Figures 1 and 2 in the preparing article on disks and stripes. On the basis of mono-pairs, a long chain is constructed, closing by an unit-distance edge, which leads to the need of an additional color.
        In the case of stripes, we have a rectangle of some width containing a mono pair, that is, two points of rectangle have the same color in a 4-coloring. Next, we connect many copies of these rectangles in a chain, so that they are located inside of slightly wider strip, while simultaneously connecting the points of mono-pairs. On the way to one side, the rectangles wiggle a little, in the opposite direction, they do not, which allows us to close the chain of mono-pairs by an unit-distance edge. You can notice that it doesn’t matter at all how the mono-pair itself is located inside the rectangle; we can always make a suitable chain.
        In the case of a disk, the situation is similar. It is possible to organize the same chain of mono-pairs, placed on similar disks and closed by an unit-distance edge. In most cases, it also doesn’t matter how the mono-pair is positioned on the disc. The resulting disc will only have a slightly larger diameter (as in Figure 7 in the article). In the case of a mono-pair 8/9 with one of the vertices in the center of the disk, a long chain is not required: it is enough to take two mono-pairs with a common center and connect them with an edge. This does not change the diameter of the resulting disc at all.
        Did I add some clarity?

      6. Thanks Jaan. Concerning the strip, yes, you have totally explained and I agree, and I will start to write the corresponding text in the paper.

        Concerning the disk, though, I am still confused. The graphs in Figure 7 do not seem to be relevant, because there is no mono-pair there. When you say “two mono-pairs with a common centre”. I assume you do not mean a common midpoint, because the midpoint is not (necessarily) a vertex with the same colour as the mono-pairs. (Or is it? Does your graph actually contain a mono-triple of three points in a line?) I can see how to arrange a long chain without any increase in radius if the distance of the mono-pair is greater than 1, because then we can arrange that the midpoints of all the mono-pairs are very close together (and it doesn’t matter thether those midpoints are also vertices). But when the distance of the mono-pair, call if x, is less than 1 it seems that the disk will need to have a diameter 1-x greater than the disk that contains the single mono-pair-containing graph.

      7. Let’s try so:
        1. My subgraph with an 8/9-mono-pair is located on a disk of unit radius so that the first point of the mono-pair coincides with the center of the disk, the second is on a circle of radius 8/9 from the center of the disk. It suffices to take two copies of this subgraph with a common center.
        2. Yes, if a mono-pair has length less than 1, then some restrictions may arise in the location of the vertices of the mono-pair. Namely, the case when both vertices of a mono-pair are located at a distance less than 0.5 from the center of the disk does not suit us. In all other cases, we can create the required chain.

      8. I’m still not getting it. I have drawn a picture:

        In the left-hand picture, the black line is length 8/9 and there are vertices at its ends that are a mono-pair in 4H4. I am assuming that these are the vertices at (-4/9,0) and (4/9,0). The blue disk is the smallest size that contains a subgraph of 4H4 that still keeps that pair of vertices mono.

        In the middle picture, I am showing my understanding of your construction. There are two copies of 4H4, and the ends of the black lines again denote the mono-pairs. The red line is length 1 and gives us a 5-chromatic graph. Then the blue disk is the smallest size that keeps both pairs of vertices mono and thus preserves non-4-colorability. The ends of the red line are closer to the edge ofthe disk than they are in the left-hand picture, because we can expect that there will be savings there as a result of having so much spare area on the other side of the disk. But the disk will still be much larger than the left-hand disk.

        In the right-hand picture, there are three copies of the left-hand picture and nothing else. Again the red line is length 1. The entire thing fits inside the green circle, which is still larger than the left-hand disk but much smaller than the right-hand one.

        What am I getting wrong?

      9. It seems that you are implicitly assuming that the diameter of the disc on which the mono-pair can be placed will be smaller if this mono-pair is placed symmetrically about the center of the disc. This intuition may not work on small radius discs. That is, your assumption may be wrong.
        My working hypothesis is this: any 4-colored graph of the form nHm containing a mono-pair must contain pairs of vertices with distance 2. (Regardless of where exactly the mono-pair is located on the disk.) So far, all the data confirm this hypothesis. But these data are not enough to assert unequivocally that it is true law.

      10. I’m very sorry if I’m being dumb, but I’m even more confused now. You are essentially correct about my assumption; I can believe that the smallest disk does not have the midpoint of the mono-pair at the centre of the disk, but I think it is VERY unlikely that the smallest disk has one of the mono-pair at the centre of the disk. But I am totally unable to understand the relationship between my hypothesis and yours. What is the relevance of the presence of vertices 2 apart? Do you mean that one of the two mono-pairs must beat the midpoint of a pair of vertices that are 2 apart?

      11. Don’t worry, it’s okay. My hypothesis (here it does not matter whether it is correct or not) says that if we want to get some mono-pair by 4-coloring of an arbitrary graph obtained by trimming some graph of the form nHm, then this trimmed graph must have vertices (which are not the vertices of a mono-pair in the general case) located at a distance of 2 from each other. In other words, it is impossible to obtain a mono pair on a disk with a diameter less than 2 by trimming the graph nHm. (So far I have not succeeded.) Therefore, it does not matter where the vertices of mono-pair are located.
        It’s only hypothesis, and we need some counterexample to break it. If you have any ideas on how to get a graph with a mono-pair on a disk of radius less than 1, suggest an appropriate construction, I will check it. And I have not checked all my constructions yet. It’s a very long process.

      12. Ah,OK… so you are reporting two things:

        1) you have found a subgraph of 4H4 that has a mono-pair at (0,0) and (8/9,0) and that fits inside a disk of radius exactly 1 centred at (0,0)

        2) you have been unable to find a subgraph of 4H4 that has a mono-pair at (-4/9,0) and (4/9,0) and that fits inside a disk of radius less than 1 centred at (0,0)

        Right?

      13. 1) It’s right
        2) I haven’t tried it yet, I plan to, but I tried other things (btw, 4H4 does not contain vertices with coordinates (+-4/9, 0), but it’s not so important)

      14. Thanks! So we can restate my (2) as:

        2) you have been unable to find a subgraph of 4H4 that has a mono-pair at (0,0) and (8/9,0) and that fits inside a disk of radius less than 1 centred at (x,0) with x greater than 0, in particular with x = 4/9.

        That is what I was trying to ask from the beginning. Sorry for being confusing and confused!

    4. As for the number of vertices of some large graph nGm, in some cases this value is irrelevant, and it is difficult to find it, since the count is in the millions. One can define it too, but I’ll have to develop a more efficient algorithm.
      I noticed that if, in the end, we need to limit the Euclidean radius of the graph, then similar results are obtained if we introduce a trimming when calculating each next Minkowski sum, instead of trimming the graph after calculating all the sums. The number of vertices does not differ much, but the chromatic number of the graph remains the same. One can trim this graph further. As a result, the exact order of the final graph depends on how it was obtained.

      Now about the actual results. I started with graphs of the form nDm. So, graph 3D2 remains 5-chromatic at radius r =1.25 (11725 vertices, 52509 edges), graph 4D2 – at radius 1.09 (75793 vertices, 424995 edges), graph 4D3 – at radius 1.04 (311509 vertices, 1602019 edges). Graph 4D4 at radius 1.04 already has 915745 vertices, and I started calculating its edges, which in the existing ineffective version of my program would take several days.
      But then I remembered that we can follow Jannis’s way and form two mono-pairs of length 8/9, connected by an edge (by the way, such a graph can be embedded in \mathbb Q [\sqrt3, \sqrt7, \sqrt{11}]). That is, it is sufficient to consider graphs of the form nHm. Thus, a 5-chromatic pair of 4H4 graphs can be located on a disk with radius 1.00 (31171 vertices, 180942 edges). I need some more time to try to move forward.

      Reply

      1. Woah, that’s a huge jump from the nDm ones!

        I have a suggestion, which is somewhat inspired by Ulrich’s graph and the fact that 8/9 is not much less than 1. If instead of two graphs of the nHm form you use three, you can arrange the mono-pairs at the corners of a parallelogram with longer diagonal 1. Since the nHm graphs are densest in the centre, and since the centres of the three components will be much closer together than the centres of the two components in the arrangement you’ve looked at, I’m thinking there is a good chance of a further reduction.

      2. Until I understood your proposal. But yes, we can increase the number of mono-pairs. We can use any 4-color mono-pair located on the disk, however we like. And then we take many copies of such a pair, gradually turning the disk back and forth around the center (as in your initial version of the proof), until we get the ends at a unit distance.
        By the way, we already had such a pair (two years ago), 4H3, d =8/\sqrt{27}, with a radius r=1.02:
        https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23272
        I’m not yet sure if the asymmetric positioning of the mono pair relative to the disc will help. The first day of tests gave nothing.

      3. My suggestion is not based on my initial version of the proof, it is based on Ulrich’s proof. If we take a parallelogram with two opposite edges of length 8/9 and with diagonals of lengths 8/9 and 1, the other edges of the parallelogram will be quite short. Thus, we can place the mono-pairs of three copies of 4H4 on those three 8/9 lengths, giving a 5-chromatic graph, and the centres of those three copies will be quite close together, so the overall graph will have a better clustering of its vertices into a small disk than a graph in which two copies of 4H4 are placed on a triangle of edges 8/9, 8/9 and 1 (which is what you tried already). Am I clear?

      4. Also – that graph with radius 1.02 is just the 4-chromatic one with the mono pair, right? Not the combination of 2 or more such graphs to make the 5-chromatic one. I would not expect that graph to be a good starting-point for my suggestion, because the mono-pair distance is not very close to 1.

      5. If I understand correctly, this does not help yet. The mono-pair I have tried has one of the vertices exactly in the center (0, 0). The other end has coordinates (8/9, 0). So I don’t lose anything at all by rotating one half of the 5-chromatic graph relative to the other. And in the case of a parallelogram, there will be losses.

      6. Your initial rotation method allows you to take (without losses) a mono pair, the vertices of which are located at any points of the disk.

      8. I must be being dumb but I don’t understand your construction. You seem to be saying that if a 4-chromatic graph with a mono-pair fits into a disk of radius r, then we can use copies of that graph to make a 5-chromatic graph within a disk also of radius r, or at least r+epsilon. How are you doing that?

      9. Ah wait, are you saying you put the both-mono-pairs vertex at 0,0 and then you also centre the disk at 0,0? Surely that is far less good than centring the disk somewhere inside the triangle of mono-pair vertices?

      10. One of the vertices of each mono-pair coincides with the center of the disk. This is the best construction so far. Everything looks as if a 5-chromatic graph based on subgraphs nHm must contain wheel-graphs H. Let’s wait a few days. Maybe not.

      12. Hm… it seems very wrong to have a construction in which most of the vertices are on one side of the disc. I feel really optimistic about what will happen if you try my tri-4H4 construction and put the origin at the centre of the parallelogram.

      13. Oh, I think I figured out how you represent my graph. No, each of its 4H4-subgraphs containing a 4-color mono-pair is symmetric about the center, and the disk is densely occupied by vertices. I will try to cut off the disk boundary on the side, but I don’t think it will be possible to cut off a significant part without damaging the mono-pair. An image of a 4H4-subgraph looks like this:
        https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23279

      14. There is little progress in the width of the 5-chromatic strip: 1.35 on a mono-pair 8/3 (a graph with 78670 vertices).

      15. Thanks Jaan. Is this still a subgraph of 4H4? What was the y-coordinate range? Did you delete any vertices other than those outside that range (e.g. those of low degree) like before?

      16. Here I decided to try a symmetrical construction. I don’t know if it helps or not. I have united two 4H4 graphs, placed at a distance 2/3 (vertices 5 and 9), taking a pair 8/3 (vertices 1 and 13). Formally, this graph is larger than 4H4. Width 1.35 is obtained for y\in[-0.48,0.87]. Implicitly, as a framework, I mean a construction like the one shown in the figure. Don’t ask me why I think it should work. If this construction works strictly, then we can get the width \frac{11\sqrt3-\sqrt{11}}{12}\approx 1.31133.

      17. Thanks! Yeah, these widths are always improvable just by checking for the extremal y-coordinates of a vertex, which will never be the decimal approximation, so we should definitely state the range in that way rather than as decimals. Keep it up!

      18. The current 5-chromatic strip width is 1.32 (-0.45\le y\le 0.87). This time I have placed six copies of 4H4 at the vertices 1, 4, 5, 9, 10, 13 of the framework graph shown earlier. Thus, the resulting graph with the mono-pair 8/3 is a subgraph of the graph 6H4. Adding new copies of 4H4 actually works. At least, this speeds up computations, and possibly reduces the width of the strip.
        In addition, I repeated the calculations with similar six copies of the graphs 4H2 and 4H3, and made sure that they are not enough for such a strip (a SAT solution is obtained).

      20. Woah, that has broken your barrier at -(Sqrt[11]-4Sqrt[3])/12 hasn’t it? (Your framework vertices 14 and 15.) I was about to include that conjecture in the text!

      22. Yes, the conjecture does not work in the sense that it does not limit the lower value of y, nor in the sense that it does not reach the upper value \frac{\sqrt3}{ 2} (it is still \frac{11\sqrt{11}-3\sqrt{3}}{36}). Let’s look further.
        Btw, for the disk I cannot obtain a radius less than 1 on single 4H4 graph for mono-pairs with coordinates (\pm4/9,0), as well as (-2/9,0) and (6/9,0). Even a radius of 1 is not obtained. The calculations were interrupted a week after the start (the result is indetermined).

      23. Thanks for the update on the disk, and for the exact value of the upper bound. What is the exact value for the lower bound at the moment?

      25. Thanks. Yes, absolutely – I’m just making sure to keep up with you. Please continue to include the exact values for both bounds in further updates.

  4. Since we are well advanced in tiling a sphere of large radius (as Tom showed, 7 colors are enough), I propose to consider other flat 2-surfaces and 2-manifolds (also large enough): a cylinder, a torus, a Mobius strip, a Klein bottle, projective plane. If, in my opinion, there are no difficulties with the first two ones, and 7 colors are enough, then for the next three the problem at first glance looks nontrivial. According to preliminary estimates, 8 colors are enough for a Mobius strip and a Klein bottle. But can 7 be used? And everything is not easy with the projective plane. How many colors are required here?

    Reply

    1. I think the standard 7-color honeycomb tiling (Isbell tiling) works for all of these, because you can use the trick in the above image to swap two colors in the honeycomb pattern.

      The cylinder and torus just work immediately. (No swapping is needed).

      With 9 such swaps you can reverse the honeycomb pattern, which allows the Mobius strip and Klein bottle to be tiled.

      The projective plane is trickier. I think 9 vertical and 9 horizontal seams would work, but the seam pattern shown in the image can’t be rotated 90 degrees (this is easy to fix, I think). Also, each vertical and horizontal seam will intersect which causes complications. So, the entire projective plane should be 7-colorable, if you ignore 81 small regions.

      Reply

      1. Great! But I didn’t understand with the projective plane yet. Hope you can give a more detailed solution.

      2. Hmm, nevermind about the projective plane. I don’t really understand it.

        The above image shows how the Klein bottle can work. I expected to be able to do the same thing for the projective plane, using both a horizontal seam and vertical seam.

        But, in a projective plane, if you are in the top-left rectangle, and move left, you end up in the bottom-right. Also, if you move up instead, you end up in the bottom-right. But are you horizontally or vertically flipped? It depends on how which way you moved.

        Maybe the leftward movement actually brings you to the “opposite side” (meaning that the “fundamental polygon” has a front and back???).

      3. I have similar difficulties in understanding the projective plane. But, I think, it is quite correct to approach the coloring problem as follows.
        First, we tile the perimeter of the fundamental polygon according to the rules in force on this perimeter. For example, if the top side of the fundamental polygon sequentially takes the colors 1, 2, 3, 4, 5, 6, 7, 1 from left to right, then the bottom edge takes the same colors from right to left. If the left side takes the colors 1, A, B, C, D, E, 1 from top to bottom, then the right side takes the same colors from bottom to top.
        Next, we need to tile the second rows from the top, bottom, left and right. Here we have to look at the tiles of the second row, located on the opposite side. Let’s say in the second row of tiles from the top we have a tile of color P under tiles 3 and 4. In a honeycomb tiling, the tiles with this color P will be prohibited in the second row from the bottom between tiles 2…5.
        Next we can color the rest of the inner area of the fundamental polygon, almost as we wish.
        In my opinion, it is not necessary to immediately try to get the minimum number of colors. You can take, say, 10 or 15 colors, and try to tile the projective plane somehow.

      4. I thought about this some more. Starting with a circular strip or mobius strip, and attaching A to A’ and B to B’ you can get Klein bottles or a projective plane (see image). For the projective plane case, the mobius edge is attached to itself, but in the opposite orientation (unlike in the Klein bottle case). This means that we’ll have two “fixed points” on the mobius edge that are attached to themselves. We label one of these points A, and a nearby edge point B.

        We might have some idea of what distance means for the mobius strip, but after gluing the edge together, this notion of distance seems like nonsense. We can “flatten” the space near A, but this warps distances.

        I was considering how to draw a honeycomb pattern into the primitive polygon (a square), but this seems a bit nonsensical now. Just like drawing a single honeycomb pattern on a flattened sphere doesn’t work. You can’t even tile a sphere with just hexagons.

        The primitive polygon idea makes it tempting to think that the projective plane is flat everywhere, and only gets funky at the edges. But, more naturally it’s curved everywhere (like a sphere). The sphere has a nice embedding in 3-d and a natural distance formula. Do we need an embedding for the projective plane to have a sensible distance formula?

        In the end, I suppose you could just color the primitive polygon, and have some definition of what points are a unit distance apart. But, just like the sphere has a radius “parameter”, I think the projective plane will have a lot of parameters. Like, let’s deform the sphere into the shape of a cat. What does coloring the surface of a cat mean? We can embed the cat in 3-d space and use Euclidean distance, but the coloring will depend on the exact embedding.

      5. I’m not totally sure how my reasoning applies to the Klein bottle. Maybe because it’s a “flat” surface (??), the euclidean distance formula on the primitive polygon just works.

      6. In my opinion, in our case it is not necessary to try to embed the Moebius strip or the projective plane into 3- or more-dimensional space. Why not just take it as a plane? More precisely, as a fundamental rectangle with correspondingly identified sides, and with the usual Euclidean metric. Coloring such a fundamental rectangle is quite a sensible task.
        As for the sphere, from a certain point of view it is more complicated than the projective plane: it must have a nonzero curvature in order to have the proper coloring. If we take the representation of a sphere in the form of a flat fundamental polygon, then in accordance with the rule for identifying sides, there is always a pair of vertices at a unit distance that have the same color.

      7. Hmm, yeah, you just get weird behavior near the corners. A unit circle circle near the corner is strange.

        Here’s a simple 9-coloring I think. Same color tiles are always separated by at least 2 rows or columns.

  5. OK everyone, I now have a deadline from Soifer for the final submission, namely March 15th. The latest draft at the dropbox includes what I think is a tolerable writeup of the 5-chromatic graphs in the strip and the disc, but I am on standby to update those if Jaan generates any improvements in the next ten days. Any further suggestions for edits of any part of the manuscript, please post them here ASAP.

    Reply

    1. It looks like I bumped into the wall with stripes. The current result is w=(7\sqrt3+\sqrt{11})/12\approx 1.28675, y\in[-(\sqrt3+\sqrt{11})/12,\sqrt3/2]. I connected 17 graphs 4H4 (not all central vertices are shown in the figure), I also tried to combine 6 graphs 4H5, but I still couldn’t overcome the lower threshold y = -0.42. Inside the interval y\in-0.43\ldots-0.42, I checked all the available thresholds for y.
      Note that at the moment, a modified version of my conjecture that the minimum width is determined by the vertices of the 2H2 graph is still working. In the modified version, the framework has the form shown in the figure below. The angles 4-1-6 and 5-1-7 between the edges at vertex 1 are equal.
      Next, for stripes, I plan to do a little work on simplifying the graph by reducing the number of used copies of the 4H4 graph. Now it is 6 copies at vertices 1, 5, 7, 10, 12, 17 with a mono-pair 1-17 with a distance 8/3 (141039 vertices, 1130696 edges). I also want to try playing with the upper threshold for y, but previous research suggests that there is little chance here.
      I also repeat my other conjecture in a slightly modified form: each 4-chromatic subgraph of a graph of the form nHm containing a mono-pair must also contain copies of a 5-vertex half-wheel graph obtained from the wheel graph by discarding two adjacent non-central vertices.

      Reply

      1. Thanks Jaan! Please give us the coordinates of all 17 centres (in quartet notation if you like). I see 17 vertices in the figure, but you say that not all centres are shown – ? Also you seem to say later on that you are only using the original six copies – I am confused.

      2. A strip of the specified width can be obtained with both 17 and 6 copies of 4H4. I tried more copies to increase the likelihood of getting a narrower strip.

      4. The fact that the figure also has 17 vertices is a coincidence. I placed the centers of 17 copies of 4H4 on lines 5-12 and 1-17 of the figure with a step 1/3.

      5. Recent results show that the upper threshold of y can be slightly moved. So the strip works with y\in[0.4454,0.8660]. The width of this strip does not reach the record. But there is something to explore.

      7. To obtain a strip with a width 1.28675, it is enough to combine two 4H4 graphs at a distance of 2/3 or 8/3 (both options work, the first one gives a graph with 99503 vertices and 723941 edges, the second one – with 112156 vertices and 763263 edges). Whether one graph 4H4 is sufficient is not yet clear.

      8. Great! I will update the manuscript using the 2/3 case. I presune the must-be-mono pair are still (0,0) and (8/3,0).

      9. It turns out that for a strip with a width 1.28675, it is enough to take one graph 4H4. If we place its center at the point (0, 0), a mono-pair with a distance 8/3 is formed both between the vertices with coordinates (0, 0) and (8/3, 0), and between the vertices (-1, 0) and (5/3, 0). The trimmed graph has 61216 vertices and 393875 edges. There is no new interesting data on disks yet.

  7. By when do you need to submit the paper? Because we could add a reference to this paper mentioned yesterday: https://www.ams.org/journals/spmj/2018-29-05/S1061-0022-2018-01515-6/ They have also studied the strip, and the cartesian product of the plane with a small interval. From this point of view, our result about the disk of radius 1/sqrt(3)+eps can be considered as the cartesian product of a circle with a small interval, at least I’m fairly confident that your proofs would also work in this case.

    Reply

    1. I need to submit it on Sunday. I think we should probably not add this, because everything else in the paper is in the plane, and also because it may take time to become more than “fairly confident” that our constructions can be adapted to that setting.

      Reply

    2. At the moment, I am unable to improve the result. And this is somewhat good, because it creates the feeling that we are stuck in some fundamental limitation, and now it is interesting to understand what it is connected with.
      The article turned out to be nice both in form and in content. I understood the system in the arrangement of the pictures. The only thing I do not like is that the latter climb onto the bibliography. Can’t we try to move everything towards the beginning? However, I’m not sure that it will be better this way. Do not forget to remove the page numbers (according to the journal’s requirements, they should be invisible).
      Btw, I don’t think we should declare victory.

      Reply

      1. Thanks Jaan.

        I did try other distributions of the figures but in the end this was the one that minimises the sum of the distances between a figire and the text that references it and also has each figure on a different page, so I think it is the best.

        I can’t figure out how to remove the page numbers. I copied the entire LaTeX from your “green article” down to “maketitle” but they didn’t disappear. What is the trick?

        You are quite right about declaring victory, of course. I think the discovery of a human (or even human-verifiable :-)) proof of CNP!=4 was such a big milestone that it makes sense to call it a victory, but for sure we should continue to work on the many remaining dragons!

        Perhaps a good one to look at now is the lower bound for the surface of a large sphere. We could start by looking for UDGs that fit inside a strip of width 1.3 and cannot be drawn on a sphere.

      4. Because then we could look for 5-chromatic graphs that do not have such graphs as subgraphs. The idea of using 1.3 as a width is just because we know that we can get to 5-chromatic without having the easy non-sphere-drawable graphs (such as the hexagon).

        Of course the real first step should be to check whether Jaan’s latest graph is already sphere-drawable! If it isn’t, we can probably find smallish subgraphs of it that are not.

      5. Can you even have dense UDG graphs on a sphere? I think the limitation is far more than “no hexagons”. If I understand correctly, the core pieces of planar 5-chromatic graphs are all based on a lattice in Z[w1,w3], where every lattice point is automatically part of dozens of Moser spindles. But a sphere doesn’t have this underlying lattice. If you start on the equator then [move east 100 miles] and [move north 100 miles], where you end up depends on the order of those two steps. Without this commutative property, making dense graphs seems impossible.

        You can still make a Moser spindle on the sphere. But can you combine multiple Moser spindles in a useful way? Can you even combine triangles in a useful way?

        An intuitive way to think about this: Take some nice dense graph on the plane, and think about it as some super-rigid structure. Try to warp it to a sphere. You can imagine that most of the edges will “snap”. Only after removing a big fraction of the edges will the graph be flexible enough. Note that this flexibility is critical if you change your radius just a smidgen. (Is there a name for this kind of flexibility?)

        A tangent for triangles on a sphere — If you add 6 triangles around a point, you’ll get a hexagon-ish graph where the “first” and “last” points on the perimeter are close but don’t touch. Keep adding triangles. For certain sphere radii, your triangles will have a rational angle and repeat after T triangles (e.g. 6000000001 triangles) (a 3-chromatic graph). When T=3,4,5 you can chain together these graphs to form a tetrahedron, octohedron, icosahedron. With T=11 and two revolutions, do you get a similar structure? I’m pretty sure not because this would give a perfectly isomorphic distribution of a lot of points on the sphere, which isn’t possible. Anyways, it might be interesting if for large spheres it mattered if the triangle angles are rational or not.

    3. It was an open problem whether a UDG on a sphere of non-special radius can have a superlinear number of edges, and we also discussed it somewhere during this polymath. These are the two relevant papers:

      P. Erdos, D. Hickerson, and J. Pach, A problem of Leo Moser about repeated distances on the sphere, Amer. Math. Monthly 96 (1989), 569–575.
      https://doi.org/10.1080/00029890.1989.11972243
      Here it is shown that a UDG can have n log*n edges.

      Swanepoel, Konrad and Valtr, P. (2004) The unit distance problem on spheres. In: Pach, János, (ed.) Towards a Theory of Geometric Graphs. Contemporary mathematics (342). American Mathematical Society, Budapest, Hungary, pp. 273-280. ISBN 9780821834848

      Click to access 77d04c603400a244004846993c70aeed910e.pdf

      Here it is shown that a UDG can have n sqrt(log n) edges.

      Reply

  9. Hey all,

    I’ve been revisiting the area of upper bounds in higher dimensions, largely as a result of a very cool realisation by Jaan that the known 15-colouring of R^3 uses distinct sets of five colours repeated every three layers of cells, with each layer being assigned colours in the manner also used by Soifer nearly 30 years ago to tile the plane with six colours when one colour has a different distance excluded than the other five. (See Figure 6.5 of his book.) I’ve been focusing on R^4, and I am really new to 4D geometry, but I am fairly convinced by now that the tesselation of R^4 with the “24-cell”:

    https://en.wikipedia.org/wiki/24-cell_honeycomb

    should be colorable with fewer than 54 colours. When each cell is centred either on a unit grid point or on that grid shifted by 1/2 in all four directions, the cells have diameter Sqrt[2], and it seems that cells with centres Sqrt[7] apart are Sqrt[5/2] apart, and thus that the number of cells around a given cell that cannot be its colour is only 328 (I think), as compared with 370 for the permutohedron. That’s as far as I’ve got, but it seems like such a big difference that it would be astonishing if it doesn’t translate into a better colouring. My first (manual) attempt at an efficient sublattice is the vectors {{1/2,3/2,3/2,3/2},{-3/2,-1/2,3/2,3/2},{-3/2,3/2,-1/2,3/2},{-3/2,3/2,3/2,-1/2}} – what number does that give? Four of the inter-centre distances in a minimal simplex based on these vectors are Sqrt[7] and the other six are Sqrt[8], which seems pretty promising given that we get a 64-colouring just by naively using the permutations of {+/-2,+/-2,0,0}, where everything is Sqrt[8].

    I’ll try to work more on this myself soon, but I won’t have much time for a while – I’m hoping others can help.

    Reply

    1. Bah – so I realised that the volume of these cells is 1/2, so the determinant method gives 64 colours for the vectors mentioned (my claim that {+/-2,+/-2,0,0} gives 64 was nonsense). I have now found a better vector set – {{5/2, 1/2, 1/2, 1/2}, {2, -1, -1, -1}, {3/2, -3/2, -1/2, 3/2}, {3/2, -3/2, 3/2, -1/2}} – but it still doesn’t get to 54, only 56. T’m pretty sure that that’s the best we can do with this tesselation, unfortunately.

      Reply

  10. Hey all – Marijn has notified me of a really nice new paper available here:

    Click to access 2106.11824.pdf

    Of course we already have 5-chromatic UDGs with no Moser spindles, but this new way to get to CNP at least 5 seems very worth analysing with our (especially Jaan’s) methods. As for spheres, I wonder if the method can be extended to other radii – but already it is a great result that the CN is not monotonic with radius.

    Reply

    1. Wow, it’s great that there is an alternative version of the 5-chromatic unit distance graph on the plane.
      It’s funny that I was dealing with the same task some time ago. Moreover, I tried the same angles of rotation \pi/12 and \arcsin\frac{1}{\sqrt3}, and stopped half a step away from the resulting 5-chromatic graph.
      It is worth noting here that it is still not entirely true that this graph has absolutely nothing to do with Moser’s spindle. It contains an extended version of the Moser (or Golomb) graph, where the distance between the vertices of the rhombuses (or the vertices of the triangle) is 2 instead of 1, that is, it is formed from the Moser (Golomb) graph by adding three vertices. It is natural to ask whether other similar extensions of the Moser’s spindle will give 5-chromatic graphs as well. (For example, we can lengthen rhombuses twice.) Is it possible to get a 5-chromatic graph that has nothing to do with such extensions?

      As for the possibility of further reducing the graph with rotations by \arcsin\frac{1}{\sqrt3}, I doubt that my method will give a meaningful result here, since the original graph is too large.

      I also noticed that the graph marked as L_{10,1} on figure 2 is 3-, not 4-chromatic. Right?

      Reply

      1. Hi Jaan,

        yes, in a sense you could say that the design is still connected to the spindle. But if we use Minkowski summation of a set of vectors containing 7-wheel (i.e. hexagon), we will almost certainly get something like that.

        I think the most important result of our work in the case of the plane is that $\chi(Q(i,\sqrt{2}, ,\sqrt{3}, ,\sqrt{5})) \geq 5$, the same is true in cases (2,3,29), (2,3,47), and thus we have 5 fields of this kind, including the previously known cases (3,5,11) and (3,11,239), where the chromatic number is at least 5. Hence the questions arise: can we get a chromatic number 5 if the vertices of the graph lie in an extension formed by two roots of prime numbers? Is it possible to do it without $\sqrt{3}$ (and without triangle)? The second one seems to be very complicated, at least if we use the algorithm we know.

        Yes, thanks for the observation. One of the edges is not drawn correctly. In fact, in the construction for the great icosahedron we used graph 10.2 from this figure.
        https://drive.google.com/file/d/1RvAFY35W5SIL0qFC_mfTHEiSd854ougu/view?usp=sharing
        (The figure shows embeddings of 4-chromatic 10-vertex minimally rigid UDG not containing Moser spindle or 9-vertex 4-chromatic subgraph.)

      2. Hi, Vsevolod.
        You probably meant (3, 11, 247) instead of (3, 11, 239), right? We can add here a long set of triples of the form (3, 11, n), where n\in {7, 13, 31, 37, 47, 55, 61, 79, 103, 109, 127, 151, 157, 181 , 223, 229, 247, 253, 255, 271, 277, 287, 295, 349, 367, 383, 391, 397, 421, 439, …}. Maybe I’ve missed something.
        It seems to me unlikely that 5-chromatic UDG in the plane can be obtained without unit triangles, or that it will be enough to take two roots.
        Could you explain the basis for your hypotesis that 5-chromatic graphs with 3-cliques are likely to be based on similar subgraphs? In my opinion, there are a large number of 4-chromatic graphs that are difficult to perceive as an extension of the Moser graph. And each of these graphs can potentially be the basis of a 5-chromatic graph.

      3. Correction: I forgot to exclude factors 3 and 11 from the set. After correction: n\in {5, 7, 13, 23, 31, 37, 47, 53, 61, 71, 79, 85, 103, 109, 127, 151, 157, 167, 181, 215, 223, 229, 239, 247, 269, 271, 277, 287, 295, 311, 317, 335, 349, 365, 367, 383, 391, 397, 413, 421, 437, 439, …}.

      4. Yes, should be (3,11, 247). The list is derived from the monochromatic edges in some \sqrt(3), \sqrt(11) construction?

        And yes, it seems likely that \chi(Q(i, \sqrt{3}, \sqrt{11})) = 4, and the same is true in case (2, 3). But as far as I know, nobody has proved this yet. Without triangles, of course, it must be computationally very hard (for example, if you take something like O’Donnell’s construction for triangle-free 4-chromatic UDG). Both of the cases we looked at are generated by two complex numbers, and there will be more.

        I wanted to say that when we consider Minkowski sums and rotations we will often get cases where three triangular lattices are pairwise intersected by vertices, or when two such lattices are connected by an additional edge. Yes, not always. What kind of construction do you have in mind?

      5. I didn’t mean anything specific. I remember there was a nice non-rigid 4-chromatic graph somewhere here, but I could not find it.

        Yes, the set follows from the fact that (3, 11)-field has mono-pairs with the distance of the form (8p)/3^{q/2} with integer p and q. Btw, how did you get (2, 3, 29) and (2, 3, 47)?

      6. We have some more examples that are not described in this article. Three are given in the repository https://github.com/vsvor/dist-graphs/tree/main/plane/series%202 . Among them there are cases embedded in the fields (2,3,29), (2,3,47).

        In addition, we may have already succeeded in constructing a UDG embedded in field (2,3), from which we immediately have monochromatic pairs at distances 2, \sqrt{8/3}, \sqrt{4/3}, 2/3, … If so, we have several more 5-chromatic fields of the form (2,3,n), and most likely we will find an infinite series as well.

      7. I have not yet been able to find a 4-color mono-pair in (2, 3). Please inform if you succeed.

      8. I used an extended version of the construction from the article. If we take set M_1 = \{0\} \cup \{phi_0^p \phi_1_q: \quad 0\leq p\leq 23, \quad -2 \leq q \leq 2 \}, |M_1|=121, then after calculating the sum M_1 \oplus M_1 \oplus M_1 (with cutting off at radius 2.0) we have a graph with 176k vertices, the coloring of which is subject to many simple constraints. (The files are added to the repository.) It is interesting that if in the original construction we find only constraints on coloring of triples, here the constraints on pairs appear.

        Of course, there is gigantic redundancy in the construction.

      9. Hmm, something went wrong. Should be
        $M_1 = \{0\} \cup \{\phi_0^p \phi_1^q: \quad 0\leq p\leq 23, \quad -2 \leq q \leq 2 \}$

        M_1 = \{0\} \cup \{\phi_0^p \phi_1^q: \quad 0\leq p\leq 23, \quad -2 \leq q \leq 2 \}

      10. I confirm the occurrence of mono-pairs in the field (2, 3). In particular, the graph [V_{121}\oplus V_{121}, 1.0] \oplus V_{73} has mono-pairs with distances 2, 2/\sqrt3, 2/3, \sqrt{8/3}, \sqrt8. Here I redesignated the unit-radius graphs with rotations \pi/12 and \arcsin (1/\sqrt3) by the number of vertices (these graphs differ in the number of rotations by \arcsin (1/\sqrt3)), and the construction [V, x] means the trimming of the graph V with radius x. This graph can be further trimmed to at least a radius of 1.4, where it has 88849 vertices and 493680 edges.

        The graph [[V_{121}\oplus V_{121}, 1.0] \oplus V_{25}, 1.3] has 35065 vertices and 168048 edges, and contains mono-pairs with a distance 2.

        Thus, if I am not mistaken, in the field (2, 3) it is possible to realize mono-pairs with all distances of the form 2p/3^{q/2} and \sqrt8 p/3^{q/2}, which gives 5-chromatic fields of the form (2, 3, n), where n\in {5, 7, 13, 23, 29, 31, 37, 47, 53, 55, 61, 71, 77, 79, 85, 95, 101, 103, 109, 119, 127, 133, 143, 149, 151, 157, 167, 173, 181, 191, 197, 199, 205, 215, 223, 229, 239, 247, 253, 263, 269, 271, 277, 287, 293, 295, 311, 317, 319, 335, 341, 349, 359, 365, 367, 373, 383, 389, 391, 397, 413, 415, 421, 431, 437, 439, 445, 455, 461, 463, 479, 485, 487, …}.

      11. It’s getting more interesting. A mono-pair with a distance 2 is observed even on a graph [V_{121}\oplus V_{121}, 1.0] \oplus V_{7} with 15547 vertices and 86766 edges. Here V_{7} is the wheel-graph. A little more, and it will be possible to do a systematic reduction.

      12. The graph [[V_{121}\oplus V_{121}, 1.0] \oplus V_{7}, 1.3] with 11305 vertices and 46194 edges is also suitable, although it takes 100 times longer to test.

      13. The graphs [[V_{121}\oplus V_{73}, 1.0] \oplus V_{7}, 1.5] (10981 vertices, 50484 edges) and [[V_{73}\oplus R_{73}, 1.0] \oplus V_{7}, 1.5] (7231 vertices, 33534 edges) also work. Here R_{73} is a copy of V_{73} rotated by \arcsin (1/\sqrt3).

      14. Yes, and I checked that in some cases we can take even \{-1,0,1\} as the third summand.

        Still don’t believe that it can lead to the smaller 5-chromatic graphs. The problem is that in the case of (3,11) there are many more 4-chromatic subgraphs with a small number of vertices. But anyway, it turned out to be much more interesting than I expected.

      15. Yes, it will be necessary to work more serious with this, and try to bring the number of vertices to 1000. What I like about (2, 3) is the presence of a mono-pair with distance 2, which is much more interesting than distance 8 in the case of (3, 11).
        What else I would like to ask, is it by chance that a spindle with a radius \sqrt7 appears in your article in Figure 9? In connection with the new data, a suspicion creeps in, whether will it work too?

      16. By tightening the trimming, one can slightly reduce the number of vertices, getting graphs with a mono-pair: [[V_{121}\oplus V_{73}, 0.68] \oplus V_{7}, 1.44] (8293 vertices, 33294 edges) and [[V_{73}\oplus R_{73}, 0.77] \oplus V_{7}, 1.50] (6169 vertices, 26796 edges).

      17. Figure 9 makes no particular sense. I do not know if anything can be done in the case (3,5,7), where we cannot even present a 4-chromatic graph. If we could construct 4-chromatic graphs for arbitrary case (p,q, …) or prove that they do not exist, it would be interesting too, but I think nobody knows how.

      18. I’m wrong, of course, the next generalized Moser spindle graph (4-chromatic) can be embedded in (3,5,7).

      19. Here the factors 5 and 7 are related, so that the corresponding generalization of Moser (Golomb) graph can be embedded in (3, 35). I would not be very surprised if we manage to obtain the corresponding mono-pair and a family of 5-chromatic fields of the form (3, 35, n).

      20. Btw, if we remember that all Loeschian numbers can be multipliers of the length of a mono-pair, then the set of possible values of n is expanded further.

      22. And in case (2, 3), one can form a right-angled triangle with a hypotenuse, which is expressed by the square root of most integers.

      24. Other constructions (small graphs and their corresponding rings, as on the ‘Algebraic formulation’ page) must exist. But for now I can say that in the case (3,35) what we did before does not immediately lead to a result.

      25. Because in this case there is no corresponding good angle of rotation that would fit an integer number of times into 2\pi?
        By the way, do you well understand the methods outlined in the “Algebraic Formulation” you mentioned? (I have problemes here.) Could you do the same for (2, 3)?

      26. For any case of a generalized spindle we can take pi/3 . The problem is the size of the 4-chromatic subgraphs, and, informally speaking, their density.

        The reasoning on this wiki page is not too complicated, the meaning is clear, but I don’t have the proper technique and can make silly mistakes.

      27. The key difference is that in the Moser spindle case we are dealing with the addition of elements that do not belong to the previous field.

        In case (2,3), the element \frac{\sqrt{3}+i \sqrt{6}}{3} belongs to the cyclotomic field Q(\zeta_{24}). In fact, we can get the same set of vertices by adding the degrees of \zeta_{24} divided by 3. Here \zeta_{24} = e^{\frac{2\pi i}{24}} .

        Therefore a similar coloring, if it exists, should be based on homomorphism
        Z[\zeta_{24}, \frac{1}{3}] \to Z_4[\zeta_{24}],

        and here the finite ring contains 2^{16} elements.

        Perhaps there is a simpler way.

  11. Has anyone figured out a fully generalized bound better than (2+sqrt(n))^n for R^n? Sorry if this has been answered, but I’ve been looking into this for several hours over a few days and haven’t found it.

    Reply

      1. Great! I’ve found a better bound: ((2+sqrt(n-1))^n)/(sqrt(n)/2) for floor(2+sqrt(n-1)) even, and (2+sqrt(n))^n/(sqrt(n)/2) for floor(2+sqrt(n-1)) odd. So I guess the latter as a universal bound; I’m working on making it work better for that one, and I can save 1/2*(floor(2+sqrt(n))-1)^n colors so far, but that converges to a small fraction of the total number of colors, 1/e^(sqrt(n)), which itself converges to 0, so I don’t think it’s relevant yet.

      2. Oh, actually, in trying to formalize the odd bound, I got a slightly better and cleaner bound: 2*(2+sqrt(n))^(n-1).

      4. You’re right, the simple bound doesn’t work for n = 2. However I found a much more interesting way to extend low dimensional results to high dimensional bounds, so I’m creating a more nuanced explanation soon, which accounts for this.

        I’ll post it when I finish.

      1. Ah, great, thanks for letting me know of the better upper bound. I would have been really sad if I hadn’t found a different related result (well, I think. I’m working on it).

        For the bound I found, though, I suppose I do better than 3^n until n = 9 (I get (2 \sqrt{2})^8 for n = 8, for example) which is marginally further than the polymath table goes, though that seems like a much lesser accomplishment.

        The general bound takes a bit to explain, which is partially why I didn’t. Defining a couple variables:

        m = \leftceil \sqrt{n}+1 \rightceil (only marginally better than \sqrt{n} + 2 but it matters in my more detailed argument).

        p and q, integers which can be chosen arbitrarily,

        \mu = ((m-1) \hspace{1mm} mod \hspace{1mm} q)+1, and,

        n, the integer dimension, of course.

        Putting it in the same terms is slightly tricky, but I believe, for the constraint

        $(p-1)(\mu-1)+(4m+2)/(\mu-1) > 2(m-1)$

        (and as a consequence, \mu > 1)

        We get a coloring with

        m^{n - \leftfloor n/p \rightfloor}*q^{\leftfloor n/p \rightfloor}

        colors. For m and n even, we can choose p = 2 and get q = \mu = m/2. This gets total colors m^(n/2)*(m/2)^(n/2), which is 8^4 or (2 \sqrt{2})^8, somewhat better than $3^8$.

      2. In any case, as far as upper estimates are concerned, nothing new has been invented for a long time, and such constructions are of interest. Do you plan to publish this?

      3. There is a paper by Prosanov (https://arxiv.org/pdf/1610.02846.pdf) from which one can derive some explicit upper bounds for every $n$, and in particular asymptotic upper bound $\chi(R^{n})\leq (1+o(1))\log n \cdot 3^n$.

        We have recently posted a paper (https://arxiv.org/pdf/2112.13438.pdf) that provides some (hopefully new) upper bounds on $\chi(\mathbb{R}^n)$ for small values of $n$. All of the bounds are based on sublattice coloring scheme by Coulson (the one used to prove $\chi(R^3)\leq 15$).

        For example, using computer verification we confirmed that $\chi(R^4)\leq 49$ (as Claimed by Coulson and Payne), and showed that $\chi(R^5)\leq 140$, $\chi(R^7)\leq 1372$, and $\chi(R^9)\leq 17253$.

        Theoretical results are based on two propositions:

        1) If in $R^{n}$ there exists a full dimensional lattice $\Lambda$ with covering-packing ratio at most 2, then $\chi(R^n)\leq 3^n$. This is proved by coloring Voronoi cells of $\Lambda$ according to equivalence class with respect to $3\Lambda$.

        2) If in $R^{n}$ there exists a full dimensional Eisenstein lattice (lattice over $Z[e^{2\pi i/3}]$) $\Lambda$ with covering-packing ratio at most 3/2, then $\chi(R^n)\leq 7^(n/2)$. This is proved by coloring Voronoi cells of $\Lambda$ according to equivalence class with respect to $(3+e^{2\pi i/3})\Lambda$.

        So for $n\leq38$ and $n=48$ we have $\chi(R^n)\leq 3^n$, and for $n=2,4,6,8,24$ we have $\chi(R^n)\leq (sqrt{7})^n$

      4. Wow, what a phenomenal set of results! Trivial notes: (1) you can mention that “ag24ag24” is actually Aubrey de Grey; (2) the best bound found by the Polymath team for 6 diimensions is actually 448, improving on the 462 you mention. But wow, just wow, these improvements are truly staggering. Congratulations!

  12. Ah, messed up half the formulas. That’s what I get for trying to tex with wordpress for the first time. The first one was just ceil(\sqrt{n}+1) and the last one was m^{n - floor(n/p)}*q^{floor(n/p)}.

    Reply

  13. OK! In true Polymath fashion we have a very cool new contribution from someone new to our little family. Unfortunately he posted it in thread number five… Anyway, rock on down there and see it – the name to scroll to is Asger Haugstrup. The discovery is a 52-vertex 6-chromatic UDG in R^3. This improves not only upon my 59-vertex effort published in Geombinatorics a while back, but also on Geoff/Dan’s improvement to 56 vertices which Dan revealed at Domotor’s workshop a few months ago. I’ve briefly studied Asger’s structure, and I hope I can illuminate it a little.

    As in the past, we begin with the 10-vertex structure first presented by Nechushtan, which consists of two copies of the six-vertex “tri-tetrahedron” with both pairs of tips coincident and with a relative rotation that creates two more edges to make a square out of the vertices that are shared by exactly two tetrahedra.

    So, first a brief historical review.

    1) Nechushtan created something with a few hundred vertices – it was a bit messy, but it worked. His first step was to add an eleventh vertex attached to just two of those four two-tetrahedron vertices, specifically two that are neighbours of the same tip (call it tip A). This is a “flap” whose distance from the other tip (“tip B”) is arbitrary within about 1 to 2.5, but which must nonetheless be different in colour from B in any 5-colouring if A and B differ in colour.

    2) In my construction, we spindle the tips of two copies of this (with the B’s coincident and A1,A2 at unit distance), and rotate so that the two flap vertices are also coincident, such that now the flap vertex and tip B must unconditionally be different colours. The key thing is that we still have not fixed the distance between the flap and B. Hence we can clamp copies of this 20-vertex thing to the non-unit distances of any 6-vertex “scaffold” graph (subject to the 1-to-2.5 range constraint), in particular the diagonals of an octahedron, and either that scaffold or one of the clamps must use six colours.

    3) Clearly there is lots of scope for rotating the three clamps, but I was unable to use that fact to eliminate more than one vertex. Dan and Geoff did a lot better and eliminated four, by using as their scaffold the other 12-edge 6-vertex UDG, namely the tri-tetrahedron.

    Right! To cut to the chase: the big innovation that Asger has introduced is to go to trios, rather than pairs, of vertices that both must and cannot be monochromatic in any 5-colouring. Rather than chucking in a spindling, he just totally brazenly chucks in a SINGLE VERTEX that is connected to ONE other vertex, namely tip A. He notes that the 12-vertex thing consisting of Nechushtan’s bi-tri-tetrahedron, plus the flap, plus this one vertex, is not 5-colourable if the flap, the extra vertex and tip B are required to be all the same colour. This is by exactly the same logic that Nechushtan used, but it clearly asks a very different question about what the scaffold should be.

    So, well, I have totally failed (so far) to understand Asger’s scaffold, which has 25 vertices and needs three clamps (because there are three trios of vertices one of which is mono in any 5-colouring), so a total of 52 vertices since each clamp adds nine. Instead I am trying to beat 52 by seeking a much smaller scaffold that only needs four clamps. One only needs 11 vertices to get to five clamps – we do this by adding to the bi-tri-tetrahedron a vertex that makes a square pyramid whose base is the quartet of two-tetrahedron vertices, and the trios consist of that vertex and either both tips or two of the four three-tetrahedron vertices – so I’m quietly hopeful that four can be done with fewer than 16 (plus 36 for the clamps) vertices. Any ideas?

    Reply

    1. Woah, I have one! 47 vertices, being an 11-vertex scaffold with only four possible mono triples (and, by pigeonhole, the need for at least one of them to be mono in any 5-colouring). It is painfully simple: we just glue three tetrahedra to faces of a fourth one, then we identify all three pairs of tips of two copies of that. The only monoable triples are (a) the three tips, or (b) one tip and the two non-tips that aren’t connected to it.

      Reply

    2. OK, I guess I owe you all a picture 🙂

      For clarity I show here only 15 of the 47 vertices, which are all that is needed to demonstrate that everything works. The three tips of the scaffold are red, the eight other vertices of the scaffold (which form two tetrahedra) are blue, and the Nechushtan-clamp vertices to which Asger brilliantly attaches just one new vertex are white for the three-tip clamp and green for the other three. Those last four vertices thus need to be 5/3, d and 1 from the trio that the clamp is preventing from being mono, where d is determined by the distance between two of the trio; in our case that distance is 5/3 or Sqrt[8/3] and d comes out at 1.71389 and 1.70828 respectively, which are indeed under the maximum of Sqrt[3] of the range available by moving the flap.

      Unit edges are grey, and I’ve shown edges length 5/3 and d in blue and red respectively. I played with viewpoint a bit but I think the blue “edges” from the green vertices really do go through the central-tetrahedron vertices, which is why they look as though they end there (i.e. those lines then become coincident with actual edges).

      The neatest orientation of the structure in 3-space is to put the tips on the coordinate axes at 5/Sqrt[18] from the origin. Then the scaffold vertices all come out with quite nice coordinates:

      {{0,0,5/(3 Sqrt[2])},{(2 Sqrt[2])/9,(2 Sqrt[2])/9,-(5/(9 Sqrt[2]))},{(2 Sqrt[2])/3,(2 Sqrt[2])/3,1/(3 Sqrt[2])},{5/(3 Sqrt[2]),0,0},{-(5/(9 Sqrt[2])),(2 Sqrt[2])/9,(2 Sqrt[2])/9},{1/(3 Sqrt[2]),(2 Sqrt[2])/3,(2 Sqrt[2])/3},{0,5/(3 Sqrt[2]),0},{(2 Sqrt[2])/9,-(5/(9 Sqrt[2])),(2 Sqrt[2])/9},{(2 Sqrt[2])/3,1/(3 Sqrt[2]),(2 Sqrt[2])/3},{1/(3 Sqrt[2]),1/(3 Sqrt[2]),1/(3 Sqrt[2])},{7/(9 Sqrt[2]),7/(9 Sqrt[2]),7/(9 Sqrt[2])}}

      The clamp vertices inevitably have repulsive coordinates, but you can’t have everything 🙂

      Reply

      1. Thanks a lot for the very nice response. It made me think a little and I felt a bit foolish when I realized that the graph I posted really didnt need a 25-vertex scaffold but it can be reduced to 21 vertices simply by removing J,K,R and S and you still get 3 triples where a 5-coloring will ensure that one of them will be monochromatic. In the updated version the triple A, E, J is replaced with the triple C, F, M which has similar distances between the vertices. We end up with a graph with 48 vertices and 152 edges. Still one vertex more than the the new graph you discovered. The 21-vertex scaffold in my updated graph is a two-copy-tri-tetrahedron graph from A to B and a three-copy-tri-tetrahedron graph going from A to C sharing the vertices A,D and E.(instead of 2 three-copy-tri-tetrahedrons).
        What software do you use when you visualize a graph?
        Right now I look into the new 47-vertex graph.. I will post more later.

      2. Ah, now I understand your original scaffold! (And the reduced one.) Thank you. I still need to understand why you can use only three of the available triples, but I’m guessing it’s the pigeonhole principle again, i.e. some colour must be used at least five times – right?

        I do everything in Mathematica. It’s very powerful at visualising graphs (as well as everything else, of course).

        Did you receive my email about writing up these graphs?

      3. Aubrey, could you please explain in more detail how these colored virtual edges should be perceived? I still can’t figure out what objects are connected to the 11-vertex graph, because I got confused in the terminology.

      4. Jaan: sure. If you go back to Nechoshtan’s 2002 paper, or indeed my paper describing the 59-vertex structure, you will see a 10-vertex thing that consists of two copies of the six-vertex “tri-tetrahedron”, with the “tip” vertices (the ones that are not vertices of the central tetrahedron) merged, and with a relative rotation around the line between the tips so that the vertices shared by two tetrahedra form a unit square. Nechushtan then attaches (as did I) an 11th vertex to two of the vertices of that square, specifically two that are connected to the same tip; call that tip A and the other tip B, and call the new vertex F, for “flap”. Asger then attaches a 12th vertex to A and nothing else; call that new vertex C. Clearly F can move freely around a circle and C can move freely around a sphere. Thus, the edges of the triangle BCF can vary a lot in length, and that allowed Asger to clamp a copy of this structure to each of the three triplets of vertices one of which must be mono in any 5-colouring of his scaffold. I did the exact same thing with my 11-vertex scaffold that needs four clamps. In my picture I show only vertex A of the clamps (as well as B, C and F, of course, since I also show the whole scaffold). The length AC is always 1, the length AB is always 5/3 (that’s my blue lines), and the length AF (my red lines) is a number between 0 and Sqrt[3] that is determined by the length BF (which itself can be anything between about 1 and 2.5).

      5. Now I understand, but not everything. In the figure, you replace each clamp with a single vertex and three pseudo-edges (one of which is a real edge). The clamp has 12 vertices, three of which are combined with the scaffold so that each clamp adds 9 vertices to the graph. I was somewhat confused by coloring one of the four vertices A in white and the others in green. Now I see that it only has to do with which vertices of the scaffold the clamps are connected to, not the difference in the clamps themselves.
        Now I do not understand why you are connecting the clamp to a triplet of vertices, which cannot be mono anyway, since it contains an edge already in the scaffold. For example, clamp 14, which is best seen, is connected to the vertices 8, 9 and 3, with the latter two already connected by an edge.

      6. Jaan – the only thing you’re missing is the commnt I put in the post just above the picture: “I played with viewpoint a bit but I think the blue “edges” from the green vertices really do go through the central-tetrahedron vertices, which is why they look as though they end there (i.e. those lines then become coincident with actual edges).” In other words, no, vertex 14 is not actually attached to vertex 3, it’s attached to vertex 7 (the red one at the bottom right).

      7. OK. Could you now could you please explain in more detail how you prove that one of the four triples of an 11-vertex graph is necessarily mono in a 5-coloring?

      8. And if you think about less confusing illustration: is this the only way to connect clamps or can it be done so that the edges do not overlap? If it is not possible, then it is better to let the blue edges be visible, and not the gray ones.

      9. “could you please explain in more detail how you prove that one of the four triples of an 11-vertex graph is necessarily mono in a 5-coloring?”

        It doesn’t matter how many triples there are. If you assign five colours to 11 points, you need to assign some colour to at least three points. (Pigeonhole principle.) And clearly it must be three points no two of which are connected.

        “less confusing illustration”

        I think it’s the only way to connect those clamps, yes. I don’t actually agree about prioritising the blue lines – I think the most important thing is to show the whole scaffold.

      10. Thank you. Now everything is clear.

        Honestly, seeing only this picture of the scaffold, I still did not understand its geometry until I entered the coordinates into the program and looked at the graph from different points of view. And even so, understanding did not come immediately. I think if you want to show the scaffold more clearly, then you need to separately show its half, and explain that the second half is its reflected copy relative to the plane passing through the vertices 1, 4, 7. As for the connection of clamps, then, probably, you should list the vertices to which they are connected.

  14. The 47-vertex graph is an elegant solution and I have the feeling that there wont be UDGs with fewer vertices proving this lower bound. We will see. 🙂

    Reply

  15. Maybe its possible to use the pigeonhole principle somehow in my graph aswell but that is not part of my reasoning, It is all about the properties of the 10-vertex structure.(Nechushstans(?))
    The same 10-vertex structure that goes from A to B goes from A to C and they share the vertices A,D and E and together they form a 17 vertex graph. If both D and E have different colors from A then both B and C have to have the same color as A(assuming a 5-coloring). This is the first possible monochromatic triple. The other option is that D or E has the same color as A and then B and C both have different colors than the one in A. Adding an extra layer of 3-tetrahedrons around the axis going through A and C and we get the remaining 4 vertices for the scaffold. Since we now look at a situation where A and C have different colors we also know that either D and J have the same color as A or that E has the same color as A. For symmetry reasons we also know that the color in C will be repeated in either F and M or just in G. Since we know that a 4-coloring of any triple-tetrahedron will result in a 6 coloring in the neighbor-tri-tetrahedron we also know that a 5-coloring implys two options: A,D and L having the same color or that C,F and M have the same color.

    Reply

    2. Extremely elegant Asger – thank you! Yeah, and pigeonhole gets nowhere, there are loads of independent quintets of vertices.

      Reply

  16. To keep everyone updated: a manuscript has now been submitted to Geombinatorics, authored by me and Asger, that describes both the 48er and the 47er (as well as noting Dan and Geoff’s 56er). I wrote it rather fast (since Soifer’s next deadline is very imminent), but I think it does reasonable justice to the various insights. As in the past, since Geombinatorics simply reproduces submitted PDFs I am reluctant to just post the thing to the arxiv and thus reduce incentive to subscribe; but I will supply a preprint to anyone who emails me at alwaysmyself-at-mail.com (not gmail).

    Intuitively, I am personally midway between Asger and Jaan regarding whether 47 can be beaten – but let’s try!

    Reply

  17. If Jaan is optimistic then I may be swayed by it. After Aubreys discovery I did try to get back with something based on a smaller scaffold and only three triples but obviously I wasn’t able to do it.. I have some very loose ideas that probably wont work but I will try.
    All the 6-chromatic UDGs I have encountered so far countains the Nechushtan 10-vertex graph as a subgraph. Does anyone exist where this is not the case?

    Reply

    1. No such graph has been discussed, as far as I know. However, I wouldn’t be surprised if one can do it by using the method Dan and Geoff (and others) have used so successfully at higher dimensions, basically involving taking slices through hypercubes and then tinkering.

      Reply

  19. It is well known that if we color the plane (with unit forbidden distance) using hexagonal tiles of 7 colors, we can get the maximum distance between the nearest tiles of the same color \sqrt7/2. If we take 9 colors, then the maximum distance will be \sqrt3. What if we take 8 colors? What is the maximum distance we can get between tiles of the same color in this case? I still get the same \sqrt7/2. And this is a little weird. Can we get more?

    Reply

    1. Hey Jaan – hm, I don’t think that’s weird if you are saying that the tiling must be regular hexagons – there are no possible intermediate distances. But that’s too obvious, so you must mean that even if you use tiles of any shape you still cannot beat Sqrt[7]/2. That is indeed surprising (to me). I will go and think about it 🙂

      Happy holidays to everyone!

      Reply

    2. The fact of the matter is that you can take tiles of any shape. It looks like the same problem occurs for the number of colors 10, 11, 14, 15, 17, 18, 20…

      Reply

  20. OK, so I think Jaan has given us a great holiday present here. I have not found any clever tilings, but the essence of what Jaan is asking us is a generalisation of the tiling-restricted CNP question:

    Let a tiling of R^n be defined as usual, Jordan curves yada yada. Then, for a given n and k, what is the greatest d such that R^n can be tiled with k colours in such a way that all pairs of points of the same colour are either in the same tile or are at least d apart, and such that no two points in the same tile are more than 1 apart?

    Jaan asks the question for n=2 and k=8. But it’s already interesting for other values. With n=2 I’m assuming that the honeycomb gives the best d for k=3 and 4, namely 1/2 and Sqrt[3]/2 respectively, but I have no clue how to prove it – and I have no idea what d is when n=2 and k=5 or 6. And for n>2, I mean wow, there are quite a few PhDs to be had there…

    Reply

    1. For six colors, Pritikin’s construction seems to be optimal. It gives a distance of about 0.99 if I’m not mistaken.

      Reply

      1. Yeah (you mean with the diamonds collapsed, of course). I think the exact value is Sqrt[9+Sqrt[45]]/4, which is indeed just over 0.99. I’m guessing that the same thinking would be appropriate for five colours, i.e. that a good attempt would come from collapsing the empty spaces in your brilliant 5-colouring of 96% of the plane. I dare you to have a go 🙂

      2. In fact, even a little more in the case of six colors, since between the tiles (of given color) in the same row we can take the distance of about 0.99 (less than 1). In the case of five colors, I also think that we can improve the result using the following trick. Take a (hexagonal) 4-coloring, and in each group of four tiles, forming something like a diamond, insert a 5th-color tile in the middle. This should relax the constraints on the original 4 tiles. But I doubt this trick will help in case of 8 colors.

      3. Six – Woah, so true! – actually more than a little – I think the number comes out at Sqrt[Sqrt[55/56]], which is just over 0.9955, so more than twice as close to 1 than we were before. Well spotted!

        Five – I’m trying to visualise your trick but I’m not seeing it yet. Post a picture?

      4. Ah no, apologies, it’s only Sqrt, not Sqrt[Sqrt. So only slightly over 0.99 after all. Still a small improvement though, so Jaan was still right!

      6. It looks like this construction doesn’t work too. If we consider a pair of adjacent tiles from an oblique row of hexagons (according to the picture), then after adding a tile of the fifth color, one of them turns into a heptagon, the second remains a hexagon. In this case, there are only 3 inner constraints for these two tiles in total instead of 6 (the diameter is not more than 1). But this still does not allow increasing the distance between tiles of the same color. So I don’t know yet how to beat \sqrt/3 for 5 colors.

      8. As for the construction that I used to increase the proportion of the colored plane, in relation to the task of increasing the distance between tiles of the same color, it comes down to cutting one of the tiles (in a 4-coloring) in half. The rest of the tiles are not affected, and the rows of such tiles remain. And this again will not allow increasing the distance between tiles of the same color.

      10. Nice! And I see that 1.4 is in fact the exact value, not a numerical optimisation as I initially guessed.

        There really ought to be a clean way to generalise that…

      11. I went over on the computer all possible (as it seems to me) variants of hexagonal tilings with the number of colors k from 5 to 66, such that all tiles have the same shape and all three diagonals of the tile have unit length. All k can be divided into Loeschian (L) and non-Loeschian (N).
        In about a third of cases with k\in N, the transition from k-1 to k leads to an increase in the maximum distance d between tiles of the same color; this happens for k\in\{6, 8, 20, 24, 30, 33, 34, 41, 42, 46, 54, 56, 60, ... \}. But in 2/3 of cases adding color does not increase d. So the function d(k) is still stepwise.
        For k\in L, the distance increases almost always, but there are exceptions. So, tiling with k=36 beats k=37. The explanation is simple. In the first case, tiles of the same color are oriented to each other by an edge, in the second – by a corner.

      12. And one more surprise. In 6-coloring, the hexagonal tiling still beats (Pritikin’s) pentagonal tiling. Here d^2 is the root of the equation 16-8 x-95 x^2+88 x^3=0, and d\approx 0.992076.

    1. Nice! I bet Jaan’s method beats most of these, since these authors seem to check only tilings with regular hexagons.

      Reply

  22. I propose to consider a modification of the problem of coloring stripes and disks for the case when the distance between tiles of the same color must be strictly greater than one. It looks like it should be interesting. In this case, Pritikin-style 6-color strip tessellations and many disk tessellations no longer work (if I’m not wrong).

    Reply

    1. For disks, the question can be rephrased as follows. Can we get the radius r_k of a k-colored disk larger than the trivial division of the disk into k equal sectors, where r_k=\{1/2, 1/2, 1/\sqrt3, 1/\sqrt2, \sqrt{(5+\sqrt5)/10}, 1\}?

      Reply

      1. k=1,2,3 are not interesting, of course, since we have sharp bounds already. For k=6 I think we can take Philip’s disc and remove the outer ring of tiles, then we can turn the vertices of the central tile into short edges so that it no longer touches the tiles that it touches at a point in Philip’s design. I think that (11-tile) design works.

      2. Simplest exact expression I can get is Sqrt[1 + (2 + Sqrt[5 – 2*Sqrt[5]])^2]/2 – numerically about 1.45207.

      3. Hmm. I did not understand the moment with the short edges of the central tile. In my opinion, the requirement that the distance between two tiles of the same color is strictly greater than one should kill every second tile of the ten that form the outer ring in your 11-tile disk.

      5. Actually no, I leave the tiles all the same shape as before (up to epsilon). The short edges are not edges of the central tile – they are boundaries between pairs of long tiles, i.e. they radiate out from the centre of the disc. The long tiles become hexagons with two short edges (not heptagons, because the outermost vertex is gone), but the central tile is still a pentagon. And the other tiles are just triangles.

      6. I meant that the distance between the vertices of the long tiles, which in your construction turned into short edges, should increase a little. Is not it so?

      7. Jaan – ah, yes I guess so – but only by an arbitrarily small epsilon I think. I don’t think the radius can be increased by a finite amount as a result.

  23. Ah, stupid calculation error, apologies – the actual radius is (I think!) the even gnarlier Sqrt[11/8 – 1/(8*Sqrt[5]) + Sqrt[1 – 1/Sqrt[5]]/Sqrt[2]] so numerically about 1.35824. Minus epsilon, of course. Could someone please derive this independently, just to be sure?

    Reply

    1. Simpler version of the expression: Sqrt[1 + (2 + Sqrt[2]/Sqrt[5 + Sqrt[5]])^2]/2. (No idea why Mathematica thought the other version was simpler!)

      Reply

    2. I can. But you won’t like my result. Sqrt[3/2-1/2/Sqrt[5]+Sqrt[1-2/Sqrt[5]]] or about 1.26543. My skeleton is five squares built on diagonals of unit length of a regular pentagon.

      Reply

      1. Hm, that was my skeleton too… Ah, OK, I just found my error – my formula and numerical value now agrees with yours. Thanks!

      3. No. I have a strong sense that one should be able to prove that the trivial construction can’t be beaten for 4-discs, but I’m not so good at proofs as at constructions 🙂

      4. Oooh I think one can do Sqrt[3]/2 minus epsilon for the 5-disk (only 0.015 better, but still). Do the 4-disk design, which obviously makes the tiles too big (diameter Sqrt[3/2], but then put two tiles of the 5th colour on opposite sides of the disk. They only come within 1 of each other, and there is quite a bit of margin to ensure that they can reduce the diameter of the other tiles to 1 while also remaining diameter less than 1 themselves.

      6. Slightly less than 0.889 here. (The faint green and red lines indicate which edges are “stressed” and should be unit length.)

      7. Woah, brilliant! I had totally not considered that making the two red tiles different could help.

      8. Haha, me neither, the simulator insisted.

        I haven’t thought this completely through, but I suspect it’s never helpful to have more than 3 tiles meet at a vertex. In that case, the dual graphs are all triangles, and there are very few designs to consider.

      9. Yep – the circumcircle of an isosceles trapezium with sides 1, 1, 1 and Sqrt[3]. The radius seems to be Sqrt[(3+Sqrt[3])/6] or about 0.888074.

  24. It’s great. It must be assumed that for the 6-strip there is also some non-trivial solution.
    There is a slightly more general task: coloring simple geometric shapes, such as a disk or a strip, in such a way that a given distance interval is forbidden. Of particular practical interest is also the coloring of the annulus, that is, the area enclosed between two concentric circles. The motivation can be found in the article that is mentioned here:
    https://dustingmixon.wordpress.com/2021/02/01/polymath16-seventeenth-thread-declaring-victory/#comment-32246

    @Tom, could you modify your simulator so that it can work with the forbidden distance interval from 1 to d? (The d parameter is set manually.) Also it would be nice to add tools for coloring the annulus (bounded by circles of radius 1 and d) and the strip.

    Reply

    1. The simulator just checks pairs of vertices for distance violations, and nudges the vertices to lessen the violation. So, a forbidden distance interval [1,d] should be straight-forward to implement. Sometimes line-vertex distances are also important to consider, or curved edges.

      I think I remember my simulator couldn’t handle the 4-colored strip for some reason (curved edges?). But I made a version specifically for it that divided each edge into a chain of 10 or so vertices, and eventually that worked decently.

      Anyways, let me know if you have specific scenarios in mind!

      Reply

      1. No, I’m not suggesting any complex scenarios. But let’s clarify a little.
        The first modification I propose is to replace one forbidden distance with an interval of distances (adding parameter d). The logic of the simulator does not change.
        The second task that interests me is the coloring of the annuli. Here the inner circle of the border is fixed (radius 1), the outer circle has a variable radius d. In my problem, this is the same d that appears in the interval of forbidden distances [1, d]. So in the process of running the simulator, this parameter is adjusted in the same way as it happens with the radius of the disk. Alternatively, these two quantities (forbidden distance interval and radius of the outer circle) can be separated by introducing two variables, one of which is set manually and the other is determined by the simulator. But so far it’s not interesting for me.

      2. I think I understand. But, I’m not sure what task you want to use a simulator for. For example, here’s a 5-color strip design. I could have the simulator nudge the vertices on the perimeter vertically to keep them off of some strip. This would let me realize the maximum strip width for this design. But you guys can figure out the precise answer without the simulator.

      3. Hey Tom – the question is whether there is a clever 6-strip design that is scaleable (unlike the system with four rows of tiles that we derived from the Pritikin design) and wider than Sqrt[3] (which is the trivial width with to rows of rectangles). Since your simulator found something clever for the 5-disc (and also of course for the unscaleable5-disc a while ago), I think Jaan is thinking it might happen again. I’m not so optimistic in this case, but I’ve been wrong before!

      4. For the simulator you need to provide the dual graph as input.

        I did have a searcher program that systematically built up dual graphs, and I manually try out some of those graphs in the simulator. But, I don’t have this automated, and that would be a bigger undertaking.

        Anyways the searcher found a good (but not optimal) unscaleable 5-disc, and Aubrey optimized it by hand.

      5. maybe something like this? it’s just the 5-color design with orange tiles thrown in. No idea if it’s better or worse than sqrt[3] (but I can add logic to the simulator if necessary to figure it out)

      6. Hm, I must say that looks quite promising. (Yeah, I think algebra will always be required in order to get an exact optimum for a design.) I’ll think what the widest version of that might look like.

      7. Yes, I want to repeat once again, just in case, that we have several different tasks. Although they are similar. I would separate them according to the shape of the object being colored (disk, strip, annulus) and the interval of forbidden distances (zero, small epsilon, significant). That is, nine different tasks are already being typed.
        Annulus is a new object for us. For me, the coloring of the annuli plays an auxiliary role, it helps to determine the scope of the method described in the article mentioned above. Although this task can be interesting in itself.
        What I want to get for the coloring of the annuli should work like this. I manually sketch some tiling (create a dual graph) and set the interval of forbidden distances, that is, the parameter d. Next, the simulator tries to maximize d in accordance with the logic that is already built into it. The role of the simulator here is in the ability to quickly test existing ideas, tiling options. In addition, the simulator will show all strenuous distances. Then, after choosing the best idea, it will already be possible to calculate the exact values.

      8. Well, after playing quite extensively with he constraints in Mathematica I’m afraid it looks very much as though the maximum is exactly Sqrt[3]. Nice idea though!

      9. I came to the same conclusion on paper. Moreover, it can be seen that in the limiting case, the tiles tend to form a vertex of the fourth degree. Also, here you can see the strip from your pentagon tiling of the plane.

      10. Maybe I could provide the simulator as a Windows executable?

        I’m kind of interested in making the simulator as a web page, but that’s a bigger project that’s new territory for me.

      13. Great! Thank you very much, Tom.

        Here is an example of 5-coloring of annulus. A noticeable improvement over the original 1.618 for radial coloring.

      14. Below are the colorings of the annulus with the number of colors from 7 to 12. I think that some of them can be beaten. For the number of colors from 3 to 12, the upper bounds obtained by coloring the graph placed inside the annulus are {1.286, 1.456, 1.710, 1.785, 1.902, 2.01, 2.26, 2.495, 2.65, 2.9}. For a large number of colors, the bounds are quite rough.

      2. No, I’m solving a slightly different problem. The outer radius of the annulus must be the same as the upper value of the forbidden distance range.

      3. Oh, gotcha. Yeah, I can’t beat the simple ring of 12 tiles. You can permute the colors slightly to add in some notches (like in the image above), but then other constraints conspire to keep sqrt(3) as the maximum.

      4. Adding in 2 consecutive notches would increase the radius, but then I can’t properly re-color

      5. Below are the colorings of the annulus with the number of colors from 7 to 12. I think that some of them can be beaten. For the number of colors from 3 to 12, the upper bounds obtained by coloring the graph placed inside the annulus are {1.286, 1.456, 1.710, 1.785, 1.902, 2.01, 2.26, 2.495, 2.65, 2.9}. For a large number of colors, the bounds are quite rough.

    3. The simulator shows that there is a better 8-color tessellation of the plane, such that tiles of the same color have the same shape. It is possible to obtain an interval of forbidden distances [1, 1.431], although it needs to be refined. The corresponding tessellation is shown below. This is the first (and so far the only) tessellation that beats the tiling of the plane with identical hexagons. Let me remind you that if the tiles of all colors have the same shape, it is possible to obtain an interval of forbidden distances [1, 1.4].
      It would seem that this gives a chance to get a tessellation for 10 and 11 colors with an interval wider than [1, 1.732]. But so far I haven’t been able to do it. Perhaps, in order to solve the problem of 10 and 11 colors, one should consider tessellations in which the number of tiles of different colors differs.
      Any ideas?

      Reply

      1. Wow, that’s a big improvement!

        I am hopeless at proofs, but I think we can say that a crude upper bound on the distance is Sqrt[3]*(Sqrt[k] – 1)/2, which is the distance between regular hexagons placed on a triangular grid so that they cover 1/k of the plane (and oriented so as to maximise the distance, of course). That’s {0.633975, 0.866025, 1.07047, 1.25529, 1.42526, 1.58346} for k = 3 through 8, so I guess there could be further improvements. Can you use your annulus trick to get the simulator to look at distances less than 1? It would be mighty cool if k=5 could be improved that way.

      2. I don’t know yet what trick you’re talking about. I tried in the simulator 5-coloring. And it gives 0.88 for the configuration below. But I’m not sure that this is the correct result. We’ll have to see what FindMaximum[] says. Or do you mean something else?

      3. Ah, apologies, I was confused – I thought you were exploring the size of annuli as a way to discover improvements in the distance for k-tilings of the plane – now I understand, those are unrelated.

        This design looks pretty interesting, for sure. Shouln’t the long purple-green and purple-orange boundaries be bending the other way, though (making the purple tiles convex?

      5. I think that in this case it is not necessary to pay attention to the bend. Moreover, there is an overlap of tiles with the opposite bend. It can be seen on the example of purple and orange tiles.

      6. In my opinion, this figure is enough to show that the distance between tiles of the same color cannot be more than \sqrt3/2:

      7. Can we show that similar hexagons are unavoidable for any 5-color tessellation that maximizes the distance between tiles of the same color?

      8. I’m not convinced. My main difficultty is that the yellow/green/orange and blue/green/orange points within the hexagon are strictly in it, which I think means we can compress the tiling horizontally and obtain a slight improvement. Also, if the logic is true, there must be a bug in the simulator, which Tom has been using without incident for some time, or else he has used it wrongly. I think we could do two things: first, Tom could try to reproduce Jaan’s simulation and see whether he too gets 0.88 (which is more than Sqrt[3]/2 for anyone who’s not paying attention :-)), and second, we could do a check with FindMaximum.

      9. I think the figure gives more visual proof.
        Red segments connect identical green-orange-purple vertices. It can be seen that exactly two tiles fit in each of the red segments. Otherwise, the distance between the tiles in these directions cannot exceed half the length of the red segments. But the latter are inscribed in a hexagon (shown in black), whose sides cannot be greater than one. (Since the tiling is symmetrical, one more red triangle can be inscribed in the same hexagon.) One cannot deform this hexagon in such a way that all red segments become larger than \sqrt3 at the same time.

      10. Regarding the .88 from the simulator: there may be some edge-vertex distances less than .88, since the simulator is only enforcing vertex-vertex constraints. The simulator was designed just for the avoid-unit-distance constraint. I modified it so the minimum inter-tile distance can be adjusted, but this causes strange curved edges to be drawn. And edge-vertex distances can’t be ignored as easily.

        I can update the simulator to fix some problems, but not until Feb 13 at the earliest.

      11. I’m very busy today so I don’t have time to do the FindMaximum thing (or anything else), but I still feel that there is no restriction to squashing the tiling horizontally, so that the top and bottom corners of your black hexagon are slightly less than 120 degrees and the other corners are slightly more thn 120 degrees. Then the horizontal red line is indeed less than Sqrt[3] long, but that doesn’t seem to force us to bring any pair of tiles closer together than Sqrt[3]/2.

      12. Ah… maybe it does – the green/orange boundaries must all be vertical, mustn’t they, and their y-coordinate extents must overlap… OK maybe I am convinced after all 🙂

      13. Horizontally, the length of the red segment is equal to the sum of the lengths of the yellow (or blue) and purple tiles.

    4. I stumbled upon the following conundrum related to the tightest hex tiling in 6 colors, for which I got a distance of about 0.9920765. A very similar tiling is mentioned by Ivanov. But he gave an estimate of the distance \sqrt{2+\sqrt{2+\sqrt3}}/2\approx 0.9914449, and he got it on the lattice given by the vectors (2+\sqrt2, -\sqrt2) and (1, \sqrt3). I can’t figure out where he got that lattice from. I thought that it occurs if the distance between tiles in a row is 1 instead of d, but in this case I get \sqrt{(20+\sqrt{57})/7}/2\approx 0.9919288.
      Aubrey, could you do an independent check?

      Reply

      2. Jaan sent me the paper, which is only available in Russian, but Dr. Google helped. (Reference 37 in the very recent paper that Domotor highlighted is not a translation, it is basically the introduction and most of the results but no method – it seems to be the abstract for a conference talk.) The paper looks at R^3 as well as R^2, but I haven’t delved into that part. For R^2 it gives bounds for various k based on only using regular hexagons; I notice that the bound stated for k=19 uses a sublattice with discriminant only 17, so that seems to be an error. But as for k=6, yeah, he seems to have pulled that lattice out of the air. Also, the sublattice seems to be wrong – I think the bottom row should be (1 2) not (2 1). And I agree with your numbers (0.9920765 and 0.991928). So I think he just made a mistaken assumption in coming up with his lattice – I’m guessing he didn’t have Mathematica… but exactly WHAT assumption is unclear – I tried changing the other inter-tile distances to 1 instead of d, and various other “deliberate mistakes”, but none of the permutations I checked gave me Ivanov’s number.

      3. Great! Aubrey, thanks for the detailed analysis. Should we ask Ivanov himself? What do you think? (Although something tells me that he no longer remembers how he got this lattice.)

      4. I don’t really think there’s much need. You need to mention his lattice when you provide your own value, since the design is the same, so I think you can just mention that he evidently made an unknown and sub-optimal assumption in determining the best lattice.

    5. I can’t say that the results provided by FindMaximum[] look quite reliable.

      I did the calculations for some annuli. For the number of colors from 5 to 8, the estimates are {1.691391, 1.732050, 1.847759, 1.940392}. For 9 colors, I found a new tiling with a distance 2.175091. But for the previously considered tessellation with 10 colors, the distance estimate decreased from 2.213 to 2.159658. For 12 colors the distance is 2.425826.

      For the 8-coloring of the plane, I got a distance 1.41799, which is also less than 1.431 obtained by the simulator. (There are clearly bugs in the latest version of the simulator, and we have to wait for Tom to fix them.) I used a simplified version of the tessellation shown below. However, it required 21 vertex-to-vertex constraints and three constraints between a point and a line. If I leave all the inequalities as they are, I get less than 1.4. Only after replacing some inequalities with strict equality is it possible to obtain an estimate greater than 1.4. Maybe I’m doing something wrong with the FindMaximum[] function?

      Reply

      1. I’ve had strange experiences with FindMaximum too – I think it does a lot of guessing when there are lots of inequalities. I’ll try the 8-colouring of the plane myself in the next few days and we can see whether we agree.

      2. OK, I’ve had a go at this. As Jaan found, Mathematica’s FindMaximum function really struggles with systems this complex, but it can be babied into giving trustable values by iteratively removing inequalities, determining which ones come out as equalities, changing them to explicit equations and reintroducing removed ones. I was able to get a value of 1.418291 by playing with WorkingPrecision. Jaan – I noticed that the distance between (for example) tiles 4 going low left to high right can be optimised by making the 4-5 boundary wavy, so I enforced a distance of k to the midpoint of that boundary rather than to the straight line; could that be why I got a slightly better value?

        My full set of values is as follows:

        k -> 1.41829100511337946600,
        xx -> 1.18343744297553699063,
        yy -> 2.06562923105276663449,
        x128 -> 0.234853562137842392099,
        y156 -> 0.97203076307039160131,
        y3478 -> 0.316525861579758593933,
        x167 -> 0.307497959353990490960,
        y167 -> 0.798946861661498863860,
        x178 -> 0.474291940418847313143,
        y178 -> 0.388536303201308330646,
        t -> 0.221396232771008338869,
        u -> 0.847411649280606860124,
        v -> 0.252895707823565796257,
        w -> 0.829681277734705791005

        Here, xx and yy are the x- and y-coordinate offsets of the repeats of the tiling, and the origin is placed at the midpoint of the 1-2 boundary. The other values should be obvious from the names, referring to Jaan’s tile-numbering, except that (t,u) and (v,w) are the points on the 1-6 boundary that are the altitudes from the 1,2,3 and 2,3,6 corners. In the end I am enforcing that the following expressions are zero:

        y156^2 + x128^2 – 1
        y3478^2 + (xx – x128)^2 – 1
        (y178 + y3478)^2 + (xx – x178)^2 – 1
        (xx – x167)^2 + (y167 – y3478)^2 – 1
        (xx – x178)^2 + (yy – y156 – y178)^2 – 1
        v(y156 – y167) – x167(y156 – w)
        x167(xx – x128 – v) – (yy – w)(y156 – y167)
        (xx – x128 – v)^2 + (yy – w)^2 – k^2
        t(y156 – y167) – x167(y156 – u)
        x167(t + x178) – (u + y178)(y156 – y167)
        xx – x178 – k/2
        xx + x128 – k
        (xx – x167)^2 + (y3478 + y167)^2 – k^2
        (t + x178)^2 + (u + y178)^2 – k^2

        and I verified that all the following expressions come out positive:

        1 – y167^2 – (x128 + x167)^2
        1 – (x178 + x167)^2 – (y167 – y178)^2
        1/2 – x178
        1/2 – y178
        1 – x167^2 – (yy – y167 – y3478)^2
        1 – (xx – x167)^2 – (yy – y156 – y167)^2
        1 – (xx – x167 – x178)^2 – (yy – y167 – y178)^2
        (xx – x128)^2 + (yy – y156)^2 – k^2
        (xx – x128 – x167)^2 + (yy – y167)^2 – k^2
        x178^2 + (yy – y178 – y3478)^2 – k^2
        xx + x167 – k
        x167^2 + (yy + y3478 – y167)^2 – k^2
        (xx/2)^2 + (yy/2 + y3478)^2 – k^2
        x178^2 + (y156 + y178)^2 – k^2
        (x167 + x178)^2 + (y167 + y178)^2 – k^2

        I think these two lists jointly cover the required constraints. I haven’t yet persuaded Solve to give me an exact expression for k, but I will keep trying.

      3. Thank you, Aubrey. I confirm that your solution is correct, i.e. does not violate the constraints. (Though I haven’t been able to get one myself yet.) Also, I’ve noticed that this solution doesn’t require the wavy sides you mentioned.

      4. Great. About the waviness, yeah, I couldn’t be bothered to check whether the angle 3478 – 267 – 167 (for instance) was actually acute, since the constraint on the midpoint suffices.

        But if that isn’t it, then either I have missed (or mis-implemented) a constraint or you have included an unnecessary one (or mis-implemente one). I hope you can compare our implementations and figure out the discrepancy.

      5. After I rewrote the constraints in a slightly different way (I added one more variable), I finally got a solution close to yours: 1.418291004750938. Your 1.418291005113379 doesn’t want to appear. But now the solution is much more stable and does not require equalities.

    6. To get a hint for the 10 color case, I got some solutions on the edge of SAT-UNSAT using SAT-solvers. With the same sets of forbidden distances for 9 colors, a UNSAT solution is observed. The results are shown below. All this is very similar to the optimal 9-coloring interspersed with the 10th color. Moreover, this color is located somewhat irregularly, with a slightly different step and at an angle to the hexagonal grid, along which the other colors are located. Can we reproduce something similar using the FindMaximum function?



      Reply

  25. One more thing. I realize this is not the right place for my question. And yet, maybe someone knows the answer (maybe Domotor)? What is the current status of Goldbach’s (binary) and pairs of prime twins problems?
    On the arXiv.org site, I found almost a dozen articles that claim that these problems have been solved. True, I did not study them carefully. It’s funny that the authors of many of them do not quote each other.

    Reply

  26. Tom did a fantastic job refining the simulator. New tools added, bugs fixed. Now, for many tilings, the calculation results coincide with the estimates obtained in Mathematica. Differences can be observed if there are vertex-edge constraints, and there are vertices on both sides of the edge that cause this edge to bend in opposite directions.

    Reply

    1. I have found non-trivial tessellations for the number of colors 14 and 15, which beat the hexagonal tiling with 13 colors. (Hexagonal tilings with 14 and 15 colors that do this could not be found.) For 15 colors, the minimum distance estimate in version 6 of the simulator has dropped to 2.357. Version 4 had 2.388. In FindMaximum I get 2.346969. The remaining difference is probably due to the presence of edge-to-edge constraints, which are not taken into account in the simulator. In the picture below a pair of colors orange-black has such edges.

      Reply

      1. Hmm, I think the rule for the simulator would be this:

        If a line between an orange vertex and black vertex crosses an orange-black edge from other tiles, the vertices must be at least 2R distance apart. (R is the minimum distance between tiles of the same color).

        Proof: The length of the line is the sum of “distance between orange tiles” and “distance between black tiles”, so R+R is the minimum distance.

        This constraint holds regardless of how the tile edges are curved.

        I’ll have to think about how to implement this for the simulator without considering millions tile-edge-tile combinations. Probably a button that you can press to add in these constraints dynamically, once your graph has approximately the correct shape. Only tile-edge-tile constraints that are violated or nearly violated would be remembered.

    2. For 14 colors, the situation is reversed. The new version of the simulator gives 2.250, while FindMaximum gave 2.260808 (the previous version of the simulator gave about 2.261). This is a reason to look for an error in the formulation of the problem in Mathematica.

      Reply

    3. White spots remain, in particular, the numbers of colors 5, 10, 11. So far, it has not been possible to find tilings that would beat hexagonal tilings with a smaller number of colors in terms of the distance between tiles of the same color. The best hope is to advance here on the tiling with 11 colors, since there are already 2 additional colors compared to the 9-coloring. However, I haven’t been able to make progress here yet. Any ideas?

      Reply

      1. We should (?) also be looking for improvements when the best is a hexagonal tiling with nearest distances being corner to corner. I can’t even satisfy myself that regular hexagons are best for k=3 (i.e. d=1/2). Can that be shown?

      2. So far, I can only say that in the class of hexagonal tessellations with the number of colors 37, 75, 93, 112, 148, 171 (I did not check more than 200) for any tile shape (including a regular hexagon), there is a tiling with a smaller number colors, which provides the same or greater distance between tiles of the same color. For example, the number of colors 75 is in the line of tiles you are talking about, 37 is close to that line. It’s funny that the 49-coloring beats itself (because there are two such tessellations with regular hexagons).

      3. Thanks. I was also thinking of cases like k=7 where it’s not the simple (3/2 * Sqrt[k/3])-1 but it’s still corner-to-corner.

        Concerning k=11, how about taking your nice new k=15 tiling and merging pairs of tiles that surround the octagons?

      4. In this case, the octagon will turn into a quadrilateral? I don’t think it will work.

        Please explain in more detail your idea about k=7.

      5. Right, quadrilaterals. I agree it probably won’t work, but it’s worth a try.

        I don’t have an idea for k=7. I only wanted to highlight that we should continue to be aware of the possibility of improvements beyond hexagons for those k that do beat k-1, not only for those that don’t. Your discovery for k=8 was an example of that, of course.

    4. Blank shot. I thought it was breakthrough in 11-tiling. The simulator showed 1.755, but Mathematica said no, 1.73205. Obviously, this is due to the limited tiling area in the simulator.

      Reply

      1. That’s such a beautiful tiling. So intricate and yet so symmetrical. Awesome!

        I’m getting a very slightly larger value for d, 1.44526. Did you include any vertex-edge constraints? I don’t think any are needed other than those like 1-5, necause the other potentially problematic boundaries (such as 6-8) can be curved safely if needed. FindMaximum is definitely not behaving stably for me, though, so I may well be wrong.

        Meanwhile I think there is hope for an exact expression in this case – considerably fewer constraints than in the earlier k=8 tiling. Working on it!

      2. Thank you. My results are also unstable. I’ll try to change problem statement in FindMaximum.

      3. I reduced the number of variables to seven and got d=1.444157346767. The result looks stable. All diagonals of pentagons have unit length.

        The simulator behaves interestingly. In my case, there are about 12 tiles of each color, occupying something like a rounded rhombus on the plane, close to a square. I quickly get d=1.441, for 1.442 there is only a small area near the sharp corner of the rhombus remaining problematic. If I remove a few tiles from this corner, then the distance comes to 1.455. Obviously, due to the fact that the vertex-edge constraints are not taken into account.

      4. I want to draw attention to the fact that in some cases the simulator seems to hang on the local optimum and cannot find the global optimum.

      5. Great job. But just to be 100% sure – are you really saying that in your optimal tiling the distance between (say) 245 and 568 is 1? I ask because in your original picture it seems to be perceptibly shorter than the other diagonals. (I’m visualising the altitude drawn from 245 to the 5-6 boundary: it will clearly meet it much closer to 568 than to 156.)

      6. Ah – I now find that in my careless assumption that 245 to 568 was way less than 1 I was not actually constraining it to be less than 1 at all, and my result of 1.44526 has it at 1.08. So I am pretty sure your latest result is correct. However, could you please list your variables and constraints, so I can do a more rigorous independent verification?

      7. Yes, sure. The origin is at point 128. Other variables:
        d = 1.4441573467677319,
        128: 2.42061914586747543,
        258: (0, -0.46769554766798844),
        568: (0.5, -0.74573968474856105),
        156: (0.21569041448078315, -1.4441573467677319)

        It’s funny how my estimates are usually too low and yours are too high. But in the end we come to the same results. This inspires confidence in their correctness.

      9. The error was in an insignificant constraint.

        Internal constraints (not greater than 1):
        tile 5: 258-156, 245-156, 245-568,
        tile 8: 128-368, 128-568, 178-368, 178-568, 178-258, 568-478,
        tile 6: 568-236, 368-276, 568-267,
        The first four and the last one are exactly 1.

        External constraints (not less than d):
        tile 8: 38-128, 178-568,
        tile 5: 15-258, 156-245,
        tile 6: 568-167, 368-167
        The first three are exactly d.

      11. Update: I now confirm your latest value to arbitrary precision. Yay! I am still hoping to get an exact expression – I am currently working with a three-variiable, three-equation system and babying Solve (and related functions) to unpack it.

      15. OK, I’ve capitulated regarding getting an exact value. I got the system down to a single equation in one variable, but it’s a couple of screenfuls long and I’m out of ideas to use Simplify and friends to make it Solve-friendly. Whatever – now that we have consensus on the numerical value to arbitrary precision, I think we’ve done enough.

      16. In any case, it was a grandiose attempt.

        I think that in the case of k=3 it is impossible to get d>1/2. For reasoning, it suffices to take one tile of color 1 surrounded by one layer of tiles of other colors 2 and 3. If this layer contains two tiles of colors 2 and 3 each, then between the tiles there is an edge of length less than 1/2. Therefore, we need to take three tiles of colors 2 and 3 each, since with more tiles there will again be an edge of length less than 1/2.

  28. In case you aren’t a subscriber (hint!), you may be interested to know that the latest issue of Geombinatorics contains a lovely short paper by Jaan that very slightly improves the value of d such that a tiling with all distances 1..d excluded needs seven colours. Though the improvement in d is slight, the improvement in the simplicity of the proof is dramatic, since he examines only the vertices of a regular 18-gon of diameter 2.

    Inspired by this, I have been looking a little at ways in which the bound might be further improved, but I have a lot of distractions right now so I thought I would share a possible way forward. Since we are looking at tilings and intervals, we can assume that no more than three tiles meet at any point, and we can consider the points where three tiles meet to be trichromatic (I’ll call them the TPs from now on). My focus is: in a hypothetical 6-tiling of the plane, what can we say about the distance between TPs that share certain numbers of colours?

    It is immediate that in a hypothetical 6-tiling there can definitely be no two TPs that share zero colours and are less than 2 apart, since then the points at 1 from both those TPs must use a seventh colour. But we can also say that no two TPs that share exactly one colour can be less than d^2-1 apart. To see this, draw the unit-radius circles around two points that are (say) 0.6 apart; there are segments of those circles that are between 1 and d from the other TP, so will be forced to be the one colour not used by either TP, hence we need the points at 1 from one TP and d from the other to be less than 1 apart. They form an isosceles trapezium with the two TPs, whose diagonal is d and three of whose edges are 1, giving the bound on the fourth edge.

    Also, by the same construction, we can exclude the distance range Sqrt[4-d^2]..Sqrt[1+2d^2], since if the distance between two TPs is in that range then the two colour-forced regions on the unit-radius circles will contain points at a prohibited distance from each other. (The lower bound is when the distance between the two points where the circles intersect is equal to d; the upper bound is the long diagonal of a parallelogram with edges 1 and d and short diagonal 1.)

    So, well… in the Isbell tiling, TPs sharing exactly one colour are Sqrt[3] apart, which doesn’t lead to an interesting d. But… of course TPs sharing zero colours are Sqrt[7]/2 apart, which is less than 2. So I’m wondering whether there might be a way to link the two – to show that in any 6-tiling (Siamese or otherwise), if TPs sharing zero colours are kept 2 apart, there will be some pair of TPs sharing exactly one colour that are at a distance that leads to a reduction in the bound on d. Any ideas?

    Reply

    1. Ah, in fact that last bound Sqrt[1+2d^2] can be improved to Sqrt[4d^2 – 1], which is the long diagonal of a rhombus with edges d and short diagonal 1. That’s because actually the furthest points that must be less than 1 apart are those that are d from both TPs.

      Reply

    2. Plus, forgot to mention: obviously no two TPs can be between 1 and d apart, because then they must not share any colours, so the points at unit distance from both must be a seventh colour.

      Reply

  29. Jaan and I did some work on hexagonal tilings that has become a paper. We just missed the July issue of Geombinatorics, so it will appear in October, and meanwhile it is here:

    https://arxiv.org/abs/2206.12635

    Also there is a very cool paper in the July issue, from a couple of people at Berkeley and Stanford, that improves the lower bound on the size of a k-chromatic UDG for k=5 and 6, by adapting our “probabilistic approach” so as to look at edges rather than vertices as Pritikin did. Check it out! I’m currently looking at ways to extend their method.

    Reply

    1. If we apply the results of the work of Peter and Domotor

      https://arxiv.org/abs/2006.06285

      to their estimates of the number of edges, then we can immediately raise the estimates for the number of vertices to 28 and 41, respectively. I think that for k=6 one can try to suggest a better tiling. (But here I still have difficulties with the calculation of integrals.)

      Reply

      1. I didn’t know that paper! Lovely results in it. Plus it led me to learn the {} notation for “fractional part”. I also get 41 using Proposition 12 when I use the new paper’s value of 178, but I have confirmed with the authors that actually their p_4 in the table is what they meant, and that gives 181 (not 180, as they accidentally put the floor not the ceiling – their k=4 should similarly be 99 not 98), and in fact it can be improved to 182 by using Croft’s tortoises in Lemma 6 instead of circles. So we are up to 42.

        As for k=6 I too am only now learning how to use Mathematica’s integration functions. I’m getting there though – I have now reproduced the k=3 result, and I too am hoping for a more impressive value than 42 using good 5-tilings rather than their Lemma 6. Same goes for k=7, for which Lemma 6 obviously does far less well than Pritikin’s 6197 and your 6992.

        Domotor: I see that for several vertex counts you show a graph with an edge count of exactly Floor[v^(4/3)], including |v|=30. Do you have any other than the examples for |v|=15 and 16 that beat Floor[v^(4/3)] ?

      2. I don’t like the {} notation for the fractional part, as it is usually reserved for sets.
        I have already asked a similar question. We have to ask Peter. But it looks like the answer is “no”. Also note that in all cases the number of edges does not exceed Ceiling[n^(4/3)] for n-vertex graph.

      4. Hm. So far I’m getting the optimum p_4\approx 0.01228 with the optimum diameter around 1.0916. Looks like there’s an error in the equations somewhere.
        But how do you take integrals? The most convenient way would be to use the function ArcLength[RegionIntersection[Circle[x,y],Polygon[…]]], but this construction does not want to work inside NIntegrate[]. One could use NSum[…] as an approximation, but it comes out pretty rough.
        Now I’m looking at all the arcs centered on a regular hexagonal tile that intersect this tile and neighboring tiles of the same color. In total, up to 4 arcs of various types are typed. Each arc is specified by the ends, which are described by the ArcSin[] function with rather long arguments. But maybe I’m overcomplicating it, and is there an easier way?

      5. Hmmm. I can’t find an error in my integrals. With diameter 1.0916, the contribution of the outer tiles is 0.00671, the contribution of the same tile is 0.00557.

      6. I’ve basically got it working. I had not discovered ArcLength so I did it the complicated way with ArcSin, but I managed to get the arguments reasonably simple, and I have reproduced the paper for k=3 and k=4. (I couldn’t get NIntegrate to work inside NMinimize, but it was quick enough to do that part manually.) I’ll email you my notebook. I tried the 5-tiling with hexagons from our latest paper and it is actually worse than k=4 (I get 0.0125134), even with full flexibility of hexagon coordinates, so something else is needed there – I think probably an adaptation of the paper’s Lemma 6 taking into account the existence of regions that cannot contain a vertex of a mono edge. I’ll try the quasi-Pritikin tiling next.

      7. OK, so in turns out that this approach considerably improves the lower bound on the number of vertices in a (hypothetical :-)) 7-chromatic UDG. Optimising the shape and size of Pritikin-esque pentagons gives me a lower bound on |E| of 465292, which when using Peter’s/Domotor’s new result translates into |V| at least 10857. I’ve put my Mathematica notebook in the dropbox (“7chrom-order.nb”) – it also has code for smaller chromatic numbers. Today I will try the method on the 6-tiling with hexagons that Jaan and I discussed in our recent paper; I have a feeling that that will do even better.

      8. Bah, false alarm, turns out I dropped a factor of 2 in the integration, so the real “new” lower bound on the order of any 7-chromatic UDG is 6456, still beating Pritikin but not beating Jaan’s 6992. Thanks to Jaan for spotting this!

  30. Hm, I’m not sure why my latest comment didn’t appear, it doesn’t have any links in it – anyway, I was just reporting that Jaan found an error in my code that gave the new 10857 bound and it is actually only 6456, which is inferior to the 6992 he achieved a year or two ago.

    Reply

  31. Greetings. It can be considered that each color interacts only with itself with such a force (electromagnetism) that at a distance of 1 equals 0. Initially, there will be only the potential energy of the system. From the principle of least action (by varying the action S), write the Hamilton equations. In the case of 4 colors, the minimal 4 uncolorable graph should exhibit symmetry with respect to a rotation of 120 degrees, which is confirmed by the “cluster” coloring of the minimal graph, where there is only one point of the fifth color. This may help in finding the 5 uncolorable graph.

    Reply

    1. Thanks Domotor – wow, at last! And I see they say they have already made further progress – it will be terrific to see how close they get to the Croft lower bound. I see you are acknowledged – maybe you could persuade one of the authors to start posting here?

      The frustrating thing for me about the paper is that the method with which they got there involves a lot of maths that I don’t know (about autocorrelation functions and so on), and they eventually say at the end of section 4 that all that maths should theoretically be superfluous, but that empirically it is not, and they (implicitly) don’t know why. I am assuming, for example, that the FCN of their 24-vertex graph is not 1/0.247, and indeed is less than 4. Is there a simple way to understand the relationship between the method that worked and the FCN-based method?

      Reply

      1. There is some difference, a lower bound for FCN translates to an upper bound for the measure of a 1-free set, but not the other way around. I know that the authors are working on trying to get a graph with FCN>4 from their constructions, but so far no success.

      2. Thank you for your interest, Aubrey, and thank you for the plug, Dömötör!

        We will try to improve the presentation of our paper before submission, but I think I can explain where the improvement comes from, and the relationship to FCN. Upper bounds for the density of 1-avoiding sets have previously been achieved by two different methods. One was to construct UDGs with high FCN, and the other was an optimization technique based on Fourier analysis. In this paper we basically merge the two approaches.

        We have a hierarchy of linear programs. Lemma 1 in our paper leads exactly to the density-bound that you would get from the fractional chromatic number of the graph $X$. (You can write up the LP corresponding to Lemma 1 and see that it is basically the same as the LP defining the FCN.)

        The next step in the hierarchy is averaging: for a subset $Y\subset X$ we average the densities $\delta(\cap_i (A+y_i))$ over all rotated versions of $Y$, so that it becomes invariant to translating and rotating $Y$. For any pair of congruent subsets $Y_1 \cong Y_2$, writing up this invariance gets us an extra linear equation that we can add to the fractional chromatic number LP. This is the step where geometry enters the picture, besides combinatorics. If our witness point set $X$ has lots of congruent subsets, these equations help a lot in bringing down the bound for $\delta(A)$. You can see these extra conditions in our paper at equation (ieC).

        The last step of the hierarchy uses the tools from Fourier analysis that are standard to use here. The details of this may require a bit more work to understand (although nothing very deep is being used). The main point is that the autocorrelation function $f(x)=\delta (A\cap A-x)$, after averaging, becomes a radial function which can be expressed in analytic terms, and this leads to further linear constraints.

        It is kind of nice that we needed to use combinatorics, geometry and analysis to get the bound below 0.25.

        As long as $X$ has up to around 30 points, we can still solve the LPs, as the number of variables is not too large.

        In the end, the question is how to find a good witness UDG $X$. Currently, we do a huge beam search for $X$ based on the $\delta(A)$ bound that it gives. We start the search from the Moser spindle, and only add vertices that are unit distance away from at least two already included vertices. We are currently investigating some other ideas of constructing even better examples of $X$ (e.g. an $X$ that has large FCN to begin with).

      3. Thank you Daniel! (And I see you are not yet conversant with the peculiarities of WordPress’s corruption of LaTeX, but that was still legible.)

        It would certainly be interesting to do your beam search starting from graphs other than the Moser spindle. You may not be familiar with Jaan Parts’s fantastic discovery of a way to prove CNP!=4 without computational help; he did it by starting from a “double Golomb” graph, i.e. a 13-vertex thing with two inner triangles. The cool thing about that graph is that there are 12 non-vertex points lying unit distance from THREE of the 13 vertices, and that every 4-colouring that has a monochromatic triangle in the unit-edge hexagon has at least a couple of those points lying unit distance from three differently-coloured vertices, such that adding such a point as a new vertex does not increase the number of cases (the colour of the new vertex is forced). Jaan was able to show that, for every such initial colouring (there are only 30-odd), this process can be continued until a point appears that is unit distance from all four colours, with only a couple of exceptions where a split does need to be made (i.e. where a point must be added that is unit distance from only two colours). If you don’t have the paper, email me at alwaysmyself@mail.com (not gmail) and I’ll send it. It seems to me that you’d have a good chance of looking at much bigger graphs in this setting.

      4. Here you go. I missed everything again. Need to come here more often.

        Just in case, I note that a year or two ago I got FCN about 3.99. The corresponding graph had more than 1000 vertices (I need some time to remember the details).

      5. My best FCN score is 3.9898059 on a 1057-vertex graph (about 10^6 seconds for last iteration of LP/ILP).

      6. Jaan, that’s shocking. 3.99? Looking at the “convergence” to 4, some on our team conjectured that the FCN of the plane is exactly 4. That would mean that the extra things that we did to go below 1/4 were really necessary.

        There were basically two extra ideas: 1. the congruence constraints based on radialization, that can exploit the geometric structure of the independent sets, 2. the Fourier apparatus. We don’t have a team consensus on whether the congruence constraints are themselves enough or not. In the next, yet unpublished version of our preprint, we define a Geometric Fractional Chromatic Number (GFCN) that’s FCN plus the extra congruence constraints. Using that terminology, m_1(R^2) <= min_G 1/GFCN(G) 4 graphs right now. But nothing so far, so far it seems that the Fourier apparatus is also needed.

        Dear PolyMath16 community, tomorrow 2PM (Central European Time) we will present our paper at the Geometry Seminar of the Rényi Institute:
        https://coge.elte.hu/seminar.html

        “Zoom link for the online lectures: https://zoom.us/j/96029300722 and the password is the first 6 terms from the Fibonacci sequence starting with 11.”

      7. The greater sign got interpreted as html in my previous post, making the post unintelligible. Here is the affected paragraph again, hopefully surviving now:

        There were basically two extra ideas: 1. the congruence constraints based on radialization, that can exploit the geometric structure of the independent sets, 2. the Fourier apparatus. We don’t have a team consensus on whether the congruence constraints are themselves enough or not. In the next, yet unpublished version of our preprint, we define a Geometric Fractional Chromatic Number (GFCN) that’s FCN plus the extra congruence constraints. Using that terminology, m_1(R^2) ≤ min_G 1/GFCN(G) ≤ min_G 1/FCN(G), and the big question is where does 1/4 fit into that chain of inequalities. Our computers are searching for GFCN≥4 graphs right now. But nothing so far, so far it seems that the Fourier apparatus is also needed.

      8. Well, I think FCN=4 is for \mathbb{Q}[\sqrt{-3},\sqrt{-11}], not for the entire plane. Another thing is that going beyond this field significantly reduces the “efficiency” of the graph. In the calculation method used (Bellitto’s method), the order of the graph is very critical, and it is not possible to significantly increase the number of vertices with an acceptable calculation time. However, even for 1000 vertices, the computation time is already huge. The number of iterations of the computational procedure for such a graph is several thousand, and without additional tricks I would never have completed them. Moreover, it is necessary to sort through a lot of graphs in order to find the most efficient one in terms of FCN.

        I have questions about your work. I sent you an email. Please check your mail when you are free. It may have gone into spam.

      9. What order of graphs are you using in your GFGN search? What GFGN values have been achieved so far? What do LP with congruence constraints look like?

      11. I may be forgetting key facts, but isn’t the FCN of a finite graph always no more than its CN? If so, FCN>4 requires working with 5-chromatic graphs, and we have hardly done that at all – they are big…

      12. Quite right. We have relatively small 5-chromatic graphs, but they give mediocre FCN values.

  33. Here’s an unrelated musing. I wonder if there is a case for generalising/systematising our work on regions of R^n. It has only just occurred to me that there is a nice way to describe strips, discs and sphere surfaces as examples of two parametrised questions:

    what is the largest (resp. smallest) d for which k colours can (resp. cannot) properly colour the subset of R^n defined by the constraints:

    – the sum of squares of coordinates 1..v equals d^2
    – the sum of squares of coordinates v+1..w is at most d^2
    – coordinates w+1..n are unconstrained

    ? (And of course the usual optional constraints of block structure and scaleability.)

    So then strips have v=0, w=1, n=2; discs have v=0, w=n=2; and the surface of a sphere has v=w=n=3. But we also get cases like the surface of an infinite cylinder (v=w=2, n=3), the interior of an infinite slab (v=0, w=1, n=3), the union of two parallel discs (v=1, w=2, n=3) etc. Seems like there’s likely to be a number of {k,v,w,n} that are yet unexplored and turn out to be interesting.

    Reply

  35. Hey all – OK here is a massively cool idea from James Davies, the same guy who did this amazing proof of the odd-distance thing that I mentioned recently.

    Suppose we 3 (yes 3)-colour the plane, obviously not requiring no edge to be monochromatic, but instead requiring that there be no ODD-LENGTH CYCLE that is monochromatic. If we could do this, we would immediately have a proper 6-colouring of the plane, because we could replace each colour with two colours and we’d be OK because each cycle that used to be mono is of even length so is now properly coloured.

    So… can we? Well, the way James began was just to tile the plane with stripes of width 1/2, and even that is enough to give a minimum odd cycle size of 15, basically by the same construction as in our paper for k=3 on strips. Question is, can we improve this arbitrarily? – not just with strips, of course. We pretty much convinced ourselves today that any such thing would be non-measurable… but … any ideas?

    Reply

    1. Is there an example of a non-measurable (“speckled”?) coloring using a finite number of colors? (one where the specific speckling pattern is important)

      Reply

      1. Hm, exactly the right question. I don’t know, and I can’t immediately think of one – speckings are altogether harder to visualise than tilings… I will relay this question to James.

      2. There is an example of such a coloring of the sphere, for which the points at a unit distance correspond to orthogonal vectors. https://arxiv.org/pdf/1505.02514.pdf

        However, this example is still artificial, and the coloring in 9 colors is based on the octahedral 4-coloring.

      3. I don’t think such an example is known for the plane (at least not one that is meaningfully different from a tiling colouring).
        It would be very interesting to see one, even with 1000+ colours.

  37. Hey all,

    I’ve put slightly more thought into my remark from a few months ago about systematising the analysis of regions of R^n. I’m convinced that in the n=3 case there is quite a rich seam of work to be done.

    Recall that my suggestion (expressed rather poorly) was: partition 1..n into sets A,B,C and define our subset of interest as those points in R^n such that:

    – the sum of squares of the dimensions in A is exactly k_1^2
    – the sum of squares of the dimensions in B is at most k_2^2
    – there is no constraint on the dimensions in C

    and then ask for the bounds on the CN of this set as a function of k_1 and k_2. Since dimensions can be transposed let us just write |A| = a, |B| = b, |C| = c.

    Then everything is trivial when n=1, or when n=2 and a!=0 (circle, two line segments, two lines); when n=2 and a=0 we have three cases, namely the plane, the infinite strip and the disk, all of which are old news.

    But when n=3, the only cases we have studied are R^3 and the surface of a sphere (i.e. where c=3 and where a=3 respectively), and there are eight other cases, as follows (writing just “k” when either of a,b is 0):

    a b c
    0 1 2 infinite slab of thickness 2k
    0 2 1 infinite cylinder (+ interior) of radius k
    0 3 0 ball (i.e. sphere + interior) of radius k
    1 0 2 two infinite planes at z = +/-k
    1 1 1 two infinite strips of width 2k_1 at z = +/-k_2
    1 2 0 two discs of radius k_1 at z = +/-k_2
    2 0 1 infinite cylinder (surface only) of radius k
    2 1 0 cylinder segment (surface only) of radius k_1 bounded by z = +/-k_2

    (I’m unclear whether the term “cylinder” includes the interior or not in conventional mathematical terminology.)

    It seems to me that there is a wealth of fertile ground here. How thin does a slab need to be to allow colouring with only 14 colours, or 13, … 8? And so on. Shall we have a go?

    Reply

    1. This is a philosophical question. Here is what I think.
      There is nothing easier than to come up with a new object for research. But this object, probably, should be interesting either in itself or in connection with some of the previous objects studied. Can you remember how the interest in discs and stripes came about? I think that not least here was meant a comparison with the coloring of the plane (as the original object). Perhaps it was hoped that the study of these more limited objects would lead to the discovery of methods that could be applied to the original one. Or at least to see how much of a difference it makes if we use 7 or 6 colors.
      How can we be interested in these new eight objects? Keep in mind that the more options you can offer, the less valuable each individual option is, if only because we have limited resources. Why should we be interested in these particular objects? The addition of each new dimension, generally speaking, expands the possibilities compared to the classification that can be proposed only on the basis of an analysis of a case with a smaller number of dimensions. Say, why not add things like torus or swiss cheese?
      It should also be borne in mind that an increase in the number of dimensions inevitably increases the number of considered colors and variables of the problem, and increases its computational complexity. That is, one must be prepared for the fact that the results will be weaker. The same applies to the visual presentation of these results.
      I remember somewhere I saw results for a thin sheet, where the thickness tends to zero in the third dimension.

      Reply

      1. We can use the principle of least action, then in the case of 012 an upper bound: for thin slabs we can use a tiling in the form of hexagonal prisms so that the major diagonal is 1. Then for Izbel tiling we know that the diameter of the hexagon(d) is 2/sqrt (7) to 1. From a right-angled triangle in a prism, we find that for k on the segment [0,sqrt(3/7)/2] cn=7. Of course, exactly the same statement is true in the case of 102. I hope that is clear, since I am using a translator.

      2. All true! But think: you decided not long ago that the question of minimum distance between tiles in a k-colouring of the plane was really interesting… and that’s mighty similar to k-colouring of a slab for k in {7..14}. In general I think the motivation here is that the definition of the class of questions in R^3 is so natural an extension of the definition of the class in R^2 that has been such fun.

      3. That was a reply to Jaan; Aleksey, yes, you are saying the same. Jaan found an 8-tiling of R^2 with a distance exceeding 1.44, for example. (See higher up this page!)

    2. In case 102, when k belongs to the ray [sqrt(13)/8, infinite) cn=7, which is achieved for k>1/2 with any coloring, and in the case of k [sqrt(13)/8, 1/2] if you take Izbel tiling from one plane and copy it exactly opposite to another plane and shift the coloring along the edge of the hexagon by the diameter of the hexagon*sqrt(3)/4 and perpendicular to the edge of the hexagon by the diameter of the hexagon*3*sqrt(3)/8.

      Reply

      1. Right – the case 102 is more interesting than it at first seems. Do we even know that hexagons are the right shape?

  38. I came up with a problem that follows from the question, what is the minimum probability of the formation of an unit non-monochromatic-pair (or, if you like, a virtual edge) on an unit triangular (hexagonal) lattice, if unit monochromatic triangles are forbidden?
    I’ll write it again. We take a set of vertices located at the nodes of a unit triangular lattice. We color these vertices so that there are no unit monochromatic triangles. (We use any number of colors.) We determine the proportion of virtual edges among all pairs of vertices with unit distance. We are trying to minimize it. It turned out that a virtual edge can appear with a probability of 2/3. In other words, a mono-pair can appear with a probability of 1/3. But can the last one be greater?
    Instead of mono-triangles, one can forbid monochromatic sets of m vertices, for example, considering only the most compact and symmetrical configurations of such vertices. So, for m=4 it will be an unit rhombus, for m=5 a trapezoid, for m=6 a triangle with side 2, for m=7 a set of wheel graph vertices. What is now the minimum probability of the formation of a virtual edge? For m=4 I got 2/4, for m=7 it was 2/7. This hints at a law of the form 2/m. But for m=5 and 6, I still can’t find examples that give less than 1/2.

    Reply

      1. Great! This shows again that the computer is smarter than pencil and paper (at least in my case).
        I didn’t understand what a bowtie is. A set of vertices adjacent to at least one of two adjacent vertices?
        Have you done an exhaustive search? It turns out that for m from 3 to 9, only cases 5 and 8 do not obey the 2/m law. Interesting. We can correct our guess: the 2/m law works for all Loeschian numbers of the form (aa+ab+bb) for non-negative integers a and b. But also for some others like 6.

      3. My search was limited to two colors and repeated tiles of N vertices. The image above shows a 9×4 tile (36 vertices), where each row of tiles is shifted left 2 spots from the row above it. Each 9×4 tile is then replaced by a pattern of 0s and 1s. I think any repeated pattern can be represented like this (replacing 9,4,2 with the appropriate constants).

        My search considers all configurations up to N vertices (20 to 40 vertices depending how long I let it run for).

        Yeah, bowtie is 3+2+3.

      4. .gist table { margin-bottom: 0; } This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters On the A2 lattice (triangular lattice — each vertex has 6 neighbors), color the vertices such that the density of mono edges is maximized. An edge is "mono" if its neighbors are the same color. A "forbidden shape" is also provided. No set of vertices in this shape can be all-the-same-color. https://dustingmixon.wordpress.com/2021/02/01/polymath16-seventeenth-thread-declaring-victory/#comment-46576 O O . . . . . O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 density = 0.333333 domain = 2×1 offset = 0 O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 density = 0.333333 domain = 3×1 offset = 1 O . . . O . . . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 density = 0.833333 domain = 8×1 offset = 0 O O . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 density = 0.5 domain = 2×2 offset = 0 O O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 density = 0.555556 domain = 6×1 offset = 1 O O . . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 density = 0.5 domain = 2×2 offset = 0 . O . . . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 density = 0.416667 domain = 8×1 offset = 2 . . . . . . . . . . . . . . . O O . . . . O . O . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 density = 0.555556 domain = 6×1 offset = 1 O O O . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 density = 0.555556 domain = 6×1 offset = 1 O O . . . . . O . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 density = 0.666667 domain = 4×1 offset = 0 . O . . . . . O O . . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 density = 0.666667 domain = 4×1 offset = 0 . O O . . . . O . O . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 density = 0.666667 domain = 4×1 offset = 0 (This entry is wrong — correction is below) O O . . . . . O O . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (wrong) 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 (wrong) density = 0.555556 domain = 6×1 offset = 1 . . . . . . . . O O O . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 density = 0.625 domain = 4×4 offset = 0 . O O . . . . O O O . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 density = 0.714286 domain = 7×1 offset = 2 O O O O . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 density = 0.666667 domain = 8×1 offset = 1 O O O . . . . O O . . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 density = 0.714286 domain = 7×1 offset = 2 O O O O . . . O O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 density = 0.666667 domain = 8×1 offset = 1 . . O O O . . . O O O O . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 density = 0.777778 domain = 3×3 offset = 0 . . O O O O . . O O O O O . . O O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 density = 0.777778 domain = 9×1 offset = 2 . . O O O . . . O O O O . . . O O O O . . . O O O . . . . . . . . . . . . . . . . . . . . . . 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 density = 0.846154 domain = 13×1 offset = 3 . . . . . . . . . O . . . . O O O O . . . O O O . . . . O O O O . . . . O . . . . . . . . . . 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 density = 0.846154 domain = 13×1 offset = 3 . . . O . . . . . O O . . . . O O O . . . O O O O . . . O O O O O . . . . . . . . . . . . . . 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 density = 0.833333 domain = 8×1 offset = 0 . . . . . . . . . O O O . . . O O O . . . O O O . . . . O O O . . . . . . . . . . . . . . . . 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 density = 0.777778 domain = 3×3 offset = 0 . . . . . . . . . O O O . . . O O O . . . O O O . . . . O O O . . . O O O . . . . . . . . . . 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 density = 0.8 domain = 20×1 offset = 3 O O O . . . . O O O . . . . O O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 density = 0.777778 domain = 3×3 offset = 0 O O O O . . . O O O O . . . O O O O . . . O O O O . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 density = 0.875 domain = 4×4 offset = 0 . O O O O . . O O O O . . . O O O O . . O O O O . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 density = 0.875 domain = 4×4 offset = 0 . . O O O . . . O O O O . . O O O O O . . O O O O . . . . O O O . . . . . . . . . . . . . . . 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 density = 0.894737 domain = 19×1 offset = 7 . . O O O . . . O O O O . . O O . O O . . O O O O . . . . O O O . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 density = 0.862069 — checked N=2..38 domain = 29×1 offset = 8 . . . . . . . . O O O . . . O O O O . . . O O O . . . . . O O . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 density = 0.833333 domain = 6×2 offset = 2 . . O O . . . . O O O . . . O O O O . . O O O O O . . . O O O O . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 density = 0.875 domain = 16×1 offset = 6 view raw gistfile1.txt hosted with ❤ by GitHub I tested a bunch of shapes. Let me know if there’s more you’d like to see.

      5. http://bit.ly/3iH5t1h

        Sorry about the previous post — my link got expanded for some reason. Hopefully this link doesn’t create the same problem.

        Anyways, I tried a bunch of shapes and you can see the results at the link above. Let me know if there are more shapes I should try.

      6. Yes, this blog is a good illustration of the Russian proverb “what is written with a pen cannot be cut down with an axe”. Sometimes you really want to remove something, but you can’t.
        The new forms are very interesting. In particular, the 2/m law is confirmed for the Loeschian numbers 12, 13, 16, 19 (for compact symmetric forms).
        There are forms that get both more and less than 2/m. In this sense, I like the shape of the “small bow tie” 2-1-2.
        I would suggest studying the square lattice in a similar way.

      7. It seems that all connected convex forms (or only without holes?) give at least 2/m. One can try to look for a counterexample to this observation. (And at the same time find such a form with 2/m for m=13.)

  39. This is very cool. I think what we are now asking is: for each n starting at 3, for k colours, what configuration of n vertices in the triangular grid, when prohibited from being mono, minimises the maximum possible proportion of mono unit edges, and what is that minimum maximum? Does it even depend on k, or is k=2 always best? Tom’s finding of 5/12 for n=4 is quite surprising and shows that this is very far from being a trivial question.

    Reply

    1. Hmm, that’s a trickier question. And searching low-density grids is slower (there are a lot more of them!). I just manually picked a bunch of shapes to test. But, there are certain shapes I know can’t be best. For example, the n=6 triangle — A simple striped grid with bars two rows thick is possible, so we know the the mono-density will be at least .66666. Same for any shape which is “3 rows tall”. (So, maybe a better way to search is to enumerate grid patterns in density order, and see which pieces it eliminates — e.g. the 2-row-thick-stripes grid would eliminate the n=6 triangle.)

      Also, I updated the 3×2 rhombus shape — at N=16 (N=tile size) two new grid patterns had a higher density. See https://i.imgur.com/bb1ojQk.png

      For a lot of these shapes, grids at N>20 improve the mono-density. So my current results might be too high or too low: The best shape might be one that I didn’t try. Also, I might not have found the best density for each shape (if N>27 or whatever is required).

      Reply

    3. I’ve updated that last link a few times — you can see all the changes in the “Revisions” tab.

      The above image has the current top results.

      Reply

  40. There is a problem that might be interesting. Let there be a sequence of graphs \{G_m\}, where each next graph is obtained from the previous one by Minkowski summation with some fixed generating graph G. How to find the number of vertices of each graph of such a sequence or at least estimate the growth function in the asymptotic case?
    If we take a 7-vertex wheel graph as the generating graph G, then the number of vertices is explicitly described by the function 3m^2+3m+1. The same can be done for a 13-vertex graph formed from two wheel graphs with a common central vertex (it seems that the rotation angle is not important here): \frac32m^4+3m^3+\frac92m^2+3m+1. But for more complex graphs G, I have difficulty.
    For example, here is the sequence of vertices for a 19-vertex graph formed from three wheel graphs with a common center and rotation angles \pm\frac12\arccos\frac56: {19, 163, 715, 2113, 4957, 10009, 18193 , 30595, 48463, 73207, 106399, 149773, 205225, 274813, 360757, 465439, 591403, 741355, 918163, 1124857}. Can anything be said about this sequence? It seems that for large m, the order of the graph grows as O(m^4).
    Or here is the same for the angle \arccos\frac56: {19, 163, 865, 3313, 10099, 25765, 55747, 105889, 183127, 295645, 452491, 663787, 940681, 1295347, 1740985, 2291821, 2963107, 3771121, 4733167, 5867575}. Or for the angle \arccos\frac78: {19, 163, 865, 3313, 10099, 26083, 59473, 122599, 229885, 395299, 634597, 9663331, 1410463, 1989325, 2726893, 3649189, 4784173, 6161743}. Or for a 31-vertex G of five wheels with angle \frac12\arccos\frac56: {31, 451, 3451, 14557, 39973, 87913, 168307, 292873, 475147, 730459, 1075933, 1530487, 21148347, 2851477, 3764719, 4880653, 6227167, 7833943}.

    Reply

  41. In your examples, you can use combinations of 2 wheels to get vertices in the third wheel. But the problem is much each easier when you can’t:

    Let a_k be the number of vertices in the kth layer of the wheel (so a_k has 6k vertices for k>0 and a_0 = 1).
    # of vertices = sum(x+y+z <= m) of a_x * a_y * a_z (for non-negative integers x,y,z)

    this

    Also, I notice that OEIS says your sequence {19, 163, 715, … } is 27/4 x^4 + 11/2 x^3 + 9/4 x^2 − 5/2 x + 7

    Reply

    1. In the general case, maybe it might be useful to think in terms of “basis” vectors. Wheels a, b, c have basis vectors {a0, a1}, {b0, b1}, {c0, c1}. (a0 and a1 form a 60-degree angle, same for b0, b1 and c0, c1)

      Then each vertex in G_m is a 6-dimensional lattice point. P(i0, i1, i2, i3, i4, i5) = a0*i0 + a1*i1 + b0*i2 + b1*i3 + c0*i4 + c1*i5.

      There’s a simple way to check if P(i0..i5) is in G_m or not. And my post above counts them. But P(i0..i5) may equal P(j0..j5). This happens when there’s some P(k0..k5) = 0. Then P(i0+k0..i5+k5) equals P(i0..i5).

      Reply

    2. Thanks, Tom. Very fast and constructive. I’ll figure out why I couldn’t handle {19, 163, 715, … }. But it looks like you wanted to add something after “this”. Or is it a typo?

      Reply

    3. I figured out why {19, 163, 715, … } didn’t work for me. In fact, I worked with the sequence {1, 19, 163, 715, … }, which seemed natural.
      For the sequence {31, 451, 3451, 14557, 39973, 87913, …} I found the following relation, which works from the sixth member of the sequence (up to at least the 18th): \frac{299}{4}m ^4+\frac{27}{2}m^3-\frac{995}{4}m^2-\frac{1371}{2}m+1189. The first terms of the sequence according to the formula are equal to {343, 127, 3313, 14467, 39949, 87913, …}

      Reply

    4. For a sequence with angle \arccos\frac56, I found a relation that works from the ninth member of the sequence (at least up to the 20th): \frac{171}{4}m^4-\frac{217}{2}m^3-\frac{1095}{4}m^2+\frac{211}{2}m+2965.
      But so far I can’t find a solution for sequences with the \arccos\frac78 angle and some others. Here are some of them:
      {19, 163, 865, 3313, 10099, 25765, 55747, 105889, 183127, 295645, 452491, 663787, 940681, 1295347, 1740985, 2291821, 2963107, 3771121, 4733167, 5867575}
      {19, 163, 865, 3313, 10099, 26083, 59473, 123121, 236035, 425107, 727057, 1190593, 1878787, 2871667, 4269025, 6193441}
      {19, 163, 865, 3313, 10099, 26083, 59473, 123121, 236035, 425107, 727057, 1190593, 1878787, 2871547, 4265545}
      {19, 163, 805, 2239, 4015, 6001, 8305, 10957, 13939, 17245, 20893, 24889, 29233, 33925, 38965, 44353, 50089, 56173, 62605, 69385, 76513, 83989, 91813, 99985, 108505, 117373, 126589, 136153, 146065, 156325}

      Reply

      2. Tom’s formula for a 19-vertex generating graph on three wheel graphs leads to \frac{3}{10}m^6+\frac{9}{10}m^5+3m^4+\frac{9} {2}m^3+\frac{57}{10}m^2+\frac{18}{5}m+1. And it gives the second sequence (out of four above). In particular, it is generated at the angles \pm\arcsin\frac14, \pm\arccos\frac{1}{23}, \pm\pi/4.
        For a 25-vertex graph on four wheel graphs, we get \frac{9}{280}m^8+\frac{9}{70}m^7+\frac{3}{4}m^6+\frac {9}{5}m^5+\frac{183}{40}m^4+\frac{63}{10}m^3+\frac{93}{14}m^2+\frac{132 }{35}m+1.
        So far, I have problems with a similar 31-vertex graph on five wheel graphs.

    5. So, consider families of graphs of the form G(h, m)=\oplus^m G(h), where the generating graph G(h) consists of h wheel graphs with a common central vertex. The number of vertices of G(h) is 6h+1. We want to find the maximum number of vertices for each such graph G(h, m).
      Based on the Tom’s formula, one can calculate the number of vertices G(h, m) for some h and m. By fixing h, one can investigate the obtained sequences of the number of vertices. They are described by \sum_k{a_km^k} polynomials of order 2h.
      Here are the coefficients of the first 7 first polynomials, if I did not make a mistake in the calculations:
      {1, 3, 3},
      {1, 3, 9/2, 3, 3/2},
      {1, 18/5, 57/10, 9/2, 3, 9/10, 3/10},
      {1, 132/35, 93/14, 63/10, 183/40, 9/5, 3/4, 9/70, 9/280},
      {1, 141/35, 2607/350, 54/7, 1713/280, 117/40, 267/200, 9/28, 27/280, 3/280, 3/1400},
      {1, 1611/385, 15681/1925, 1593/175, 1527/200, 1143/280, 5643/2800, 837/1400, 549/2800, 9/280, 3/400, 9/15400, 3/30800},
      {1, 21738/5005, 1535661/175175, 2844/275, 140331/15400, 531/100, 7767/2800, 2619/2800, 3231/9800, 27/400, 3/175, 9/4400, 3/7700, 9/400400, 9/2802800}

      The leading coefficients are of the form a_{2h}=\frac{6^h}{(2h)!}. In general, the values of the coefficients fit into the scheme a_{2h-g}=\frac{f_g(h) 6^h}{(g+1)!(2h)!}, where the first few functions f_g(h) form the sequence {1 , 1, (h+1)/2, h, (5h^2+11h-2)/12, h(5h+1)/4}. But I still don’t see any pattern here. Maybe I made a mistake somewhere?

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s