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

Here’s a brief summary of the progress made in the previous thread:

– Let w(k) denote the supremum of w such that is k-colorable. Then of course and for every . Furthermore,

Colorings that produce these lower bounds are depicted here. The upper bound for k=3 is given here.

– The largest known k-colorable disks for k=2,3,4,5 are depicted here.

Presumably, we can obtain descent upper bounds on w(4) by restricting (a finite subset of) the ring to an infinite strip.

### Like this:

Like Loading...

*Related*

For completeness, let me just re-record here that Philip’s disk for k=6 is shown here:

https://dustingmixon.wordpress.com/2018/06/16/polymath16-seventh-thread-upper-bounds/#comment-4851

I’ve been trying to deform it in such a way as to cover a sphere with two copies of it, suitably juxtaposed, but I haven’t succeeded yet. If this were possible it would be of interest, because as of now the best tilings of surfaces of spheres are extremely boring (tetrahedron, square pyramid, dodecahedron) with the sole exception that a sphere of circumference exactly 4 can be 4-tiled as an octahedron.

Another line of enquiry that might be interesting is to identify tight bounds on k-colorable regions other than infinite strips. For example, we currently have that a rectangle exceeding 1 x cannot be 3-tiled (because a 4-chromatic UD graph can be drawn inside it); do we have a way to 3-tile a rectangle of exactly that shape? What about other shapes?

Aubrey, could you show your almost fine 36-tiles 6-colored sphere tessellation?

I don’t have a picture of it, but it is derived from the tesselation of the plane with two distinct tile shapes (the one that Tom showed was not quite 7-tileable): centre a pair of curved triangles at each vertex of an octahedron, then three of the other shape (as opposed to four for the plane) can meet at the centre of each face of the octahedron.

Hm, which Tom’s tessellation or tile shapes did you mean? I don’t understand, sorry. Did you replace every face of octahedron by 4 tiles?

Oh, yes, every vertex gives 2 tiles and every face 3 additional tiles, 12+24 tiles in total.

Sorry. I meant the tessellation in:

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

Let the tile coloured black in the left-hand panel be A and the one coloured black in the right-hand panel be B. Then place two A’s symmetrically at the North pole of the sphere, so that the pole sits at the centre of their shared edge. Do the same at the South pole and at four points on the equator, and orient them perpendicular to each other in the same way as for the plane. Then each face of the octahedron has three of tile B meeting in its centre and three halves of tile A at its corners.

I was for a second earlier;) Yes, I got it. Here is a Picasso projection of what you mean. Apologies for handmade picture. Two upper and two lower tiles are the same ones.

Exactly right. It is really annoying that it doesn’t quite work!

Since previous thread is not active already, I will repost here my question.

Consider any periodical tile based tessellation. For such tessellation there exists some colored pattern by witch one can cover the plane back to back using translations only.

Is it true, that for any periodical tessellation one can find “one-dimensional” pattern?

Other words, one can convert any initial pattern to almost straight connected string with the same set of colored tiles. Single vertex connections are allowed.

Some special cases, which cannot lead to reducing of colors number, such as surrounding of some tile by other tile, are out of the question. (One can include them with some reservations.)

11th thread!

There is another tessellation with rational coloring number , based on Pritikin’s design with diamonds decimation sequence (1100110). Four other examples are listed here: https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5685 and here https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5702.

For all of them there exist one-dimensional colored pattern with 7th color period equal to 8. It may be noted also, that momentary period could be exactly 8 for all tessellations, except for Pritikin’s, where it takes two values: 3 and 13 (or some other odd values, depending on the pattern direction).

I have found also tessellations with other values of RCN, namely , and . Corresponding decimation sequencies are (11001100110), (110011001100110) and (1100). Color ratios are , , . It seems all of these tessellations are valid. One need to check them.

One can exchange blue and cyan tiles in one of the 4-tiles row (4th and last) of Tom’s pentagonal -coloring. This will give regular blue coloring (it is a special color).

I produced a lot more pentagonal colorings and posted the results here: https://groups.google.com/forum/#!topic/hadwiger-nelson-problem/SiD4Zicd20A

No new records though. It seems like a color can use 1/8 of the tiles but no less.

That’s great! It is interesting also to get solutions for opposite task: finding a coloring with the largest most-used-color-ratio. The conjecture is that it cannot be more than 1/6. Or will such question give the same set of color ratios, you have found already?

I added results for the maximum density for 1 color (leaving all other tiles uncolored). It seems that .15 is the maximum density for the pentagonal tiling.

Example of tessellation with -coloring, 7th color density 1/9 and rational coloring number is shown below.

Thanks! – um but are you sure it works? Look at the tile coloured 3 whose botom-left corner is at the origin is closer and the tile coloured 3 that is at “one-o’clock” from it. They seem to be inescapeably closer together than the diameter of the tile coloured 4 that sits between them.

Ops, correction is needed.

Sorry for being too fast for you 🙂 A good thing is that even though no one except Dustin can edit their own posts, we CAN overwrite files in the dropbox, and the new version does indeed replace the old one in pre-existing posts linking to it. (I have silently corrected my own mistakes several times by this means!)

Thank you, Aubrey. You are extremely fast;) Why bugs are obvious olny after posing?

It seems, it cannot be corrected. One need to think and try -coloring first.

First, can you make a proper picture of your dot-dash ideas? I couldn’t work them out.

I’ll do it a bit later. Better I’ll start with simple case.

Here is a tessellation with -coloring and . (I’m not sure already;)

I think it’s OK!

“Dash-dot” tessellation with -coloring and 7th color density 1/6.

Other announced tessellations have internal conflicts and require more attention to overcome them (if it is possible at all).

I suggest following notation for 2-colored (or bichromatic) tile chains: v – vertex, e – edge, […] – finite chain, (…) – infinite periodic chain. Examples: [eve] – finite 1e2v1e2-chain, [evvve] – finite 1e2v1v2v1e2-chain, (v) – infinite 1v2v1v2v…-chain, (ev) – infinite 1e2v1e2v…-chain, where 1 and 2 are tile colors. Examples of allowable chains: [eve], [evvve], (v). Examples of invalid chains: [ee], [vev], (ev).

Some explanations and illustrations for “dash-dot” approach.

One can take 7-colorable Pritikin’s tessellation, then remove and/or combine some diamonds to get required property, for example, to minimize (or maximize) 7th color density. One can do it in two steps.

At the first step, one get sketchy Pritisin’s style construction, which shows initial tiles placement. First thing one should do here is to minimize number of conflicts (invalid chains).

Example of such construction with no conflicts for -coloring is shown below. One can see here allowable [eve]-chains (some of them shown by dotted lines).

At the second step, one convert this construction to valid tessellation by means of tiles boundaries correction. Such operation is not always possible due to second order conflicts.

The next example is a sketch for -coloring. There appear invalid [eveve]-chains here (dashed lines). At the first sight it is easy to overcome them via changing middle edge to vertex (marked by small circle). But this operation affects many neighbor tiles. Consider a set of tiles, marked by dotted circle. It seems, the only way to start is to place all 6 tiles into circle with unit radius. This, in turn, requires further transformations of surrounding tiles and might lead to the failure of entire operation.

Best sketch for -coloring, I’ve found, contains about 3 times more [eveve]-chains:

I used a SAT solver to 6-color a square grid with the exclusion set shown in the top-right. It’s interesting that tiles, stripes of 3 repeated tiles, and a hexagonal pattern for each color emerged.

Some more pictures can be found here:

https://groups.google.com/forum/#!topic/hadwiger-nelson-problem/iSEFqdTMlNg

Seems like it’s a warped version of Pritkin’s pattern

There is a simple claim, that might be useful:

If some vertex connects tiles with different colors and only colors are used in tessellation, then unit circle with the centre at this vertex can be crossed only by at most remaining colors.

(This is due to the fact, that such unit circle is contained in exclusion zones of all colors.)

For example, it is easy to show, that all three Aubrey’s tessellations should have at least 7 colors. For first tessellation one of the 4-valent vertices corresponds to unit circle, crossed by 3 tiles, every two of which cannot have the same color, hence . Second tessellation has 5-valent vertex, and corresponding unit circle is crossed by 3 tiles, which cannot have the same color simultaneously, hence .

For pentagonal tessellation (tiles 1…4 on picture below), hence for four nearest tiles should be colored by 2 remaining colors (5 and 6). Similarly, tiles A and B should have color 1, therefore tile C cannot have color 1…6 and tessellation requires at least colors.

Yeah – this looks like a simple observation but it may be quite powerful – it may give rise to a way to streamline the search that Philip has been working on for ways to juxtapose tiles. Philip, are you out there? How is that work going?

Hi I am still out here but have been distracted by so many other things. Still hoping to get back to this though.

A little bit cleaner picture of 6-flower (Philip’s disk) is shown below. One can see here a skeleton from five connected regular pentagons with unit edges (dotted lines). Minimum radius of 6-flower is .

There is a lot of hidden pentagons here in fact. One can think about “pentagonal grid”. Could we spindle it?

I looked at that some time ago but I couldn’t find a useful way forward – but I agree that it deserves more exploration. Since spindling at distance phi equates to a rotation of pi/5, i.e. a rational proportion of a circle, we can quite easily get graphs that have a lot of “unplanned edges”. But I didn’t succeed in finding graphs that have an edge density exceeding the graphs we’ve been mainly focusing on (i.e. ones with a high density of Moser spindles).

Hey everyone,

Things have gone a bit quiet here, so I wonder if it might be useful if everyone could post a little update on the status of their work. I’m hoping that quite a few of you are quietly beavering way on one or another aspect of the approaches we’ve been exploring. Don’t be shy!

Yeah, that’s definitely the case for me. Though I’ve been following this thread, there’s just not much I can add here or post myself currently.

I’m still working on my plan to make some actual plots of how certain variables affect chromatic number, based on the really helpful posts from Jaan and Tom in the previous thread. I feel though that this still might take the one or the other month to really bear any demonstrable fruits.

Aside from that, now that the n-ball graph approach to explaining why tile-based colorings are necessary feels rather complete, I’ve returned to tackling the topological approach to the same issue, using punctured neighborhoods again.

It has felt too deceptively simple the last time I seriously worked on it (at the start of this year), but putting the n-ball approach together has given me new certainty that there’s mileage to that approach too.

Not much news around here either, I guess otherwise people would post. One little good to know fact that was pointed out to me by Laczkovich today is that the https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem can be used when we consider (1,d)-distance graphs. A consequence of the theorem is that in case of a system of polynomial equations in (x1,..,xn,y1,..,yn,d), the values of d for which there is a solution forms a union of intervals such that both endpoints of each interval is an algebraic number. This implies that for every transcendental d and finite graph G there is an such that if G is a (1,d)-distance graph, then it is also a (1,d’ )-distance graph for every . This was conjectured by Tamas Hubai about a year ago. (In fact, he also conjectured the stronger statement that instead of transcendental numbers, this also holds for non-constructible numbers – I don't know whether this also follows from algebraic geometry.)

I have to many questions to afford to be not shy.

Maybe you know about new fractional CN record, 3.8992: https://arxiv.org/abs/1810.00960.

Thanks to Aubrey and D.E. Knuth I finally understand how to calculate CN for large graphs using SAT, but I still don’t know how to get fractional CN. Probably it will be interesting to calculate it for known 5- or almost-5-chromatic graphs.

I reread first threads trying to find the answer, what does it take to be 5-chromatic? There is a lot of thoughts here, which I cannot understand before, but I still haven’t a clear picture. What is essential here? Spindles density, edges density, vertices number, rotations set, something else?

I plan to define spindles density for known graphs. Is there some theoretic bound for spindles density ? How does it relate to edges density ? Here are the numbers of Moser’s spindles, edges and vertices. The best known bound for edges is , see interesting pictures here:

https://math.stackexchange.com/questions/1986369/erdos-unit-distance-problem-maximal-graphs?rq=1

Thanks Jaan! I, for one, had not heard about the new FCNP record. It’s nice to see that the same kind of thinking that led me to the original 5-chromatic graph has related uses. The authors don’t seem to say that theirapproach has reached diminishing returns, so I infer that the key milestone of a FCN exceeding 4 may be within reach!

We have not worked much on spindle density, but one interesting feature is that the spindle density I was able to achieve is actually a bit lower for the 5-chromatic graphs arising from the 30 unit vectors in my graph V than for the graphs arising from the original 18 unit vectors (those in the graph U). I’m unaware of any attempt to identify a theoretical upper bound.

Also, note that the upper bound on e is actually o(1) more than the 4/3 power of v. I believe that only one graph has ever been discovered that exceeds 4/3, though – it has 16 vertices and 41 edges and is due to Ed Pegg:

https://math.stackexchange.com/questions/2575268/maximally-dense-unit-distance-graphs