# Polymath16, seventeenth thread: Declaring victory

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

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

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

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

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

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

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

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

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

## 94 thoughts on “Polymath16, seventeenth thread: Declaring victory”

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

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

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

1. ag24ag24 says:

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

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

3. ag24ag24 says:

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

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

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

1. ag24ag24 says:

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

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

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

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

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

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

1. ag24ag24 says:

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

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

2. Tom Sirgedas says:

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

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

2. Jaan Parts says:

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

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

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

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

2. ag24ag24 says:

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

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

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

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

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

2. ag24ag24 says:

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

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

3. Jaan Parts says:

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

1. ag24ag24 says:

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

2. ag24ag24 says:

thanks!

3. ag24ag24 says:

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

4. Jaan Parts says:

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

5. ag24ag24 says:

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

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

6. Jaan Parts says:

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

7. ag24ag24 says:

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

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

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

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

What am I getting wrong?

8. Jaan Parts says:

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

9. ag24ag24 says:

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

10. Jaan Parts says:

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

11. ag24ag24 says:

Ah,OK… so you are reporting two things:

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

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

Right?

12. Jaan Parts says:

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

13. ag24ag24 says:

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

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

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

4. Jaan Parts says:

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

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

1. ag24ag24 says:

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

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

2. Jaan Parts says:

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

3. ag24ag24 says:

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

4. ag24ag24 says:

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

5. Jaan Parts says:

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

6. Jaan Parts says:

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

7. Jaan Parts says:

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

8. ag24ag24 says:

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

9. ag24ag24 says:

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

10. Jaan Parts says:

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

11. Jaan Parts says:

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

12. ag24ag24 says:

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

13. Jaan Parts says:

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

14. Jaan Parts says:

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

15. ag24ag24 says:

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

16. Jaan Parts says:

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

17. ag24ag24 says:

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

18. Jaan Parts says:

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

19. Jaan Parts says:

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

20. ag24ag24 says:

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

21. ag24ag24 says:

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

22. Jaan Parts says:

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

23. ag24ag24 says:

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

24. Jaan Parts says:

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

25. ag24ag24 says:

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

3. Jaan Parts says:

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

1. Tom Sirgedas says:

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

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

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

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

1. Jaan Parts says:

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

2. Tom Sirgedas says:

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

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

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

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

3. Jaan Parts says:

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

4. Tom Sirgedas says:

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

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

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

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

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

5. Tom Sirgedas says:

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

6. Jaan Parts says:

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

7. Tom Sirgedas says:

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

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

8. Jaan Parts says:

Yes, that’s a good example!

4. ag24ag24 says:

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

1. Jaan Parts says:

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

1. ag24ag24 says:

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

2. Jaan Parts says:

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

3. ag24ag24 says:

Ah, OK – thanks!

4. Jaan Parts says:

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

5. Jaan Parts says:

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

6. Jaan Parts says:

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

7. Jaan Parts says:

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

8. ag24ag24 says:

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

9. Jaan Parts says:

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

10. ag24ag24 says:

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

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

Everyone is welcome to attend!

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

1. ag24ag24 says:

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

2. Jaan Parts says:

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

1. ag24ag24 says:

Thanks Jaan.

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

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

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

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

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

3. ag24ag24 says:

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

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

4. Tom Sirgedas says:

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

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

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

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

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

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

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

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

7. ag24ag24 says:

Hi everyone,

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

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

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

8. ag24ag24 says:

Hey all,

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

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

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

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

1. ag24ag24 says:

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