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

Hey Domotor – OK, I just found the comment of yours that I was remembering:

https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5492

I see you were hoping to improve it. Would you like to suggest wording?

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?

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.

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?

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?

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.

Hey, I attempted to “prove” that you can’t 4-color an infinite strip of width > 1 here:

https://groups.google.com/g/hadwiger-nelson-problem/c/luwhYQuk1Ls

I hope my general idea is good or at least inspires a proper proof.

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?

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?

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.

Indeed! I bet sooner or later this guy will have more papers than I do: https://arxiv.org/search/math?searchtype=author&query=Polymath%2C+D+H+J

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

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

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?

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?

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.

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?

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.

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 , where is some base graph, is the number of identical terms in the Minkowski sum, is a graph composed of copies of the graph rotated around the center by angles .

In most cases, the graph is a 7-vertex wheel graph (hexagon), or a 13-vertex 2-wheel graph (dodecagon or double-hexagon), where the wheels are rotated around the common center by an angle .

The “+” sign indicates the Minkowski sum. The union of graphs is denoted by “” 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 can be written as 1H2 or just H2, the graph as 2H2+H0, the 6937-vertex Tamas’s graph 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.

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?

It was a graph 4H4 () with a mono-pair with a distance :

https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24332

Later I will try to advance here too.

thanks!

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.

I’m sorry the explanation was not clear enough. But I thought the rest was obvious. Everything is exactly the same as in Figures 1 and 2 in the preparing article on disks and stripes. On the basis of mono-pairs, a long chain is constructed, closing by an unit-distance edge, which leads to the need of an additional color.

In the case of stripes, we have a rectangle of some width containing a mono pair, that is, two points of rectangle have the same color in a 4-coloring. Next, we connect many copies of these rectangles in a chain, so that they are located inside of slightly wider strip, while simultaneously connecting the points of mono-pairs. On the way to one side, the rectangles wiggle a little, in the opposite direction, they do not, which allows us to close the chain of mono-pairs by an unit-distance edge. You can notice that it doesn’t matter at all how the mono-pair itself is located inside the rectangle; we can always make a suitable chain.

In the case of a disk, the situation is similar. It is possible to organize the same chain of mono-pairs, placed on similar disks and closed by an unit-distance edge. In most cases, it also doesn’t matter how the mono-pair is positioned on the disc. The resulting disc will only have a slightly larger diameter (as in Figure 7 in the article). In the case of a mono-pair 8/9 with one of the vertices in the center of the disk, a long chain is not required: it is enough to take two mono-pairs with a common center and connect them with an edge. This does not change the diameter of the resulting disc at all.

Did I add some clarity?

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.

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.

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?

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.

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?

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.

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?

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)

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!

As for the number of vertices of some large graph , 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 , connected by an edge (by the way, such a graph can be embedded in ). 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.

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.

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, , with a radius :

https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23272

I’m not yet sure if the asymmetric positioning of the mono pair relative to the disc will help. The first day of tests gave nothing.

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?

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.

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.

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.

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

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?

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?

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.

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

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.

Oh, I think I figured out how you represent my graph. No, each of its 4H4-subgraphs containing a 4-color mono-pair is symmetric about the center, and the disk is densely occupied by vertices. I will try to cut off the disk boundary on the side, but I don’t think it will be possible to cut off a significant part without damaging the mono-pair. An image of a 4H4-subgraph looks like this:

https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23279

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

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?

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 (vertices 5 and 9), taking a pair (vertices 1 and 13). Formally, this graph is larger than 4H4. Width 1.35 is obtained for . 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 .

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!

The current 5-chromatic strip width is 1.32 (). 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 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).

Now the strip width is 1.30, for the same construction ().

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!

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

Yes, the conjecture does not work in the sense that it does not limit the lower value of , nor in the sense that it does not reach the upper value (it is still ). 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 , as well as and . Even a radius of 1 is not obtained. The calculations were interrupted a week after the start (the result is indetermined).

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?

, so this gives the width . But I think this is an intermediate solution.

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.

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?

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.

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

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

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.

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.

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.

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.

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.

Yes, that’s a good example!

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.

It looks like I bumped into the wall with stripes. The current result is , . 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 . Inside the interval , I checked all the available thresholds for .

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 (141039 vertices, 1130696 edges). I also want to try playing with the upper threshold for , 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.

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.

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.

Ah, OK – thanks!

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.

Recent results show that the upper threshold of can be slightly moved. So the strip works with . The width of this strip does not reach the record. But there is something to explore.

of course

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.

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

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.

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

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!

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.

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.

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.

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.

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

such

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.

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.

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.

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.

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.

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.

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.

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 and , 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 , 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 on figure 2 is 3-, not 4-chromatic. Right?

Hi Jaan,

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

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

Yes, thanks for the observation. One of the edges is not drawn correctly. In fact, in the construction for the great icosahedron we used graph 10.2 from this figure.

https://drive.google.com/file/d/1RvAFY35W5SIL0qFC_mfTHEiSd854ougu/view?usp=sharing

(The figure shows embeddings of 4-chromatic 10-vertex minimally rigid UDG not containing Moser spindle or 9-vertex 4-chromatic subgraph.)

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, ), where {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.

Correction: I forgot to exclude factors 3 and 11 from the set. After correction: {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, …}.

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

And yes, it seems likely that , 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?

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 with integer and . Btw, how did you get (2, 3, 29) and (2, 3, 47)?

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 , , , , … 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.

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

I used an extended version of the construction from the article. If we take set , , then after calculating the sum (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.

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

I confirm the occurrence of mono-pairs in the field (2, 3). In particular, the graph has mono-pairs with distances , , , , . Here I redesignated the unit-radius graphs with rotations and by the number of vertices (these graphs differ in the number of rotations by ), and the construction means the trimming of the graph with radius . This graph can be further trimmed to at least a radius of 1.4, where it has 88849 vertices and 493680 edges.

The graph has 35065 vertices and 168048 edges, and contains mono-pairs with a distance .

Thus, if I am not mistaken, in the field (2, 3) it is possible to realize mono-pairs with all distances of the form and , which gives 5-chromatic fields of the form (2, 3, n), where {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, …}.

It’s getting more interesting. A mono-pair with a distance 2 is observed even on a graph with 15547 vertices and 86766 edges. Here is the wheel-graph. A little more, and it will be possible to do a systematic reduction.

The graph with 11305 vertices and 46194 edges is also suitable, although it takes 100 times longer to test.

The graphs (10981 vertices, 50484 edges) and (7231 vertices, 33534 edges) also work. Here is a copy of rotated by .

Yes, and I checked that in some cases we can take even 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.

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 appears in your article in Figure 9? In connection with the new data, a suspicion creeps in, whether will it work too?

By tightening the trimming, one can slightly reduce the number of vertices, getting graphs with a mono-pair: (8293 vertices, 33294 edges) and (6169 vertices, 26796 edges).

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.

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

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

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 is expanded further.

I meant the square roots of Loeschian numbers

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.

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

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.

Because in this case there is no corresponding good angle of rotation that would fit an integer number of times into ?

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

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.

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 belongs to the cyclotomic field . In fact, we can get the same set of vertices by adding the degrees of divided by 3. Here .

Therefore a similar coloring, if it exists, should be based on homomorphism

and here the finite ring contains elements.

Perhaps there is a simpler way.

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.

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

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.

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

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

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.

But this bound is asymptotically worse than the known upper bound (Larman, Rogers, 1972)?

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 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:

(only marginally better than but it matters in my more detailed argument).

p and q, integers which can be chosen arbitrarily,

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

We get a coloring with

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

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?

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$

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!

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() and the last one was .

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?

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.

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 🙂

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.

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

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

Did you receive my email about writing up these graphs?

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.

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

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.

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

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?

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.

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

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.

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

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.

neighbour

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

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!

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?

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.

contains

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 . If we take 9 colors, then the maximum distance will be . 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 . And this is a little weird. Can we get more?

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!

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…

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

No method yet. Pencil and paper.

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…

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

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 🙂

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.

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?

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!

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

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 for 5 colors.

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.

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

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…

I went over on the computer all possible (as it seems to me) variants of hexagonal tilings with the number of colors from 5 to 66, such that all tiles have the same shape and all three diagonals of the tile have unit length. All can be divided into Loeschian () and non-Loeschian ().

In about a third of cases with , the transition from to leads to an increase in the maximum distance between tiles of the same color; this happens for . But in 2/3 of cases adding color does not increase . So the function is still stepwise.

For , the distance increases almost always, but there are exceptions. So, tiling with beats . 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.

And one more surprise. In 6-coloring, the hexagonal tiling still beats (Pritikin’s) pentagonal tiling. Here is the root of the equation , and .

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

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

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

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

For disks, the question can be rephrased as follows. Can we get the radius of a -colored disk larger than the trivial division of the disk into equal sectors, where ?

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.

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

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.

Ah, I understand. You make long tiles wider.

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.

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?

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.

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?

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

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.

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

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

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 🙂

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.

My simulator agrees that it’s slightly less than 1.266

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

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

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.

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.

It’s great. It must be assumed that for the 6-strip there is also some non-trivial solution.

There is a slightly more general task: coloring simple geometric shapes, such as a disk or a strip, in such a way that a given distance interval is forbidden. Of particular practical interest is also the coloring of the annulus, that is, the area enclosed between two concentric circles. The motivation can be found in the article that is mentioned here:

https://dustingmixon.wordpress.com/2021/02/01/polymath16-seventeenth-thread-declaring-victory/#comment-32246

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

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!

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 ). 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 . In my problem, this is the same that appears in the interval of forbidden distances [1, ]. 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.

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.

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!

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.

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)

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.

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 . Next, the simulator tries to maximize 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.

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!

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.