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

Activity on this project has slowed considerably, as we’ve gone 6 months without having to roll over to a new thread. As mentioned in the original thread, the deadline for this project is April 15, 2019, so we only have a couple of weeks remaining. Dömötör and Aubrey took the time to summarize the highlights of what we’ve accomplished in the last year (see below). While we don’t have a single killer result to publish, there are several branches of minor results that warrant publication. Feel free to comment on additional results that were missed in the summaries below, as well as possible venues for publication.

Dömötör Pálvölgyi:

**Finding 5-chromatic UD graph with few vertices.**The record 553-vertex graph has been published by Marijn, not much news.**Probabilistic formulation.**Here I believe we have quite interesting results, my student is planning to write his MSc thesis on it (due June).**Bichromatic origin.**Here again we have some nice small graphs (in the plane, still looking for them on the sphere), and mathematically intriguing conjectures, which would imply improved bounds for the chromatic number of the space (if we find that graph on the sphere). About an attack on a conjecture by similar copies of almost monochromatic sets with limited success (and known limitations) we will soon publish something with Nora Frankl and Tamas Hubai.**Finding bounds for the width of the largest disk/strip that can be k-colored.**We have some bounds.**Determining the chromatic number of the extended rational field Q[w1,w2,..] for certain wi’s.**I know there are some results here, but what?

Aubrey de Grey:

**Fractional CN.**Jaan Parts has improved on the published record, but no one has yet computed the FCN of a 5-chromatic graph; however I put Jaan in contact with Marijn, who has much better hardware, so that may change soon. Then the question will be to find how to get a FCN above 4; presumably it will need at least a few interlocking 5-chromatic subgraphs, and that might be a clue for a 6-chromatic strategy.**Small graphs in higher dimensions.**There has been a fair bit of interest in my 59-vertex 6-chromatic graph in R^3, which is unpublished, so it should probably be described here. For completeness it may also be worth mentioning my 7-chromatic 24-vertex one in R^4, since it’s the best that has been achieved by explicit spindling and rotating and such like. My gut feeling is that the current records for higher dimensions can be beaten by spindling and rotation if only we can come up with some kind of pan-dimensional modular toolkit with which to build larger graphs, so it may be worth laying out what is so far known as a way to motivate such work.**Upper bounds in higher dimensions.**Philip coded up a nice fast way to find the most efficient colouring of a permutahedron-based tiling in higher dimensions and provided answers for R^5 and R^6; the number is still growing at about 3^n, so there seems to be a strong case for finding better tilings, especially ones in which tiles have fewer too-near neighbours. We should probably include my tiling of the plane in which each tile has onlly 16 too-near neighbours (as against 18 for the hexagonal tiling) as a way to motivate such a search in higher dimensions.**Fraction of the plane that can be k-coloured.**We have improvements (due to Jaan) for k=5 and 6, while Croft’s solution for k=4 remains unimproved (and also solves k=1, 2, 3).**The general concept of clamping.**Three families of 5-chromatic graphs (mine, Marijn’s and Dan/Geoff’s) are constructed by identifying simpler graphs with particular properties of this or that subset of vertices in any 4-colouring, and combining them so as to preclude all such properties being simultaneously true. There is sure to be masses to discover here. Way back in the first thread we had a brief exchange about finding simple M’s at the expense of more complex L’s (using graph names from my paper) but it never really went anywhere. A promising approach could be to find hexagonally symmetric graphs in which there is a hexagon (of non-unit radius) of vertices in which all three colours different from the centre are represented in any 4-colouring; I bet there are human-provable examples of that. We already have ones in which a hexagon of radius 8/3 has to all be the same colour as the centre, and there might be human-provable versions of that too.**Measurable CNP.**Marijn found a graph with 5617 vertices for which (in his words) it was “computationally hard” to find a 5 coloring with the center vertex being bichromatic. Sounds like it’s worth keeping looking for one that can’t be done, which would give MCNP >= 6.**Siamese tilings.**It turned out to be not particularly obvious how to tile the plane with seven colours in such a way that no two points of the same colour are exactly 1 apart but yet there are, irreducibly, separate tiles less than 1 apart. We never did anything much with such tilings, but they do seem to me to be so qualitatively different from ones in which all pairs of tiles are >=1 apart that we should say something about this.**SAT-based approaches to proving the nonexistence of a 6-tiling.**Boris’s original approach couldn’t find unscaleable tilings, but my suggestion for a variation seems to be theoretically more promising; however, Boris didn’t make it work. I think we should document what we did achieve so that others have a starting-point.- On Sept 29th, Jaan optimised Philip’s brilliant 6-tiled disk from June 17th. It ended up making sense! (in terms of regular pentagons)
- Just to be sure we remember: our bounds on Euclidean dimensions of k-coloured things need to include both the largest k-tileable disks or strips and the smallest disks or strips containing a graph that is not k-colourable.

Thanks for the summary. I would like to add that parts of these reflect the state of the project at the end of 2018. Since then there weren’t many comments, but the last few were about the chromatic number of spheres (). We only know that the chromatic number is at least 4 (if the radius is large enough) and we don’t have any upper bound (although 8 should be easy if the radius is large enough). We don’t even know whether the chromatic number is monotone in the radius, not even for tile based colorings.

Yes. All we have that breaks monotonicity is one case for upper bounds, namely the octahedron when the sphere has circumference exactly 4. I think there may be rather a lot of ranges of radii with different things that can be easily or less easily said: for example 7 must be possible for a sphere only slightly too large to accommodate a regular dodecahedron, but I have no idea how far. Some time back I described a 36-tile thing that comes agonisingly close to being 6-colourable; maybe we can revisit that with 7 as the goal. Etc.

You mean that when the unit edge octahedron can be inscribed in the sphere, then its chromatic number is 3? Not sure what the circumference is… Do you mean the length of the equator and your measuring the distance on the surface of the sphere? Probably we should agree on whether we want to measure distance on the surface or in , and stick to it. I’m not sure which would be a better choice.

Ah, apologies. I was going with length of lines on the surface (I think that’s the choice that most past literature has used). And I was referring only to upper bounds, i.e. tile colourings not graphs: the octahedron can be coloured with two tiles of each colour, whereas everything else larger than a tetrahedron needs at least five colours.

I made a section on the wiki about these questions:

http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem#Best_known_results_for_the_chromatic_number_of_spheres

The paper what I’ve read measures chordal distance, so I’ve used these numbers for simplicity. What bothers me is that it seems to prove that the octahedron’s sphere has chromatic number 4, which contradicts the Pritkin type ‘no need to worry about the boundary’ logic. Where is the mistake?

https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S1446788700019315

I’m not seeing the contradiction. Any particular octahedron has CN=3, but that doesn’t mean the whole sphere does. Can you explain it in more words please?

This is not original with me but I can’t find where I saw it, but anyway: we have an upper bound of 5 for spheres small enough to draw a square pyramid, and 6 for spheres small enough to draw a regular dodecahedron.

Oh, an octahedron has 8 facets… Yes, the construction for the sphere of the cube should have CN 3. I’ll add this and the other polyhedron based upper bounds too to the wiki.

Wait, no, the sphere with a cube does not have CN=3! because we can’t colour opposite tiles the same, as we can for the octahedron.

Yes, I’ve also just realized this, that’s why I haven’t added anything yet. These small radii are tricky, I’ll see if I can find some other papers on them.

I find it quite amazing that for a sphere of radius r>1/2 we don’t know a lower bound of 4. This is similar to the Borsuk graph, so we know that at least one color class contains two points whose distance is >1. Can we apply some topological methods to prove that 4 colors are needed? Can we maybe embed some Kneser graph or Schrijver graph as a unit distance graph?

I strongly suspect that the chromatic number of the sphere is not monotone in radius. My former PhD student Greg Malen proved that the measurable chromatic number is not monotone.

If we accept that the measurable chromatic number is the same as the chromatic number, then I agree with you. Especially, because then it follows from what you write… Just for reference, here is the preprint of the paper: https://arxiv.org/pdf/1412.2091.pdf

Thanks Matthew – and Domotor, ha, you beat me to editing your table wrt the dodecahedron case 🙂

It is so extraordinary that no one seems to have noticed until now that it is not easy to 7-tile arbitrary-sized spheres, nor to draw 4-chromatic UD graphs on small spheres. Saturday is my birthday and my fiancee can’t be with me, so I think I will spend it working on those 🙂

Then of course there is the question of 5-chromatic UD graphs on large spheres. One place to start mght be to tae some of our larger 5-chromatic cases in the plane and see if we can remove edges (as opposed to vertices) so as to give a graph with no unit-edge hexagons. That might be bendable around a sphere.

And let me also shamelessly repeat my last comment from the other thread:

Whatever graph can be realized as a unit-distance graph on every large radius sphere, can also be realized on the plane by taking the limit. So I propose to call these generic unit-distance graphs (GUDG) and study the same questions for them as for UDG. Can we make a 5-chromatic GUDG? At least with a bichromatic origin? Can we get a better lower bound on the number of edges than ?

I wonder if we can come up with a set of operations which can produce every GUDG. I’m not sure that we can have a complete characterization, but generating a sub/superclass can be also interesting. For example, we could take the two operations of the Henneberg construction (1: add new degree 2 vertex, 2: subdivide edge with new vertex and add another edge from new vertex) and add spindling to it in the way it was used in the Erdos-Hickerson-Pach paper, i.e., 3: Take copies of the graph glued together at some vertex , and for other vertices, , connect the copies of them, denoted by , where is a binary sequence of length , such that is a neighbor of if and only if and differ only in their coordinate.

Can we get every GUDG with these operations? If not, what further operations do we need? How big can the chromatic number grow with such operations?

I’ve picked up manim (the Python animation library created and used by 3blue1brown) in order to create a video showing why non-tile based colorings aren’t a thing in 2 or more dimensions as animations can convey this far better and make it more accessible than writing and still pictures can. Though I’m more interested in pursuing possible proofs for statements on arc boundaries I feel this would be a more useful and realistic attempt at a final contribution before the 15th April.

What caught my eye in the summary are the Siamese tilings. If I got that correct, wouldn’t the 7-color Reuleaux triangle tesselation qualify as such an example? What other examples do we have of such tilings?

@Bernhard: the only Siamese tiling we have is the one I came up with in response to a question from Domotor, and which you then drew: a stretching of the Pritikin construction so that the diamonds in any one column are more than 1/2 apart. In your version the diamonds had height 1/3 and separation 1/3, which is the maximum admissible height.

Ah, it’s this interlocking pattern, I remember. Although this makes me wonder, can we come up with such Siamese tilings that are not trivially transformable into one another? Having dabbled with topology a little more in the recent months I wonder if there’s parallels to draw there similar to the genus of a torus, this specific type of homeomorphism or another pre-existing concept…

I might just be rambling but my curiosity is sparked either way.

Having occasionally thought about this the past week, here’s what I came up with.

If we group such tilings by the amount of same colored regions within a given exclusion zone then I’d say whenever there are only 2 such regions, they can likely be fused together. 3 is the case we explored back then in periodically returning chains.

And I would conjecture that there’s enough flexibility with 7 colors in the plane to take this further. For instance it should be possible to have some regions with 3 other regions within their exclusion zone (so a total of 4), making them a meeting point with 3 chain-links (or whatever it should be called) rather than 2.

4 and some more chain-links might still be possible, but I’d wager this would stop relatively soon as the chains would interfere with one another.

If so then this might be used to create a whole class of Siamese tilings which couldn’t be converted into one another or a normal tiling.

Alas I currently don’t have access to SketchUp and my workspace the way I used to so this is going to be everything I can deliver on this front for now, and possible generally given the impending end of this Polymath project.

I haven’t been able to come up with a specific use or some predictive capability for such tilings though. Is there something special we could do with this information?

I’m coming along decently with my programming of an explanatory video explaining the emerging patchiness and need for tilings for chromatic colorings.

Heule has created the nice 553-vertex graph which shows this patchiness and I plan to show it as an example, and the SVG certainly would be enough, but if I had the raw data available for parsing I could animate it and highlight the predicted results better.

I have found the data for some other graphs but not this one, is it private or did I just miss it?

I copy here my message, placed erroneously in the previous thread.

I have some progress in FCN. My last FCN record is .

Here is a link to an interesting article about multicoloring: J. Grytczuk et al. “Fractional and j-fold coloring of the plane”, https://link.springer.com/article/10.1007/s00454-016-9769-3.

It helps to better understand what is the fractional chromatic number and gives upper bounds for some -fold chromatic numbers: , , , , , , , .

Multicoloring (or -coloring, or -fold coloring, BCN) is an extension of the concept of vertex coloring in the case when each vertex is colored in some fixed number of colors. In this case, the usual chromatic number (CN) corresponds to , fractional chromatic number (FCN) corresponds to .

I’ve found slightly better upper bounds for some small values. BCN could be interesting because it is possible to calculate it by SAT.

As a first approximation (taking into account known results and inequality ) the following bounds for BCN of the plane are obtained:

,

,

,

,

,

,

,

,

,

.

I have not worked on this task for a long time and I believe that some bounds can be improved rather quickly. It is interesting that to achieve some better bounds is not enough quite a bit. For example for the distance between the tiles should be only 0.64% larger to get upper bound , for it lacks only 0.1% to get .

Also, I have a suspicion that my SAT-formulation is inefficient and not compact (if I have not made any mistakes at all). The number of clauses and computation time increase dramatically with an increase in the colors number . I tested with SAT/UNSAT-programs (glucose and palsat) some small set of graphs and got the following results: , , , , . The ratio does not exceed 4 for successfully tested graphs with and . For graphs of the order of 1000 or more, the computation time exceeds several hours even for , so I interrupted the calculations.

A small clarification to Aubrey’s comment about 5-chromatic graphs with known FCN. We have an example of such graph, see https://dustingmixon.wordpress.com/2018/09/14/polymath16-eleventh-thread-chromatic-numbers-of-planar-sets/#comment-12149.

Several small graphs (with nice FCN) that may be interesting.

One can ask questions like the following:

What is the smallest order of a graph with ?

Is it possible to get such a graph without Moser’s spindles?

It is well known that Moser’s spindle has , the Golomb graph has . It is less known that 13-vertex double Golomb graph also has . Here is it:

The smallest graph with , which I was able to find, is a 23-vertex cat-graph, including quad Golomb and two additional vertices (and no Moser’s at all). It has FCN :

Here is 35-vertex graph with :

Highly symmetric graphs are of particular interest. Among such graphs (with 24-fold symmetry) are the following small ones:

49-vertex, :

103-vertex, :

199-vertex, :

As for graphs with a large FCN, my current record is approaching 3.971. The corresponding graph is not fully processed, but by all indications this estimate should not change significantly.

To date, the following record graphs have been discovered:

547-vertex,

625-vertex,

799-vertex,

The calculation time of their FCN is huge. So the time of one ILP iteration on my computer is about 50 hours (I use full version of Gurobi ILP-solver now) with a total number of iterations of about 1000. Using various accelerating tricks, one can nevertheless get a more or less acceptable calculation time (400 hours for 625-vertex graph).

There is some hope to reach , although the first tested 1021-graph gives something around 3.975.

What else?

It was possible to reduce the nice 745-vertex graph of Jannis Harder (see https://dustingmixon.wordpress.com/2018/04/22/polymath16-second-thread-what-does-it-take-to-be-5-chromatic/#comment-4074), all vertices of which at an Euclidean distance of 8/3 from the origin have the same color as the origin in 4-coloring (which, by spindling, leads to a 5-chromatic graph). As a result, a 547-vertex highly symmetric graph was obtained (which, obviously, allows further reduction, but due to the loss of symmetries).

Very recently (just now), I discovered graphs with the same properties, but provided at different distances from the origin. This, in particular, allows one to obtain rather compact graphs (in the sense of a Euclidean radius). So, the graph forces all vertices on the radius to have the same color, and this property is not lost after trimming it to this radius (the previous record of radius for 5-chromatic graphs was at least 2). The same result is achieved when using the base graph or even but with an increase of minimum trimming radius to .

The graph additionally shows the same properties at a radius .

Here subgraph contains 5 wheels rotated by around common origin, subgraph – 7 wheels, – 9 wheels, – 3 wheels.

Presumably, one can find graphs with a grid of virtual edges of length , , and so on. Maybe it will help to obtain new records in the order of the 5-chromatic graph or move towards 6-chromatic graphs.

Jaan – wow, this is great. To be clear: when you say “the same colour”, do you always mean “the same colour as the origin”? Also, for your multi-wheel subgraphs, do you mean that V_n (where n mod 12 = 7) is V_7 rotated by k/2 arccos (n-1)/36 for k in {0..(n-7)/6}?

Yep, always. I hope to write correctly:

No, these are vertex angles of course

Wrong: these are angles of course

Exp is missing

OK, got it, so always arccos(5/6), i.e. we are still in the usual field. Really terrific discovery!

As for me, I do not like idea of the deadline. Once a month I have a thought, and once a year it turns out to be not completely stupid. Where should I report it?

We have the good fortune that Alexander Soifer is such a strong supporter of this research. I think he will want to cover our work in detail in the forthcoming second edition of his fantastic book, and also he will continue to be interested in reporting all results in Geombinatorics.

I share this concern as well. Further publications on this matter will certainly be interesting and important.

Likewise I’m considering to not merely make the video on the necessity of tilings I’m working on now, but to make an highly animated video series on many of the things that surfaced in the project, such as the Siamese tilings, the Reuleaux tiling whose 100% exclusion rate still fascinates me, as well as the topological and measure based approaches to deriving fundamental constraints.

But what I feel would really be missing is some sort of place to keep publicly or at least semi-publicly collaborating. Something like a forum, a Discord server… something like that. I like the idea of a Discord server along with a Mathbot to render LaTeX and channels dedicated to subproblems, and I could set something like that up too, but I don’t know the types of platforms the other people here would tolerate or actively prefer.

Right guys, I think I have a lower bound of 4 for spheres too large for a unit tetrahedron, i.e. of radius more than 0.563… Please check.

In the plane, consider a parallelogram with edge lengths 1 and 2 and angles 60 and 120 degrees, i.e. a string of four unit equilateral triangles. This shape is a limiting case for the transition between 3- and 4-colorability: it can easily be 3-coloured (since any stripe of width at most can), but if we scale it (in both dimensions) by 1+epsilon we can draw a chain of unit diamonds in it whose ends are 1 apart (I’ll draw a picture if people need it, but basically we just wriggle along the parallelogram, with diamond n being a translate of diamond n-4 parallel to the long edge of the parallelogram), which is of course 4-chromatic.

But this parallelogram, since it is a string of four equilateral triangles of edge 1+epsilon, can be drawn as a tetrahedron on a sphere of radius 0.563…+epsilon. Hence we can do the same construction there, giving a 4-chromatic graph on that sphere.

Do I have that right?

Your proof is correct, but your radius is wrong – for a unit tetrahedron you need In fact, already for a unit triangle you need In the wiki the number 0.563.. comes from projecting the facets of a non-unit edge length tetrahedron to the sphere such as the max diameter of the projected spherical caps is 1. Note that this is not attained between two vertices. At least you won’t run out of problems until your birthday…

Damn! Thanks Domotor. Yeah, the triangles are “hyper-fattened”, I’d missed that. Ah well!

BTW, when thinking about colorings of spheres, I came up with another notion that is somewhere between tile-based and arbitrary colorings. Call a coloring (only) k-mixed if any point has a neighborhood where at most k colors appear. For example, it makes sense to study 2-mixed 3-colorings where color classes separated in a way. Unfortunately I cannot boast with any interesting discoveries, but I think it can be useful to classify colorings depending on how mixed they are.

“2-mixed 3-colorings where color classes separated in a way” should read “2-mixed 3-colorings, which means that color classes are separated in some sense”

OK here is another idea. On a sphere of any radius greater than 0.5, there is an x for which we can place four points A,B,C,D such that AB=BC=CD=AD=1 and AC=BD=x. If the radius exceeds about 0.543, x will be greater than about 0.6, which allows three points P,Q,R on that sphere to satisfy PQ=QR=x and PR=1. Let us suppose we can 3-colour such a sphere. Then we know that at least one of the pairs A,C and B,D must be monochromatic – but we also know that at most one of the pairs P,Q and Q,R can be monochromatic. Thus, I think this means that exactly half of the pairs of points at distance x must be monochromatic. Is that correct?

If so, it remains only to show that the “exactly half” option is impossible. I haven’t yet seen a way to do that – anyone?

Nice! About a month ago I also had the ABCD part of this argument, but I haven’t realized that you can continue it with the PQR. Btw, why do you need x to be greater than 0.6? Isn’t 0.5 enough? Or you want to use it for some further arguments like in Prop 36?

One issue (that we can think about later) is that the probabilities cannot be defined on the sphere as on the plane because of the Banach-Tarski paradox.

Thanks! I got 0.6 (actually 0.5996…) because we’re using chordal distances, so PR/x is less than 2 even when P,Q,R all lie on the equator (and as the radius falls, so do both x and PR/x). I’d forgotten about Prop 36 – does that complete the argument, or does the B-T paradox (which is waaay above my pay grade) mess it up?

Actually I do now see that we can complete the argument for a countable infinity of radii (unless the B-T paradox intervenes?). Let PQ be x and P,Q bichromatic. Then we can identify two points R1,R2 at distance 1 from P and x from Q, which must both be the same colour as Q. But then there is also a point P2 at distance x from Q and 1 from R2, which is not the same colour as Q, so then there is a point R3 at xfrom Q and 1 from P2 that is the same colour as Q, and so on. For suitable radii, there will then be a finite number n such that Rn coincides with P. But of course there are also uncountably many radii for which there is no such n.

Yes, I think that your argument is correct, except for the B-T paradox, because of which we cannot define . At least it shows that there cannot be a measurable coloring. Also, Prop 36 works, in fact, is even simpler. As you wrote, for any PQ of length x>0.6 there are two possibilities to find an R such that PR=1 and QR=x. Denote these by R1 and R2. If R1R2>0.6 (another condition about r), then we get that the triangle QR1R2 is monochromatic with probability exactly half and rainbow with probability exactly half. Creating a rhombus or parallelogram QR1R2S such that S is also at least 0.6 far from the other vertices, we get a contradiction as we have only 3 colors. I didn’t calculate how large a radius we need for this to work.

Ha, your post crossed with mine. Yeah, you had the same idea as me that R1,R2 must be different colours if they are different from Q. I don’t think your construction quite works as stated, because R1R2 could be too big to allow a triangle with third side 1, but my fix for that (iterating rotations) presumably works for yours too – and it also of course means that R1R2 can be arbitrarily small, so there is no new constraint on the radius after all. Ah, and I’m not seeing why your Q,R1,R2,S can’t all be the same colour – where is the contradiction?

But anyway, regardless: how could we sidestep the B-T issue? It would be awfully nice not to have to assume measurability. Can you explain in simple terms why B-T implies that P_d is not defined?

OK, I have now understood why B-T implies that p_d is not defined – we basically get p_d = 2p_d.

Suppose we had a set of points in which all 3-colourings make exactly half of the edges of length x mono (I don’t have such a graph but I bet they can be constructed from multiple copies of ABCD and PQR). Then presumably we could combine multiple copies of that using something like the construction I just derived, to create a bona fide 4-chromatic UD graph. I will think about that…

Q,R1,R2,S can be monochromatic, but only with probability exactly half. I think this is exactly the same as in your crossposted argument (and also the same as Prop 36).

Regarding B-T: The problem is that defining is not possible directly when the coloring is non-measurable. If you check the beginning of http://michaelnielsen.org/polymath1/index.php?title=Probabilistic_formulation_of_Hadwiger-Nelson_problem, you can see that it is done using some tricks and that the appropriate group is amenable. Unfortunately the same group is not amenable for the sphere (or any higher dimensional Euclidean space). I’m also not an expert of this topic, so I’m afraid I won’t be able to provide more details.

Another crossposting… Anyhow, I would also think that the gadget can be usually combined to get a finite UD graph.

OK, I think I have a way to eliminate the “exactly half” case (with the caveat that I still need Domotor to rule on whether the B-T paradox gets in the way). It’s a bit elaborate – maybe it can be streamlined.

Define x as a function of the radius as before (i.e. wrt my ABCD tetrahedron), and let the radius be strictly greater than the minimum value that allows a triangle of sides x,x,1 on the sphere. Since we are only interested in radii less than , it turns out that x is always less than = 0.8016…

Then let the distance PQ be x and the pair P,Q be bichromatic, and identify R and S as the points at distance x from Q and 1 from P. Define R2 as before – most simply, it’s the reflection of S in QR – and S2 as the reflection of R in QS. Then define Rn and Sn iteratively. Find the minimum n for which the distance RnSn (which hereafter we denote as y) is greater than x but small enough to let us make a triangle on the sphere with sides y,y,1. We won’t be using the intermediate Ri and Si below, so for simplicity we now just rename Rn and Sn to R and S respectively.

As noted earlier, R and S are the same colour as Q and thus each other. Now, for each P,Q-like pair there are two R,S-like pairs (i.e. pairs of points at distance y) – one at x from Q and 1 from P, and the other at x from P and 1 from Q. Conversely, for each R,S-like pair there are two P,Q-like pair there are two P,Q-like pairs (i.e. pairs of points at distance x) that give rise to that R,S pair. Also, because triangles of sides y,y,1 exist, we know that at most half of the pairs of points at distance y are mono. Since exactly half the pairs of points at distance x are mono, that means that NONE of the R,S pairs associated with mono P,Q pairs can be mono.

But now, we can rotate again. Consider a mono P,Q (say it’s colour 1) and let its R and S have colours 2 and 3 respectively. Then we identify T as the reflection of S in QR. Identify the point U that’s at distance x from Q and distance 1 from R and T. The U,Q pair must be mono, so T must have colour 3. So that means the pair S,T is mono (both colour 3). Now check whether the distance ST is in the range that allows triangles with two such sides and the third side 1. If it isn’t, keep going: make T2 as the reflection of S in QT, T3 as the reflection of T in QT2, etc until the distance STn does allow such a triangle, Rename Tn as T and let the distance ST be z. Note that T is an even number of steps from S (where the original R was one step from S), so we still have S,T mono.

But wait: that same pair S,T can also be constructed if we start with P,Q bichromatic, and in that case it’s also mono. So all pairs of points at distance z are mono – which is impossible because we can make a triangle with sides z,z,1.

Have I messed up?

I’m a bit tired and failed to fully digest this. My main concern is that if you can find far enough Rn and Sn, then why can’t we do the same in Prop 36 for every d? This would be a great improvement there.

Well, just because in the plane we don’t have the equivalent of the ABCD tetrahedron that defines an x with p_x = exactly 1/2, so the argument can’t even begin. Right?

test

For some reason my comment won’t post, but you can read it here:

https://math.wordpress.com/2005/11/23/hello-world/#comment-139

I’m posting this for Domotor, who for some reason couldn’tget it to appear.

I might overlook something, but I think that something similar to your method will prove that in the PLANE we have for every .

Proof. Take a circle of radius d centered at O. Pick a point A1 on the circle. Let B1 be another point on the circle such that A1B1=1. Let A2 be another point on the circle such that B1A2=1, etc. Assume . Then (with probability 1) either each Ai has the same color as O, or each Bi has the same color as O. Pick 4 indices i1,i2,i3,i4 such that for any pair j,k. This can be indeed done except for a few , for example (but luckily we already know that the statement holds for these d from earlier proofs). But then for any distance we know that , and from our assumptions, also due to our construction. Moreover, since all the Ai are monochromatic at the same time, also all of them need to be different from each other (and from O) at the same time. But this is impossible, as we have only 4 colors.

Note that the upper bound we get from this proof tends to 0.5 as d tends to 0.5.

What I like in this proof (if it’s correct) is that the only fact it uses about the number of colors that it’s less than the kissing number. So let me conjecture (why not?) if nobody has done so before that the chromatic number of any is equal to its kissing number.

Come to think of it, we don’t even need this if we slightly alter the construction; instead of rotating always around O, we could also rotate around any Ai (as is also done in the proof of Prop 36), so the bound holds for every for any number of colors. (This kind of makes my conjecture ill-funded but it’s so nice that I’ll go with it anyway.)

Though I don’t think I’ve heard the kissing number/chromatic number conjecture anywhere else before explicitly, I think I’ve seen it at least implied. I’ve also briefly conjectured in this direction myself when I first heard about the E_8 and Leech lattices. My thoughts went to Permutohedron constructions since those have a lot of great properties for tesselating spaces, and assuming that the most efficient coloring is based on Permutohedrons, or something similar I’d be fairly certain the the chromatic and kissing number are at the very least very closely related. Something like… CN=KN+n-1 or what have you. There’d have to be some sort of very similar structure.

What threw a wrench into those thoughts were the arc boundary tesselations I first saw thanks to Aubrey. It was also around this time I lessened my focus on the geometry and instead started stabbing at the fundamental constraints with topology, set and measure theory, of which the last is the only really tough customer, on which I just can’t seem to find the necessary intermediate steps no matter what I do.

If I had to conjecture then we don’t have the flexibility to actually find a 6-color tesselation of the plane, and non-tile based colorings are off the table anyway.

With 3 dimensions I can certainly imagine a super specific arc boundary severing enough connections to push the chromatic number down to 14. Maybe even 13, though I doubt that.

12 though as with the kissing number? Having spend weeks on the according Honeycomb I can’t even begin to fathom what sort of shape would severe enough connections to drop 3 whole colors.

I’m curious to look into the possible connections between KN and CN but I’m blanking on any concrete conjecture to chase. For now I’m busy with the video a few more days anyway. Since the deadline has passed… I’ll just put some extra details in, try and make this accessible and understandable to a wide audience. It was certainly nice to see the patchiness in Heule’s 553 graph animated and highlighted.

Talking about the passed deadline… now what? Is this place gonna actually be locked some time or will there just be no new threads/wiki updates?

Yeah, CN=KN+n-1 seems more plausible.

Something about this kept popping into my mind regularly since yesterday.

So, on one side we have highly regular structures, such as permutohedra honeycombs and lattices.

On the other side we have arc boundary constructions and a looming possibility of non-lattice arrangements for kissing numbers too.

A deeper look at different types of tesselations, their duals and also other ways of turning one honeycomb into another has generally shown to me that in 2 and 3 dimensions there doesn’t seem to be too much hope for better chromatic numbers than 7 and 15 respectively. Arc boundaries can sever some connections, but we need a lot of severed connections to drop even a single color.

If however there are non-lattice kissing numbers, I would assume most likely in the dimensions leading up to those with new extreme symmetry (such as 8 and 24) I could see how they at the same time might predict less symmetric most efficient tesselations, using arc boundaries to drop needed colors below what a more universally symmetric construction can do. If so then the CN and KN might respectively be bound not to one most efficient rule of tesselating, but 2 (or more) that alternate depending on the number of dimensions and resulting possible symmetries.

I suppose this might be a conjecture I could chase… many years down the road if I keep my hobby investment and fascination with this up for so long.

Though the idea sounds interesting to me, I think actually looking into it further is way above my head for now. I’ll just keep it around here to look back on in case I decide to go for it some other time.

I think I follow that… yeah I think it works! Basically you are extending my approach simultaneously to the (up to) six distances between your four A’s – right?

By the way, I just dug out what someone told me way back in the first thread about strict inequality symbols: within the latex dollars you can still use “& l t ;” and “& g t ;” to get the simple angle brackets. (Without the spaces, of course!)

Nice conjecture! It seems to be consistent with what’s known… the numbers at https://en.wikipedia.org/wiki/Kissing_number_problem stay between the known asymptotic bounds on CN for R^n. I haven’t found whether there are known asymptotic bounds for the kissing number.

Yes, I also couldn’t find anything about it, except for these complicated bounds in the comments section here: https://oeis.org/A257479

Some thoughts towards the human-verifiable proof (for the chromatic number of the plane ).

Starting from graph I have found 409-vertex graph with Euclidean radius only and monochromatic pair of vertices with coordinates and in 4-coloring (see picture below).

Vertex coordinates are available here:

https://www.dropbox.com/s/msbtrhd5gs8ajsn/g409c.vtx?dl=0

This graph has 409 vertices, 2046 unit-distance edges, 912 cliques, 186 Moser’s spindles, vertex degree in range 6…30. It includes 17 unit-distance 7-vertex wheels, 12 unit-distance 6-vertex almost-wheels (see yellow, green and blue vertices) and three 8-vertex constructions (including monochromatic pairs of vertices), which I called the sliding bridge (see blue vertices). Interestingly, a similar bridge appears also in more compact graphs with other Euclidean distances between equally colored vertices in 4-coloring.

The graph allows further reduction (397-vertex with 4-fold symmetry). Two copies of such graph with an additional edge lead to 5-chromatic graph. This is not so far from record graphs of Marijn Heule. In some ways, the resulting 5-chromatic graph is even simpler, since it splits into two subgraphs, connecting only at two vertices, and has a fairly strong 12-fold symmetry.

The graph has the following additional properties in 4-coloring:

– all 5 wheels centered at the graph origin (shown in yellow) cannot contain a monochromatic triple;

– all 6 wheels with centers on a radius of from graph origin (some of green vertices) cannot contain a monochromatic triple;

– all large diagonals of 6 rhombuses that make up the bridge (see blue vertices) cannot be monochromatic (that is, this gives virtual edges with lengths of and )

It remains to figure out what caused these properties and how they force a pair of extreme vertices of the bridge have the same color.

I try to write not parsed expressions differently (it seems used minus sign causes error):

What I would be very interested to know is how much smaller these graphs can be if we combine them with the results of the probabilistic approach. We can use 0 < > 0.5 for a wide range of values; for simplicity, suppose we could use it for all d. This would mean that we can add two additional edges to a unit distance graph or, alternatively, we can merge any two vertices of a unit distance graph to obtain a new graph whose chromatic number is still a lower bound for the CNP. Would any of these tricks significantly reduce the number of vertices in your constructions?

Of course I’ve meant to write 0 < pd < 0.5, just these codes are driving me nuts…

Hmm, I did not understand the question. I have to get into the probabilistic formulation first.

You needn’t get into it at all. My first question is what if two of your edges needn’t be unit edges, how much would that decrease the number of vertices? My second question is what if two given vertices need to have the same color, how much would that decrease the number of vertices?

As an example, note that if we ask the same question with three non-unit edges instead of two, then the answer is that 5 vertices suffice, as K5 can be realized (with 7 unit edges and 3 non-unit edges).

I did not do such research and do not quite understand what the point is. Could you clarify the purpose?

The point is that if this operation makes the graph small enough so that it becomes human verifiable that the chromatic number is 5, then we have a proof for CNP least 5 that doesn’t use a program.

Yes, but we only have edges of unit length to do that. I still do not understand.

Let me try. Suppose we had proved that and are both less than 1/3. Then, we would immediately know that the CNP is at least 5, because there exists a 5-vertex graph (namely, half a hexagon) that has only three non-unit inter-vertex distances, all of which are either or 2, and which thus must have one of those three vertex pairs mono in any 4-colouring, whereas with those upper bounds on the probabilities there must, in any colouring of the plane, be some half-hexagon somewhere in the plane that has none of those three vertex pairs mono, and that therefore has all five vertices being different colours.

So now, in reality we do not have any such bound (though I wonder if we might get it for ). What we do have, though, is that p_d is less than 1/2 for all d greater than 1/2. Therefore, the equivalent logic works if we have a graph in which there are two specific vertex pairs, A,B and C,D, such that in any 4-colouring of the graph either A and B are the same colour or C and D are the same colour. Obviously we already have such graphs, since in your graphs we can dispense with C,D. But with that relaxed condition, it should be possible to remove vertices. The question is, how many? It is tantalising that the geometric mean of 5 and 409 is only 45… if we could find such a graph with under 100 vertices, it’s a fair bet that we could prove the property without a computer.

The next question is where to begin. I think the most promising line of attack would be to use two of the 8/3 pairs in your 409er, so let’s say and . They start out both needing to be mono, and the relaxed property is that one or other of them is mono.

If this works it will be so cool. It was one of he main original goals of the project, and it’s already the result of substantial input from several of us.

Jeez I made a mess of that. I think everything is reasonably intelligible, but Dustin please fix things if you have a moment.

[Done! – M.]Thank you, Aubrey. Something starts to clear up. But again there are more questions than answers.

All three pairs of vertices with distances of 8/3 in the 409-vertex graph are monochromatic. Why do we need to weaken this statement and say that at least one of them is mono? What does this give?

Does the probabilistic argument take into account that if we take several non-unit distances, then, generally speaking, the probability of one event depends on the probability of another? What if, for example, in the presence of one monochromatic pair, the probability of the formation of another sharply increases? (Or is it impossible or does not change the overall logic?)

It is not clear how the geometric mean appears.

Is it normal that some lower bounds (on a wiki page, for example, for 8/3) are greater than upper bounds?

I’ll answer those questions in increasing order of difficulty!

3) My comment about the geometric mean was really jsut frivolous speculation. I have no real reason to suppose that the smallest graph with one of two specified edges mono will have somewhere near that number of vertices. Please ignore that.

4) The cases where the lower bound is greater than the upper bound are simply those that lead directly to the proof that the CNP is greater than 4. Remember that the table is for 4-colourings: I think the only things we know about higher-order colourings are that p_1 is 0 and p_d is less than 1/2 for all d greater than 1/2.

1) The only reason for weakening the statement is that then it is likely that the graph can be smaller – maybe much smaller. One of the main goals of Polymath16 is to find a proof that the CNP is at least 5 that does not rely on computers to verify any properties of any graph. Domotor’s cool realisation is that we would obtain such a proof if we could find a reasonably small graph that has at least one of two specified vertex pairs (both of which must be more than 1/2 apart, of course) the same colour in any 4-colouring. The smaller the graph, the shorter the proof that it has that property; therefore, the hope is that we can find a small enough graph that the proof is human-derivable (in a publishable number of pages!).

2) The probabilities are actually not dependent on each other, because they are not defined in terms of any particular location or orientation of any particular graph in the plane – they are defined in terms of all such locations and graphs. The statement “p_d is less than 1/2” simply means that in any 4-colouring of the plane, fewer than half of the pairs of points at distance d from each other are the same colour – no graphs mentioned yet. So then if p_d1 and p_d2 are both less than 1/2 and we have a graph that has vertices A and B that are d1 apart and also two vertices C and D that are d2 apart, and then we colour the plane, then we know that out of all the infinitely many places and orientations that we can place our graph in the plane, there will be some in which A and B are different colours and C and D are also different colours, because fewer than half of those infinitely many copies of our graph have A and B the same colour and also fewer than half have C and D the same colour. (I’m playing fast and loose with fractions of infinities, of course, but that’s OK in this case, trust me.) So if we have a graph in which either A is the same colour as B or C is the same colour as D in any 4-colouring, we have a contradiction, which means CNP must be greater than 4 (because the P_d’s are all defined in terms of 4-colourings of the plane). Note that d1 and d2 can be equal; in the case I’m suggesting you explore, they are both 8/3.

It seems to have come to me. It is proposed to throw out vertices from the graph until at least one of the two fixed pairs remains monochromatic. (And when it will be clear with the proposed four of vertices, play with all possible combinations of fours up to isomorphisms.) So?

Yes, exactly, throw out as many vertices as you can without allowing a 4-colouring in which neither of the two pairs is mono. I don’t think there is any need to look at other pairs of vertex pairs, because you would be starting from a weaker condition on the 409er and thus it is very unlikely that you can delete a larger number of vertices than with the suggested pairs while still retaining the required property. (We really need a name for the property: I’m going to call it “semi-mono”.) When you have your minimal semi-mono graph, show it to us and we’ll all see whether we can figure out a human-comprehensible proof that it is semi-mono.

Addendum to answer 2: of course the generalised version of Lemma 17 also applies for any number of colours.

Many thanks Jaan – a lovely graph! Not sure there is all that much in it that is fundamentally new, though – we already had graphs enforcing mono at distance 8/3 (Jannis and Marijn; see the second thread, posts starting on April 28th), and the rhombus properties follow directly from that – but it’s great to have a compact one with so many triangles that can’t be mono.

I feel we really ought to look hard at building graphs with a lot of edges of length 8/3 and spindlings thereof. If we can find one that (for example) forces just one 6-wheel (of a component Parts graph, presumbly) to have a mono diagonal in any 5-colouring, the chase would be on for a counterpart of my graph L that requires a mono triangle in any 5-colouring. Or of course there could be much more elaborate clampings, such as in Geoff and Dan’s “new proof” paper.

Yes, you are right about rhombuses. But I meant reverse causation.

I set myself the task to get an analogue of a half-Moser’s diamond for 4-coloring. Graphs of Marijn are not suitable because they require multiple links between subgraphs. The graph of Jannis is not compact.

Trimming the graph , I obtained a graph with Euclidean radius of and distance between two vertices with the same color in 4-coloring. Minimum radius of such graph is somewhere between and .

Nice! Show us! The spindling of two of those must be really close to fitting inside a 4-tileable shape.

The picture is not interesting: too many vertices (several thousand).

Oh, it’s still interesting because of the 4-tileable question (above). What are the coordinates of the two forced-same vertices? Also, is the graph still hexagonally symmetrical? If so, I bet you can find lots of specific radii less than one at which you can remove the vertices without losing the forced-same property.

It is 12-fold symmetric (hexagonal). Forced vertices coordinates are .

I did everything I could to thin the graph while maintaining symmetry. I do not think that it is possible to significantly reduce the number of vertices due to the loss of symmetry.

Judge for yourself. Numbers are vertex degrees. This is a reduced version already.