Polymath16, eleventh thread: Chromatic numbers of planar sets

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 [0,w]\times\mathbb{R} is k-colorable. Then of course w(1)=-\infty and w(k)=\infty for every k\geq 7. Furthermore,

\displaystyle{w(2)=0, \quad w(3)=\frac{\sqrt{3}}{2}, \quad w(4)\geq\sqrt{\frac{32}{35}}, \quad w(5)\geq\frac{13}{8}, \quad w(6)\geq \sqrt{3}+\frac{\sqrt{15}}{2}.}

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 \mathbb{Z}[\omega_1,\omega_3,\omega_4] to an infinite strip.


42 thoughts on “Polymath16, eleventh thread: Chromatic numbers of planar sets

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


    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 \sqrt 3 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?

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

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

      3. Sorry. I meant the tessellation in:


        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.

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

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

  3. There is another tessellation with rational coloring number k_r=6\frac67, 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 k_r=6\frac{9}{11}, 6\frac45 and 6\frac34. Corresponding decimation sequencies are (11001100110), (110011001100110) and (1100). Color ratios are 11^6:9, 5^6:4, 4^6:3. It seems all of these tessellations are valid. One need to check them.

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

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

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

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

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

      2. 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 11^6:9-coloring first.

      3. I’ll do it a bit later. Better I’ll start with simple case.
        Here is a tessellation with 7^6:6-coloring and k_r=6\frac67. (I’m not sure already;)

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

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

    3. 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 7^6:6-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 11^6:9-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 4^6:3-coloring, I’ve found, contains about 3 times more [eveve]-chains:

  4. There is a simple claim, that might be useful:
    If some vertex connects tiles with c different colors and only k colors are used in tessellation, then unit circle with the centre at this vertex can be crossed only by at most k-c remaining colors.
    (This is due to the fact, that such unit circle is contained in exclusion zones of all c 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 k\ge7. Second tessellation has 5-valent vertex, and corresponding unit circle is crossed by 3 tiles, which cannot have the same color simultaneously, hence k\ge7.
    For pentagonal tessellation c=4 (tiles 1…4 on picture below), hence for k=6 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 k=7 colors.

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

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

  5. 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 r=\frac{1+\sqrt5}{2} \sqrt{\frac{15+\sqrt5}{10}} \approx 2.12426.

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

  6. 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!

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

    2. 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 \varepsilon such that if G is a (1,d)-distance graph, then it is also a (1,d’ )-distance graph for every d-\varepsilon<d'<d+\varepsilon. 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.)

    3. 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 s/v? How does it relate to edges density e/v? Here s, e, v are the numbers of Moser’s spindles, edges and vertices. The best known bound for edges is e \le v^{4/3}, see interesting pictures here:

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s