This is the thirteenth “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.

Interest in this project has spiked since approaching (and passing) our original deadline of April 15. For this reason, I propose we extend the deadline to October 15, 2019. We can discuss this in the Polymath proposal page.

Here are some recent developments:

I’m interested to see if this last point has legs!

1. ag24ag24 says:

I support the new deadline. However, I think it makes sense to start writing a rough draft of the paper now, since there is so diverse a range of results to cover and since many areas are unlikely to change much because none of us is currently focusing on them. Can I suggest that Dustin should put together a skeleton structure of the paper, following which each of us can supply some text for those parts where we feel the greatest competence/responsibility?

1. Jaan Parts says:

What output size? What goals are pursued?
For me, this project is not only a wealth of knowledge, but also an excellent textbook. Therefore, I would not change anything in form (leaving the dialogues and the process of developing ideas, which is very valuable), I would only remove the garbage and divide the material by topic.

2. I would like to ask (as a complete nonexpert) whether there are heuristical arguments for CNP being either 5,6 or 7 – i.e. what do experts think CNP should be? One of the goals of this project is to find one graph thats not 5-colorable — do you consider that realistic?

1. ag24ag24 says:

One heuristic argument is based on the proportion of the plane that can be tiled with k colours avoiding unit length. Seven colours suffice for the whole plane (giving the known upper bound) and more than 1999/2000 of the plane can be covered with six colours, but with five we haven’t even reached 29/30 (though we don’t have a formal proof that we’re at the maximum). That says to me that the true CNP may be 6 or 7 but is very unlikely to be 5. In other words, absolutely a 6-chromatic UD graph is realistic, though the methods for finding it may be computationally daunting.

3. Fernando Oliveira says:

I am very interested in the graph by Jaan Paarts with fractional chromatic number (FCN) >= 3.98. Can I get it somewhere? How was it verified to have such large FCN?

This would imply an upper bound for m_1(R^2) of about 0.2512, which is quite close to 0.25; showing that m_1(R^2) is < 0.25 is an open problem. There is the possibility that combining this graph with spectral methods would give a bound < 0.25, and I would like to try that.

Also, how is the approach for finding this graph different from the one by Thomas Bellitto and others, who adapted the de Grey algorithm for computing bounds for m_1 directly? They get a much worse bound than 0.2512, so I am curious to know what the difference is.

1. ag24ag24 says:

I am pretty sure that it would be easy to push the FCN record considerably above 4 if only we could compute it for larger graphs. So far, the only 5-chromatic graphs for which the FCN has been computed are close-to-minimal ones in which the removal of only one vertex (or a few?) reduces the CN to 4. Such graphs are never going to have an FCN over 4 – but it is very easy to construct graphs in which quite a lot of vertices would need to be removed in order to reduce the CN. Graphs consisting of a lot of 5-chromatic subgraphs with a lot of vertices in common are all that should be needed.

I wonder whether there is a much more efficient algorithm that can deliver a reasonably tight lower bound on a graph’s FCN?

1. Fernando Oliveira says:

Croft constructs a 1-avoiding set in R^2 (i.e., an independent set of the unit-distance graph) that has density 0.22936. Since m_1(R^2) * measurable FCN = 1 (this should be easy to prove), at least the measurable FCN of R^2 should be at most 1 / 0.22936 = 4.3599.

Now FCN 4.3599. This is interesting, since it implies that to get a bound on the chromatic number larger than 5 we need to work with the chromatic number itself, not with the fractional chromatic number.

2. Jaan Parts says:

To get the bound CN >= 5, we also work directly with CN. Reaching and crossing the bound FCN > 4 is extremely difficult when using known methods.

2. Jaan Parts says:

The current record for which FCN value is known is slightly less: 3.971119. In fact, the Bellitto algorithm is used for calculations, maybe with minor improvements. I’m working on calculating of FCN of larger graphs, but apparently I’ll reach 3.98 in only a month or two (I use a laptop for calculations). I am also interested in someone doing independent calculations to compare the results. The fact is that already with Bellitto’s graph I have small differences in FCN estimation. Here is the graph for which I got FCN = 3.971119:
https://www.dropbox.com/s/xfl9qhmnb6qj07s/v799.vtx?dl=0

1. Fernando Oliveira says:

This is very nice! Are you finding the FCN by computing weights for the vertices and then finding the weighted independence number? If so, then if you send me a file with the position of each vertex, the weight of each vertex, and the weighted independence number (or an upper bound for it), I can try to put the graph in the spectral bound and see what I get.

2. Jaan Parts says:

Below is a link to the weights file. It is synchronized with the vertex file, that is, the vertex number is equal to the line number in both files.
https://www.dropbox.com/s/jgcjnqdo2llp40x/g799.vtw?dl=0

Could you describe in more detail the essence of your spectral method and its purpose?

3. Fernando Oliveira says:

The spectral bound is related to Hoffman’s bound. Maybe the most accessible paper about it is this one: https://arxiv.org/abs/0808.1822

Thank you for the vertex weights. Just to be clear: with these vertex weights, the weighted-independence number of the graph is 1 / 3.97119, is that it?

Any weighted graph gives extra constraints that can be added to the spectral bound.

4. Jaan Parts says:

Sum of weights should be 3.971

5. Fernando Oliveira says:

Sorry, I still don’t understand what the weights are supposed to be. Can you tell me exactly what they mean?

6. Jaan Parts says:

As far as I can tell, Dustin is right. If I say that this is the solution vector of the dual linear program (7) in Bellitto’s paper, will this answer your question?

7. Fernando Oliveira says:

I think I know enough then. I will try to see what comes out of it.

4. Jaan Parts says:

I spent a lot of time trying to reduce small subgraph, but without success. It was possible to obtain a set of 525-vertex 5-chromatic graphs. Below is a variant with 2605 edges, containing 428 Moser’s graphs. There are also options that look visually more symmetrical, but with a larger number of edges.
https://www.dropbox.com/s/2mcb5o7r0uewoua/v525e2605.vtx?dl=0

1. ag24ag24 says:

Congratulations Jaan! It would be great if you can give a bit of a description of how you found these.

2. Jaan Parts says:

Thank you, Aubrey. And you are right. I need to think about the description. Partly for this, I published the result in order to suppress sports excitement.

5. ag24ag24 says:

I’ve just had a go at the idea of Domotor that we tried to coerce Jaan into exploring, namely cutting down a graph in which two or more vertex pairs are all constrained to be mono to a graph in which one of two vertex pairs is so constrained. I chose Jaan’s 409er as my starting point. Surprisingly (and disappointingly), I have only been able to get down to 391 vertices with this relaxed constraint. I may try some of the other graphs we know of that have mono pairs at distance 8/3, but I’m sensing that the degree of relaxation is actually only dramatic in the eye of the human beholder.

I am, however, wondering whether the same idea might be more readily applicable when we consider distances with a tighter probabilistic upper bound. Might there be a way to make the bound of 1/3 on p_(1/sqrt[3]) strict? If so, the task would be to find a graph in which one of three specified vertex pairs at that distance must always be mono. I have not yet thought much about this but it seems like something to try.

1. Jaan Parts says:

Great! How exactly did you get 391? I managed to throw off only a few vertices using a probabilistic approach. (Shaking up 409-vertex graph, I got an honest 387, but your result is very interesting.)

1. ag24ag24 says:

I didn’t really do anything interesting – I just deleted any vertices whose deletion did not introduce a 4-colouring with (2/3,2/Sqrt[3]) a different colour than (-2/3,-2/Sqrt[3]) and also (2/3,-2/Sqrt[3]) a different colour than (-2/3,2/Sqrt[3]). I didn’t try to be clever about the order of deletion, except that I only deleted vertices in groups with the same absolute value of both coordinates. I tried two different orders and both got me to 391 (though the vertices deleted were not the same, so maybe an optimal order can shave off a few more). The ones I was able to delete are +/-:

{1/6 (-1-Sqrt[33]),0}
{1/6 (4-Sqrt[33]),-(Sqrt[3]/2)}
{1/12 (-5-Sqrt[33]),1/12 (7 Sqrt[3]-3 Sqrt[11])}

plus either +/-:

{1/6 (3-Sqrt[33]),1/6 (-Sqrt[3]-Sqrt[11])}
{-(Sqrt[(11/3)]/2),1/6 (-2 Sqrt[3]+Sqrt[11])}

or else +/-:

{-1,0}
{-(4/3),0}
{-(1/2),-(Sqrt[3]/2)}

I did try one other thing – I noticed that your 409er was not totally symmetrical across both axes, so I tried deleting vertices after first adding the 22 vertices whose reflections were already present. But that didn’t given me any improvement.

I’ve also just had a go starting from Jannis’s 745er, with the two pairs not allowed to be both bichromatic being {(0,0),(8/3,0)} and {(0,0),(-8/3,0)}, but the lowest I’ve got to is 591. I’m pretty sure that if there is a graph that human-comprehensibly has this property then we will only find it by starting from a very different graph.

What was your 387er? Did you require the same property as I did (the same two pairs of vertices)?

2. ag24ag24 says:

I just tried being a bit more intelligent about the order of deletion of vertices, but I haven’t improved on 391. I found five more sets of vertices that can be deleted if nothing else has been deleted first – they are +/-:

{(1+Sqrt[33])/6,0}
{1/2,Sqrt[3]/2}
{1/2,(Sqrt[3]-2 Sqrt[11])/6}
{Sqrt[(11/3)]/2,1/Sqrt[3]-Sqrt[11]/6}
{(7-Sqrt[33])/6,0}

which makes a total of 32 from the original 409er, but I could not find a way to delete more than 18 of them simultaneously (though I haven’t tried to be exhaustive).

3. Jaan Parts says:

Strange. I checked the 409-vertex graph. It is completely symmetrical (12-fold symmetry), and coincides with its copy when reflected on both axes and when rotating at angles multiple of 60 degrees.
It is also strange why I did not manage to reduce the graph using two pairs with a distance of 8/3. Your option works. I guess I did something wrong.
To obtain the 387-vertex graph, I did not use the probabilistic approach at all. This is true 387-vertex graph with single 8/3-pair.

4. ag24ag24 says:

Correction: {1/2,Sqrt[3]/2}, {(1+Sqrt[33])/6,0} and {Sqrt[(11/3)]/2,1/Sqrt[3]-Sqrt[11]/6} were already present in the previous list, in a different format.

5. ag24ag24 says:

You’re right about the symmetry – Mathematica misled me – I just checked seeking equality rather than identity and indeed there is nothing missing. For the 387, well, I have not been exhaustive, so maybe you are right – do you have a list of the 22 vertices you were able to remove?

6. Jaan Parts says:

I was able to reduce 409 to 395, again without using two 8/3-pairs. But also did not try this for a long time.

2. I can only add that Tamas also tried back then to reduce some graphs with this method and could only get similar (by 10-20%) improvements in the number of vertices. Even then it was very strange for me, since if we could add any 3 edges, then we could even get a $K_5$. But apparently adding 2 edges doesn’t help much. I think another idea worth exploring is that now we know that $p_d\ne 0$ for many values of $d$, so we can contract (almost) any two vertices of a unit-distance graph. Could this significantly reduce the number of vertices?

1. ag24ag24 says:

I’m not sure how it could, but I will think more. Meanwhile here is another idea: maybe we should look for additional smallish graphs that can’t have three edges added, because the juxtaposition of those edges matters. For illustration: suppose we have a graph that can only be 4-coloured if at least one of {(a,0),(0,b)}, {(a,0),(0,-b)} or {(-a,0),(0,b)} is mono. Then we can just union that graph with its reflections in one or both axes and bingo, we have a graph in which at least two of the edges of the rhombus (the fourth edge being {(-a,0),(0,-b)} must be mono, so suddenly we have a length that has p at least 1/2 and we’re done. Worth a shot?

2. This is very interesting! Another option is to have 3 edges from the same vertex of the form (where I use complex number notation) like (0,z), (0,-z), (0,w).

6. ag24ag24 says:

Thanks again Jaan. Yeah, I see eight vertices in the 387er that are not in the 409er. How did you find them? I checked that (-4/3,4/3) must be mono (yes) and I see that both of its 60-degree rotations can simultaneously be bi. Thus I rotated it by 60 and 120 degrees and took the union, giving a 403-vertex graph whose 60o rotations of (-4/3,4/3) must both be mono, and then tried to delete vertices while enforcing just one or the other of those pairs being mono; I was able to get back down to 387 but no further.

1. Jaan Parts says:

I added different orbits to 409, then I tried to reduce it (and obtained 403er), while maintaining 12-fold symmetry. Then I got 387 by breaking 403er to 4-fold symmetry. You have gone my way in reverse direction.