# Polymath16, seventeenth thread: Declaring victory

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.

## 292 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?

1. ag24ag24 says:

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. ag24ag24 says:

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.

1. ag24ag24 says:

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?

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?

1. ag24ag24 says:

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. Tom Sirgedas says:

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).

2. Jaan Parts says:

@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.

1. I don’t have edit privileges to the start page anymore. (I think it navigated to another system?) Maybe someone else can post the links?

1. Dustin, as the current admin for the Polymath Wiki I can help with restoring your edit privileges. Could you email me at thomas@asone.ai with the message you are getting when you try to edit a page?

2. ag24ag24 says:

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.

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. ag24ag24 says:

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. Jaan Parts says:

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.

1. ag24ag24 says:

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?

2. ag24ag24 says:

thanks!

3. ag24ag24 says:

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.

4. Jaan Parts says:

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.

5. ag24ag24 says:

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.

6. Jaan Parts says:

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.

7. ag24ag24 says:

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?

8. Jaan Parts says:

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.

9. ag24ag24 says:

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?

10. Jaan Parts says:

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.

11. ag24ag24 says:

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?

12. Jaan Parts says:

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)

13. ag24ag24 says:

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. Jaan Parts says:

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.

1. ag24ag24 says:

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. Jaan Parts says:

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$:
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. ag24ag24 says:

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. ag24ag24 says:

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. Jaan Parts says:

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. Jaan Parts says:

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.

7. Jaan Parts says:

Well, almost any, if we talk about less than unit distances.

8. ag24ag24 says:

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. ag24ag24 says:

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. Jaan Parts says:

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.

11. Jaan Parts says:

On the other hand, this is not so for stripes…

12. ag24ag24 says:

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. Jaan Parts says:

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:

14. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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).

19. Jaan Parts says:

Now the strip width is 1.30, for the same construction ($-0.43\le y\le 0.87$).

20. ag24ag24 says:

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!

21. ag24ag24 says:

I meant (Sqrt[11] – 5Sqrt[3])/12 of course, sorry

22. Jaan Parts says:

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. ag24ag24 says:

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?

24. Jaan Parts says:

$-\frac{\sqrt{11}+7\sqrt{3}}{36}$, so this gives the width $\frac{3\sqrt{11}+\sqrt{3}}{9}$. But I think this is an intermediate solution.

25. ag24ag24 says:

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.

3. Jaan Parts says:

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?

1. Tom Sirgedas says:

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.

1. Jaan Parts says:

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

2. Tom Sirgedas says:

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. Jaan Parts says:

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. Tom Sirgedas says:

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. Tom Sirgedas says:

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. Jaan Parts says:

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. Tom Sirgedas says:

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.

8. Jaan Parts says:

Yes, that’s a good example!

4. ag24ag24 says:

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.

1. Jaan Parts says:

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.

1. ag24ag24 says:

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. Jaan Parts says:

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.

3. ag24ag24 says:

Ah, OK – thanks!

4. Jaan Parts says:

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. Jaan Parts says:

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.

6. Jaan Parts says:

$y\in[-0.4454,0.8660]$ of course

7. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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.

10. ag24ag24 says:

Yay, just in time! I will update the manuscript.

5. Let me also post it here that there will be a 3-day Workshop on Euclidean Ramsey Theory from tomorrow, where Aubrey will talk (among other things) about this polymath project:
https://coge.elte.hu/WERT.html

Everyone is welcome to attend!

6. 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.

1. ag24ag24 says:

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.

2. Jaan Parts says:

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.

1. ag24ag24 says:

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.

2. You want them suc that they canNOT be drawn on a sphere? Why?

3. ag24ag24 says:

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.

4. Tom Sirgedas says:

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.

7. ag24ag24 says:

Hi everyone,

I’m delighted to say that our article is out! I have placed a copy of the whole issue here:

https://www.dropbox.com/s/8zmhm4ouhol8zco/xxx-4.pdf?dl=0

because it also contains the latest solo report from Jaan, a very nice demonstration of improved multi-fold chromatic numbers in the plane. I’m sure he would be happy to engage in discussion of that work here.

8. ag24ag24 says:

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.

1. ag24ag24 says:

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.

9. 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.

1. Jaan Parts says:

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?

1. Vsevolod Voronov says:

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.
(The figure shows embeddings of 4-chromatic 10-vertex minimally rigid UDG not containing Moser spindle or 9-vertex 4-chromatic subgraph.)

2. Jaan Parts says:

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. Jaan Parts says:

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. Vsevolod Voronov says:

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. Jaan Parts says:

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. Vsevolod Voronov says:

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. Jaan Parts says:

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

8. Vsevolod Voronov says:

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. Vsevolod Voronov says:

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. Jaan Parts says:

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. Jaan Parts says:

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. Jaan Parts says:

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. Jaan Parts says:

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. Vsevolod Voronov says:

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. Jaan Parts says:

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. Jaan Parts says:

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. Vsevolod Voronov says:

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. Vsevolod Voronov says:

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

19. Jaan Parts says:

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. Jaan Parts says:

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.

21. Jaan Parts says:

I meant the square roots of Loeschian numbers

22. Jaan Parts says:

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.

23. Jaan Parts says:

Actually in (3, 11) we can form such triangles too.

24. Vsevolod Voronov says:

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. Jaan Parts says:

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. Vsevolod Voronov says:

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. Vsevolod Voronov says:

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.

10. Collin says:

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.

1. Jaan Parts says:

As far as I know, there is no such bound.

1. Collin says:

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. Collin says:

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

3. Jaan Parts says:

For n=2 the upper bound is 6.82… according your last formula. Is it OK?

4. Collin says:

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.

2. Vsevolod Voronov says:

But this bound is asymptotically worse than the known upper bound $\chi(R^n) \leq (3+o(1))^n$ (Larman, Rogers, 1972)?

1. Collin says:

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. Vsevolod Voronov says:

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. AAR says:

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. ag24ag24 says:

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!

11. Collin says:

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)}$.

12. ag24ag24 says:

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?

1. ag24ag24 says:

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.

2. ag24ag24 says:

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 🙂

1. Asger Haugstrup says:

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. ag24ag24 says:

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).

3. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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. Jaan Parts says:

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. ag24ag24 says:

“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. Jaan Parts says:

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.

13. Asger Haugstrup says:

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. 🙂

14. Asger Haugstrup says:

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.

1. Asger Haugstrup says:

neighbour

2. ag24ag24 says:

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

15. ag24ag24 says:

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!

16. Asger Haugstrup says:

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?

1. ag24ag24 says:

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.

17. Asger Haugstrup says:

contains

18. Jaan Parts says:

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?

1. ag24ag24 says:

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!

2. Jaan Parts says:

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…

1. ag24ag24 says:

Thanks. Can you give us some description of your method for seeking such tilings?

2. Jaan Parts says:

No method yet. Pencil and paper.

19. ag24ag24 says:

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…

1. Jaan Parts says:

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

1. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. ag24ag24 says:

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!

5. Jaan Parts says:

Perhaps, my explanation wasn’t clear. I meant something like this (for 5 colors):

6. Jaan Parts says:

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.

7. Jaan Parts says:

$\sqrt3/2$

8. Jaan Parts says:

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.

9. Jaan Parts says:

A small breakthrough for 8 colors. The distance between tiles of the same color is 1.4.

10. ag24ag24 says:

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. Jaan Parts says:

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. Jaan Parts says:

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$.

20. Hi all!
I’ve stopped following things here, just wanted to mention that this paper has been uploaded to arxiv with a fantastic introduction about the whole problem, and some new results whn a range of values is forbidden (see table at the end):
https://arxiv.org/abs/2201.04499

1. ag24ag24 says:

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

2. Jaan Parts says:

Yes, I am dealing with just this topic. I plan to publish my results soon.

21. Jaan Parts says:

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).

1. Jaan Parts says:

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\}$?

1. ag24ag24 says:

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. ag24ag24 says:

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

3. Jaan Parts says:

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.

4. Jaan Parts says:

Ah, I understand. You make long tiles wider.

5. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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.

22. ag24ag24 says:

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?

1. ag24ag24 says:

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!)

2. Jaan Parts says:

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.

1. ag24ag24 says:

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

2. Jaan Parts says:

Okay. No ideas for 4- and 5-discs and 6-strip yet?

3. ag24ag24 says:

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. ag24ag24 says:

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.

5. Tom Sirgedas says:

My simulator agrees that it’s slightly less than 1.266

6. Tom Sirgedas says:

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

7. ag24ag24 says:

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

8. Tom Sirgedas says:

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. ag24ag24 says:

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.

23. Jaan Parts says:

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:

@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.

1. Tom Sirgedas says:

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!

1. Jaan Parts says:

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. Tom Sirgedas says:

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. ag24ag24 says:

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. Tom Sirgedas says:

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. Tom Sirgedas says:

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. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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. Tom Sirgedas says:

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.

11. Jaan Parts says:

Yes, sure. Exe would be nice.

12. Jaan Parts says:

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.

13. Jaan Parts says:

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. Jaan Parts says:

I can’t beat 1.732 for the 6-coloring of the annulus. Any ideas?

1. Tom Sirgedas says:

here’s a quick idea (i just sloppily made the outer ring)

2. Jaan Parts says:

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. Tom Sirgedas says:

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. Tom Sirgedas says:

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

5. Jaan Parts says:

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. Jaan Parts says:

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?

1. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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?

4. ag24ag24 says:

Actually I hink they should probably be straight.

5. Jaan Parts says:

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. Jaan Parts says:

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. J says:

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

8. ag24ag24 says:

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. Jaan Parts says:

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. Tom Sirgedas says:

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. ag24ag24 says:

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. ag24ag24 says:

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. Jaan Parts says:

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

4. Jaan Parts says:

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?

1. ag24ag24 says:

Can you send me Ivanov’s paper? (Ideally in English, but Russian if neessary!)

2. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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?

1. ag24ag24 says:

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. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

Excellent!

6. Jaan Parts says:

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?

24. Jaan Parts says:

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.

1. Sorry, but I’ve stopped following things here… Goldbach’s conjecture is wide open, don’t believe any article claiming a solution, unless it appeared at a major journal. But if it gets solve, you’ll definitely hear about it in mainstream news as well. Also trust Wikipedia: https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

25. Jaan Parts says:

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.

1. Jaan Parts says:

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.

1. Tom Sirgedas says:

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. Jaan Parts says:

It would be cool.

2. Jaan Parts says:

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.

3. Jaan Parts says:

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?

1. ag24ag24 says:

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. Jaan Parts says:

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. ag24ag24 says:

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. Jaan Parts says:

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

5. ag24ag24 says:

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. Jaan Parts says:

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.

5. Jaan Parts says:

But I found a better 8-tiling with a distance of 1.441934884.

1. ag24ag24 says:

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. Jaan Parts says:

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

3. Jaan Parts says:

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. Jaan Parts says:

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. ag24ag24 says:

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. ag24ag24 says:

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. Jaan Parts says:

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.

8. Jaan Parts says:

Wait, I think I’ve found a bug in my constraints.

9. Jaan Parts says:

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.

10. Jaan Parts says:

And you are right, the picture has changed a bit.

11. ag24ag24 says:

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.

12. Jaan Parts says:

Three variables is cool. I see at least four.

13. Jaan Parts says:

Ah, figured out how to kill one.

14. ag24ag24 says:

I’ve got it down to two now, but still a long way to go to get an exact expression.

15. ag24ag24 says:

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. Jaan Parts says:

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.

17. ag24ag24 says:

Nice proof!

26. ag24ag24 says:

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?

1. ag24ag24 says:

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.

2. ag24ag24 says:

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.

27. ag24ag24 says:

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.

1. Jaan Parts says:

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.)

1. ag24ag24 says:

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. Jaan Parts says:

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.

3. Jaan Parts says:

And we have to stabilize the meaning of $k$. Otherwise $\pm 1$-uncertainty appears.

4. Jaan Parts says:

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. Jaan Parts says:

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. ag24ag24 says:

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.