Polymath16, tenth thread: Open SAT instances

This is the tenth “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:

– We have new results in the probabilistic formulation, namely, Proposition 36 and Lemmas 38 and 39.

Jaan Parts refined Pritikin’s analysis to prove that every unit-distance graph with at most 24 vertices is 5-colorable, and every such graph with at most 6906 vertices is 6-colorable.

Domotor, Frankl and Hubai showed that, if there exists a k-chromatic unit-distance graph with a bichromatic origin such that all its neighbors are in the upper half-plane and all their coordinates are rational, then CNP is at least k.

At the moment, there are a few outstanding SAT instances that we’d like to resolve:

– Philip Gibbs proposed a couple of graphs as possibly 6-chromatic (see this and that). Are either of these 5-colorable?

– Can we find a tile-based 6-coloring of the plane? Such a coloring must satisfy several necessary conditions.

– Aubrey has suggested a new take on Boris’ pixelated colorings by SAT solver. I have heard offline that the details of this approach are evolving.

131 thoughts on “Polymath16, tenth thread: Open SAT instances

  1. There are some problems with the sections on tile-based and non-tile-based colorings as linked in the initial post.

    “Intuitively, a colouring of the plane using the minimum number of colours will surely be a tiling. However, this is not necessarily so, and indeed the possibility that a non-tile-based 5-colouring of the plane exists has not been ruled out.”

    Actually we can rule out any chromatic non-tile-based coloring for dimensionality 2 or higher.
    Put as concise as possible, every unit distance graph can be expanded into a unit distance n-ball graph, and every unit distance n-ball graph is homomorphic to such a unit distance graph.

    So for instance K_2, 2 vertices at unit distance, can be embedded and expanded in \mathbb{E}^2. The resulting n-balls are homomorphic to K_2, they can be 2-colored, and explicitly only through filling the n-balls. No non-tile-based coloring is possible.

    This property holds in general for proper n-ball graphs. For every complete n-ball graph no n-ball can contain more than a single color, and for every critical n-ball graph some n-balls have to have only a single color.

    Assume the use of 1-colored regions locally homeomorphic to \mathbb{X}^{\cup\circ\infty}(x \in \mathbb{E}^n), n-dimensional Jordan–Brouwer separated spaces, is avoidable for G_{n} where n\geq 2.

    The De Bruijn–Erdős theorem states that for every infinite graph with a finite chromatic number \gamma(G_x)=k, there exists a finite k-critical graph. Such a critical subgraph G_{nk} can be embedded and expanded in E^n, giving us another infinite subgraph G_{nke}.
    If it would be possible to efficiently color the entirety of G_n without such regions, the same would have to apply to the simpler subgraph G_{nke}. We know that such n-ball graphs expanded from finite k-critical graphs contain such continuous regions that can only be 1-colored in a k-coloring, a contradiction.

    I have more details in my paper, which isn’t yet published anywhere. While I want to publish it on arXiv (which would require endorsement however) there’s still work I want to do on the document, specifically on proving the necessity of diameter 1 tiles. We’ve already seen hints of homomorphisms of close vertices in high density graphs, that strikes me as the right direction to look into.

    1. You cannot beat the unit width with ‘nice’ tile-based coloring. If your tiles are such that no 3 ever meet in a point, then they slice up the strip (with further possible small islands that have only one neighbor), and each slice will have a unit distance. If there are 3 tiles, colored, say, 1, 2, 3, that meet in a point x, then draw a unit circle around x. Consider the part of the top arc of this unit circle contained in the strip. None of its points can be 1, 2 or 3, yet it has two points at unit distance, so it needs colors 4 and 5.

      This proof doesn’t rule out the case when you drop niceness, and consider different colorings of the boundaries. But I think with a little care it can be improved to prove an upper bound <1 (for tile-based colorings). For example, already the above proof shows that 3 tiles can meet only very close to the centerline of the strip (as happens in your figure).

      It would be also interesting to see a unit distance graph that fits in a narrow strip (or at least a graph with a bichromatic origin).

      1. It seems OK. But I don’t understand your last comment about trichromatic origin. Maybe because I don’t understand much more. Could you provide some specific example of such graph? How it connects to tile based coloring?

      2. Thank you a lot. I think I understand the backbone of the idea of bichromatic origin. Your recent post was more clear to me because it is more visual (though it takes a lot to search for nonagons). I mean this:
        Now I have difficulties to understand the conjecture for using bichromatic vertices to bound CNP. There is a some special graph G, the origin v_0, a set of unit distance neighbours (for example, 14 vertices v_{1…14}), a set of circles C_{1…14} with centers v_{1…14}, colored red & blue (why?). And then muddle appears in my head. The same happens with bichromatic pencil too. Could you help me to gain an understanding? Do we allow at the start for v_0 to be bichromatic or not? If not, let it be yellow. What next?

      3. Yes, exactly here my brains switch off. At the bottom, yes. There are origin, neighbour vertices, circles, it is OK. But starting from the coloring I loose the thread. I do not understand what happens and why. Could you start again from this moment?

      4. So the point is that if you have a neighbor, v, of the origin, that is red, and the unit circle around v also contains a blue point, then you can conclude that v is neither red, nor blue, because unit distances are forbidden. So if you could simultaneously do this for all vi neighbors of the origin, the none of them could be red or blue, so you could consider the origin to be bichromatic. But of course, when you try to do this simultaneously, then the position of the neighbors must be as in the unit graph we are trying to embed. Did this help?

      5. Not quite, sorry. Maybe it will be better to start with definitions, not with coloring. I will enumerate paragraphs to simplify the navigation.
        1. I read the following (from wiki): “Suppose that we have an (embedded) unit-distance graph G with a special vertex v0 that doesn’t admit a 4-coloring if v0 has two colors, i.e., none of its neighbors can be red or blue. We want to argue that in this case the chromatic number of the plane is at least 5.”
        2. And I understand it so (tell me where is my mistake): “We have some special graph G with monochromatic origin v0. Monochromatic means that we cannot use for v0 one of two (or more) colors after any 4-coloring of all other vertices of this graph G. Other words, we have no choice for v0 after any 4-coloring of all other vertices. We have such graph G. And this leads directly to the conjecture: the chromatic number of the plane is at least 5.”
        3. I can understand it otherwise, but this is more probable case. I mistrust it because I cannot see here “bichromatic vertices”. I define for myself the bichromatic (or m-chromatic in common) vertex as some given vertex of some given graph such that it is possible to color this vertex by any one of two (or m) colors after some special (not every) k-coloring of all other vertices of G (k=4 here).
        4. I don’t understand phrase “v0 has two colors”. Is it the same as “we can choose for v0 any one of two remaining colors”?
        5. Or maybe the word “embedded” has some special meaning? Is the graph G a part of some other graph? Can I assume, that there is no other graph here?
        If there is no mistake up to here, we can continue with coloring.
        6. So we have 4 colors: red, blue, green, yellow. We have special graph G with monochromatic origin, colored red. We have fixed number n of unit-distance neighbor vertices v_{1…n}. Every such vertex has its own set of neighbor vertices, and every such set has the vertex, colored blue already. As result all vertices v_{1…n} can be colored only green or yellow.
        Is there some mistake here? If no, we can continue.
        7. I read then: “you could consider the origin to be bichromatic”. I cannot understand it. I think (following my definition), we can use term “bichromatic” only if there is a choice of color for origin (it can be colored in our example red or blue) AFTER coloring of all other vertices. But we start from coloring origin red, and only then try to color its neighbors. Therefore the origin remains to be monochromatic.
        8. I read: “Conjecture. In any non-monochromatic coloring of the plane with finitely many colors, we can find any such configuration.” Should I understand “finitely many” as any number, for example, 100 or 1000?
        9. Now (as opposed to 6 some new graph Gb appears) I understand this conjecture so (without circles): “We have some special unit-distance graph G with monochromatic origin colored red (and we use 4 colors only). We can have any number of such graphs, but we can choose any graph we like. The origin of this graph has n neighbors v_{1…n}. The conjecture: we always can find some other graph Gb that includes the same vertices v_{1…n} and excludes blue for all of these n vertices.”
        10. If this is right, then the role of graph G is not very clear for me, because graph Gb should already contain the origin v0 and vertices v_{1…n} and should be more complicated than G.
        I think there is lot of my mistakes and I’d like to see all of them.

      6. I’m afraid that already your interpretations 2 of 1 is incorrect. Maybe it’s best if I give an example. Consider the triangle ABC. This is a 3-chromatic graph. Fix one of its vertices, say A, and call it the origin. When I say that a triangle graph with a bichromatic origin, then I mean that we need to use two colors for coloring A. For example, A can be red and blue, B can be yellow, C can be green. A triangle with a bichromatic origin is a 4-chromatic graph.

      7. Jaan – it may be easier if, instead of defining the origin to have two colours, you just think in terms of standard colourings and you ask the question whether a colouring of a given graph exists in which only k-2 colours are used by the neighbours of the origin.

      8. Or, imagine that instead of one bichromatic origin, v, you take two copies of it, v1 and v2, that you both connect to all neighbors of v and also to each other.

      9. I know, I’m stupid.
        How can “we need to use two colors for coloring A”? Every point of the plain can be colored only with one single color. We have to choose: red or blue. Not red and blue simultaneously.
        Aubrey, you are right, it would be much easier. I assumed standard coloring everywhere. So, it is non-standard coloring, and non-standard terminology, right?
        Domotor, should I imagine half-Moser-diamond with an additional edge between v1 and v2? Or something like tetrahedron, projected on the plain? What is the reason to introduce such difficulties?

      10. What I wrote is general, v can be a part of any graph. A triangle with a bichromatic origin is equivalent to a tetrahedron. A diamond with a bichromatic degree-2 vertex is NOT the Moser-spindle, but there is some similarity in the main idea of the construction, I suppose. I’m not sure how I could explain this better. Have you read this (with the answer)? https://mathoverflow.net/questions/299616/ Maybe it helps.

      11. Yes, I have. But now I’m not sure, that I understand it. Did you imply there non-measurable sets of colored points or tile-based coloring?
        By the way, the definition of bichromatic pencils is more clear for me: the origin is colored with single color only and I don’t need to crack my head to imagine two-colored points. The pencil is given by angles between lines with common point and we can move and rotate it looking for position and orientation such that all lines of the pencil will cross somewhere (the distance is not constrained) some other common color, right?
        But vertex is 0-dimentional object… Could you give the definition of bichromatic vertex? And monochromatic?

      12. It is for any (thus non-measurable) colorings. You get the required statement that we need exactly by replacing lines by unit disks that go through one point, where the angles of their tangents is fixed.

        Bichromatic point is indeed meaningless. In a graph coloring you can require that a point gets two colors instead of the usual one – that is what we call bichromatic vertex. Then since in the plane there are no bichromatic points, we need to simulate such a vertex with the help of d+1 points, where d is the degree of the bichromatic vertex. One of these d+1 points is where the vertex is embedded to, while the other d vertices lay on the unit circles around its neighbors, one on each, and they must be colored with the same color, moreover, this common color must differ from the color of the point where the bichromatic vertex is embedded to. This guarantees the simulation.

      13. Than you, I hope I get it. A 4-coloring of the plain cannot contain bichromatic vertex. And if we can forces such vertex, it leads to CNP is at least 5. Conjecture is that we can do it.

    2. Probably, some connected k-colorable tile based tessellations for k=5 and k=6 can provide more information than used. I mean something like this:
      Some widest known k-colorable flowers (not truncated) for k=2...5 are shown here:
      Flowers with 4 and 5 colors are extendable, but their minimum radius remains the same.
      One can note the following for 4 colors. Moser’s spindle Euclidean radius (\approx 0.904) is more than minimum radius of 4-colorable tile based flower (\approx 0.869). But Moser’s spindle Euclidean width is in range \approx [1.457, 1.732] and it can be placed wholly inside 4-flower if this flower is not truncated. Moreover, it can be rotated staying inside such flower. And it even can be placed inside 4-worm, shown in previous post, but without rotation and free line motion capability.
      The same holds also for k<4 and maybe it holds for k=5 and k=6. So there is a wild conjecture:
      For any number of colors k\leqslant 7 there exist a pair of finite unit graph G with chromatic number k and k-colorable tile based tessellation of finite region R such that all vertices of G lie within R.
      If it is true, there should exist more compact 5-colored graphs. Known most compact 5-colored graphs have Euclidean diameter about 4, but 5-flower has minimum diameter \approx 2.181, and sufficiently compact 5-graph should have approximately the same size (it could have slightly larger diameter because we don't need any truncation of 5-flower and we can extend the flower by adding new petals). It means also that such graph should have more compact building blocks. Searching for such graphs could be interesting direction.

      1. Well, except that we don’t currently have a proof that our 5-flower is the best possible, do we? I can’t do better, but I also don’t see a proof. Do you have one?

      2. No, I have not. The only thing I see is the possibility to extend it. This will give larger flower with uncolored holes.

      3. One can construct 4-chromatic UD graphs that fit into a strip of width exceeding sqrt{3}/2 by an arbitrarily small amount. Take a strip of 6n-1 unit triangles, for sufficiently large n, and colour its leftmost vertex 1, so making its rightmost vertex also 1 in any 3-colouring. Then remove all edges parallel to the strip that join colours 2 and 3, and stretch (and thus thicken) the strip (which now consists of a string of diamonds joined at their sharp corners, all of which must be coloured 1) so that the length of the strip is increased by 1. Then add a second (intact) strip whose left-hand end coincides with that of the stretched strip; it will have a vertex not coloured 1 in any 3-colouring that coincides with the rightmost vertex of the stretched strip.

        By similarly compressing a simple chain one can get a 3-chromatic graph that fits into a strip of arbitrarily small width, but I don’t see how to beat (or indeed reach) sqrt{3}/2 for 4-chromatic.

      4. For k=3 the worm by Jaan has width exactly \sqrt 3/2, and even its boundary can be colored appropriately, so because of these unit distance graphs built from triangles, now we know the exact answer for this problem.

      5. Yes, you are right. But wait, what do you expect at the end? Why \frac{\sqrt3}{2}? Minimum width of the 4-worm (or strip) is \sqrt{\frac{32}{35}}, and yes, now you can freely move your 4-graph staying inside of the strip. The same holds for 2- and 3-strip again. And maybe for 5 colors?

      6. Um – Domotor, what precisely do you mean by “this problem” for which we have the exact answer? Sorry if I’m being dumb.

        I think our knowledge is still consistent with a stronger conjecture than Jaan’s, namely: for no k is there a non-k-colorable UD graph G and a k-tileable region R such that all vertices of G can be located within R. As things stand there are critical distances for k=2 and k=3, namely 0 and \sqrt{3}/2. Domotor – is that what you meant?

      7. He means that we have examples of 3-tileable strips and non-3-colorable graphs whose widths (in the latter case this means the width of the thinnest strip that contains the graph) are infinitesimally different, which is the best one can have. Ditto for 2.

      8. Well, it is obvious: we cannot put in (k+1)-graph inside k-tileable region. But maybe it is possible for k-graph (for any k).

      9. Yes, I’ve just meant that for k=3 we know exactly the largest possible width of a strip that can be 3-colored.

        Regarding Jaan’s ‘wild conjecture’ – I don’t understand what it states… Isn’t this implied by de Bruijn-Erdos?

      10. I mean the following. If the conjecture works, then it could give some hints for minimization of 5-chromatic graph or seeking of 6- and 7-chromatic graphs.
        More strong conjecture is that minimal k-chromatic graph rotation or free moving is essential. This could give some constants for further seeking (for example to find minimal 5-graph building blocks). 3-worm gives \frac{\sqrt3}{2}, it is used to build 4-graph as essential part of half-spindle diamond. 4-worm gives \sqrt{\frac{32}{35}} (if there is no error). …And what? Or maybe there exist more wide 4-worm?

      11. Maybe the shape of k-worm or k-flower is important too, not only minimum width or radius. For 2…4-worms we have thickness ranges [0, 1), [\frac{\sqrt3}{2}, 1), [\sqrt{\frac{32}{35}}, \sqrt{\frac{93}{35} + \sqrt{\frac{48}{35}}}) and step of the same color tiles 1, \frac{3}{2}, 1+2\sqrt{\frac{3}{35}}.

      12. It seems possible to get down to epsilon over 1 x \sqrt 3 by slowly rotating a diamond by 60 degrees about its centre (with appropriate translations to make it a chain of diamonds).

      13. I’m thinking of a quadrilateral with two curved edges of radius \sqrt 3/2 and two straight edges of length \sqrt 2, formed as the intersection of a disk of diameter \sqrt 3 with a strip of width 1. Basically, consider the circle as a regular (2n+1)-gon with n large, and where the diamonds join almost-opposite vertices. Deform this shape a tiny bit so that two vertices of the polygon lie on the edges of the strip, so are exactly 1 apart. All the diamonds we use then lie entirely within the quadrilateral. (Yeah, the rotation is just over 70 degrees, not 60 as I said.)

        I get an area of about 1.63 for this. This can be reduced by a slight variation on the construction, whereby the rotation really is 60 degrees but the centres of the diamonds crawl progressively across the strip, such that the first and last vertices are 1 apart but the other sharp vertices of the first and last diamonds are only \sqrt 3 - 1 apart, and one sharp vertex of every diamond lies on the line perpendicular to the strip between the first and last vertices. I get an area of about 1.55 for that – the shape covered seems to be a unit square plus a complicated shape with one curved edge and two concave corners. This is the only way I can find that gets below pi/2.

      14. On reflection I’m not sure I can make that smaller shape work – I can’t join the diamonds up. The best I can definitely do involves using the same first and last diamonds that I described but minimising the number of other diamonds by iteratively rotating the previous diamond as much as possible subject to staying within the strip. The perimeter becomes very zigzag and I haven’t even tried to calculate the total area. It may be slightly better to allow small bulges beyond the strip in return for using fewer diamonds in the middle of the chain – maybe reducing the chain to only 4 or 6 diamonds total.

      15. Pictures a more descriptive. I have used following area compressed 4-chromatic graphs:

        Starting and ending diamonds are shown black. Some intermediate diamonds are colored gray. Central edge of diamonds is not shown. Used rectangle region is bounded by dotted lines.

      16. Nice pictures! Could you include next to each its dimensions? It really looks like we won’t have one optimum, but several, depending on what we’re trying to minimize (area, width, perimeter etc).

      17. Thank you. Dimensions in normal order are following: \frac{\sqrt3}{2} \times \frac52, 1 \times 2, 1 \times (\sqrt8-1), \sqrt{2-\frac{\sqrt3}{2}} \times \sqrt3. I also think we have choice depending on the task. Two upper graphs are “compatible” with 4-worms (strips). Next two minimize area of rectangle (and its height or width). Aubrey described more area compressed graphs, but I’m not sure, that I imagine them right.

      18. Here’s a simplified version of the construction that I claim can get arbitrarily close to fitting into a 1x\sqrt 3 rectangle. Here I only use four diamonds; AE = 1 and A,B,C,D,E are all the same colour in any 3-colouring. In this construction the y-coordinates of P and Q are equal, likewise R and S, and AC = CE = BD. The enclosing rectangle is slightly wider than \sqrt 3 but also of course slightly taller than 1. I think the area of the enclosing rectangle continues to fall (asymptotically to \sqrt 3) as we increase the number of diamonds, but I’m not 100% sure of that.

      19. Ah yes, I meant to rite “narrower” where I wrote “wider”. I guess it could be fun to optimise the construction, but there are dauntingly many variables (and the number grows with the number of diamonds, of course) – not least because there is actually no need for the constraint that BD = AC.

  2. Jaan – I am having trouble reproducing your value of \sqrt{32/35} for the 4-tileable strip. As far as I can see, one can actually get \sqrt{15}/4 ~= 0.968. The periodicity can be 3/2, with the tiles coloured 1 and 2 having height 1/2 and being truncations (by horizontal lines) of unit-diameter circles whose centres are 1/8 away from shared boundary. What am I missing?

    1. With such tiles you will have less than unit distance between neighbor tiles colored 3 or 4. To see it you could draw unit circle with center in the middle of top edge of your tile colored 1.

      1. Yeah, apologies – I woke up in the middle of the night and realised that 🙂 I obtain your value now. I’m trying to beat it by using Siamese tiles (tiles that lie entirely within each other’s annulus of exclusion) but I don’t have anything yet.

    2. There is other thickest 4-worm candidate:
      Its “straight line” minimum width is only \frac{\sqrt3}{2} (and this property was the reason to reject it). But its “zig-zag” minimum width is exactly unit. And it seems it is the one we are looking for.
      Possible definition of zig-zag width: it is the minimum length of all cross-sections of the worm. And one can consider cross-sections with right angle to worm’s axis only and call their minimum length zig-zag thickness.
      Some other 4-worms are shown here (two of them have uncolored holes):
      By the way, “zig-zag width” of 5-worm is \frac{\sqrt{11}}{2}, exactly the height of Moser’s spindle. (Spindle itself could be rotated and moved inside the worm standing across it. The same holds for half-spindle diamond.) Worm’s tile periodicity is \frac{\sqrt7}{4} (without coloring). Zig-zag thickness is \frac74. So, we have for 5-worm a collection of magic numbers: \frac{\sqrt7}{4},  \frac{13}{8}, \frac{\sqrt{11}}{2}, \frac74. Some of them could be a hint.

  3. @Jaan Parts
    So Jaan, in the last thread you asked about the Birou/De Grey mix tesselation or whatever it should be called, and for a bigger area sample. I haven’t gone to SAGE yet (I need some more time to study up things) and instead inspected the geometry myself in SketchUp. I’ve found a lot of different periodic placings but indeed all of them have stayed just slightly below the necessary density for a 7-coloring.
    You had posted this tesselation back in the 6th thread:

    But we’ve never sufficently discussed actual colorings for it. Do you have any for this tesselation?

    If it turns out to not be 7-colorable it would disprove one of my earlier conjectures, and I think there’d be quite a bit to learn from it.

    1. I found that that tesselation is NOT 7-colorable. Above is a 12-tile pattern repeated 6 times. I used a SAT solver to find a 7-coloring, but it failed. Removing the 9 gray tiles does not help, but then also removing the black tile gives the 7-coloring shown.


      I wrote some code where I provide some minimal info:
      – I number the tiles in the 12-tile pattern arbitrarily
      – I define two transforms (a mirror and a rotate) by specifying where each of the tiles end up after transformation
      – The “exclusion set” of 17 & 18 tiles (marked by x’s in De Grey’s) for the two tiles as marked by x’s in De Grey’s image

      With this info the code can find a mapping between any two tiles of the same shape, and thus the exclusion set for all tiles (doing this by hand would be error-prone). I turned the exclusion sets into edges of a graph (tiles are the vertices). I converted the coloring problem into SAT, and used Glucose as the solver.

      1. Wow, very cool Tom – thanks! Looks like most (all?) of your grey tiles can actually be retained, just so long as we omit the black tile. That woould sure have been hard to determine by hand!

      2. It’s frankly bewildering that a tiling with only two essentially different tiles can be so close to k-colourable. I’m wondering how large you can go – how many tiles surrounding a single “uncoloured” tile can be assigned one of seven colours. It’s looking like it might be as many as 200 or 300. Insane.

      3. @Tom Sirgedas: Greatly appreciated, given my lack of experience with SAT solvers and mathematical programming of this kind it’s safe to say I would have taken quite a bit longer to get this result with confidence.

        This throughly breaks my conjecture of a final chromatic number for a tesselation (with maximum diameter tiles) emerging within an n-ball of radius 2, so the link to dimensional escalation clearly isn’t going to be anywhere near as neat and clear as I had hoped. I should drop that approach I guess.

      4. Re “I’m wondering how large you can go – how many tiles surrounding a single “uncoloured” tile can be assigned one of seven colours”:

        One more layer (of 2 12-tile “supertiles”) can go on top, but not two.

      5. Thanks! Have you tried maximising by (e.g.) removing one perimeter tile and seeing whether you can add more than one new tile somewhere?

      6. re “Have you tried maximising by (e.g.) removing one perimeter tile and seeing whether you can add more than one new tile somewhere?”:

        No, I guess I don’t understand the goal. You could make an infinitely long strip of tiles if it’s skinny enough.

      7. Ah, very true. I guess a meaningful question is, hw Uzbek can a single uncoloured tile be? (That’s a term I coined a while ago in honour of the fact that Uzbekistan is not only landlocked but is entirely surrounded by landlocked countries.) So – how many concentric rings of tiles can surround such a tile?

      8. The curved triangle can have 4 rings of tiles, but not much past that. The other tile can almost have 4 rings. (Tiles can be placed added at the two checkmarks, but then not at the x-mark).

      1. Yes, that would be very interesting too.Note that my exclusion zones in that post were incorrect though – see my followup post 4678.

      2. Right, I had forgotten that tiling for a while. I’ve attempted the rotation mentioned in 4678 but it didn’t really compute for me without making some tiles larger than 1. What I did find is that altering the triangles seemed to have some merit, but ultimately comes out even worse. Here’s what I was working on back then, briefly brushed up in case it helps, but keep in mind that Aubrey’s proposed adjustment isn’t included.

        The numbers are the exclusion set cardinalities. Given our previous experience I would now say that this is very unlikely to be 7-colorable as well. What these tesselations have in common is that the ratio of directly excluded to indirectly excluded area is very bad in all of them. This is a factor in predicting bad geometry of the homomorphic graph contraction, but then again there are definitely other strong factors too (regularity for one I think), as the hexagon tesselation doesn’t actually have the best ratio in that regard either, yet is still 7-colorable, and flexible as well.

        I think that the ratio of volume of continuous color areas to the volume of exclusion establishes a lower bound on the chromatic number of colorings. Specifically I still conjecture that a truly less than n-dimensional coloring requires an infinite amount of colors, and that as we scale up tile diameters (until maximum) we reduce this lower bound until we reach 7 for the plane, possibly 6.
        I’ve got some old work approaching fundamental contraints, dimensional escalation and diameter from the perspective of topological neighborhoods, I think I’ll pick up where I left off there.

      3. Even with the too small exclusion sets, I find that the above graph can’t be 7-colored (removing the black tile allows the 7-coloring shown).

      4. Very nice! It seems one can use here “rational coloring number” k, described here https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5569 with k slightly more than 7 and fractional part proportional to periodicity of 8th color (black) tiles.
        I like the term “indirectly excluded area” introduced by Bernhard to indicate some additional unwanted constraints of tessellation. The “exclusion set number” cannot give sufficient information for coloring task. Even the pentagonal tessellation with exclusion set 16 is less flexible than hexagonal one with exclusion set 18.

      5. While mulling over the ratios of indirectly/directly excluded areas I’ve come up with a pretty specific conjecture and some further ideas. There’s something very interesting I totally missed about the relations of measures, ratios and critical/complete subgraphs in contracted tesselations.

        I’m gonna write this down in full and post it here later, but it’ll probably be a serious wall of text and I need a while to get everything together, possibly the one or the other day.
        The abstract goes like this: Non-tile based colorings require an infinite amount of colors. The larger the diameter and more efficient the tesselation of continuous color areas, the smaller is the chromatic number of the coloring.
        But there’s also the size of the biggest complete subgraph we can find in the homomorphic contraction of the tesselation.

        So for a coloring without any continuous color areas the homomorphic contraction is an identity function, and the biggest complete subgraph in the plane has n+1=3 nodes.
        So thats 3-complete and \aleph_1 colors.
        On the other end of the spectrum, what is presumably the most efficient tesselation, we have 6-complete and 7 colors with Aubrey’s well known tesselation.

        So, what I expect to see in between in regards to the complete subgraphs however is a bell curve. If we go below maximum diameter then I would expect the largest complete subgraph to go up first before it eventually falls towards n+1, and at the same time the chromatic color would rise constantly, barring some expected hiccups.
        If this is actually true it should allow to develop a much deeper understanding of the fundamental constraints at play, not just for the euclidean plane but infinite graphs in general.

        @Jaan&Tom: You two have a much better understanding of using SAT-solvers. Do you deem it possible to feed a SAT-solver with a single tesselation at many different tile diameters and then look for the chromatic number as well as the biggest contained complete subgraph?

      6. Figuring out if some tiles are k-colorable:
        1. Convert to a graph coloring problem
        a. Each tile is a vertex in the graph
        b. Tiles that are within a unit distance are connected by an edge in the graph (exclusion set)
        c. Achieve “wrapping”: e.g. tiles on the top and bottom are connected as appropriate.
        2. Convert the graph coloring problem to a SAT problem
        3. Run SAT solver (returns solution or “unsatisfiable”, or takes too long)

        So changing the tile diameter means just means changing the exclusion set for each tile. I didn’t compute the exclusion sets myself, I used the ones provided with each graph.

        Proving a tiling IS k-colorable for the whole plane is tricky. The graph you provide is the repeating portion of the coloring. So, you need to guess what geometry the repeating portion will have. A large portion is more likely to have a solution, but larger graphs take longer to solve.

        Smaller diameter tiles will make the graph grow larger, and the chromatic number to increase (checking for 30-colorability translates to many more SAT clauses than 7-colorability).

        I don’t think trying smaller diameter tiles with SAT is too practical (problem size will be too big to solve). (Though, finding a 40-coloring for a large 30-colorable graph MAY be fast, but getting closer to 30 will certainly take too long).

        Intuitively, the tesselations we are trying are tuned for unit distance. When shrinking the tiles, do the shapes actually matter much? Why not just hexagons or squares?

      7. Sorry Bernhard, your post is a bit over my head. “Biggest complete subgraph” is that like a clique? An example with small tiles would be helpful for me!

        Also, I guess I now realize if the tiles become small, adjacent tiles can share colors. So, no graph would be “30-chromatic” like I mentioned, unless you change the rule to “tiles can share a color only if they’re at least unit distance apart”.

      8. [So changing the tile diameter just means changing the exclusion set for each tile. I didn’t compute the exclusion sets myself, I used the ones provided with each graph.]
        Indeed, this is one of the things I’m worrying about in regards to feasibility. The exclusion sets would have to be determined via computation, otherwise the amount of human work needed would be substantial, but I have no idea how to efficiently compute them.

        [A large portion is more likely to have a solution, but larger graphs take longer to solve.]
        What kind of Hardware restrictions and speeds do we have? Assuming the workload is threaded and I’d get some help setting it up I could run it on my 16-core system for weeks if need be.

        [Intuitively, the tesselations we are trying are tuned for unit distance. When shrinking the tiles, do the shapes actually matter much? Why not just hexagons or squares?]
        No, I don’t think shapes matter that much. The only effect of different shapes that I would expect are different curve shapes.

        [Also, I guess I now realize if the tiles become small, adjacent tiles can share colors. So, no graph would be “30-chromatic” like I mentioned, unless you change the rule to “tiles can share a color only if they’re at least unit distance apart”.]
        Yes, this is another issue I imagine to be tricky. Adjacent tiles wouldn’t be allowed to share colors (otherwise adjacent tiles sharing a color would effectively be just larger compound tiles), so are effectively connected via an edge, however this would be a special edge type and couldn’t be considered in the search for complete subgraphs. Easy enough to do via hand, but doesn’t sound easy to feed to a computer.

        [Sorry Bernhard, your post is a bit over my head. “Biggest complete subgraph” is that like a clique? An example with small tiles would be helpful for me!]
        Steps a and b in your previous post are what I consider contracting, and the search would be for the biggest complete subgraph in there.

        I’ve made an example with hexagons, diameter 0,65 and 0,54. In the picture you see on the left the excluded tiles. On the right all the colored tiles make up the complete subgraphs for which I’m now even more sure there’ll be a curve, as it’s 9 and 4 respectively. The gray tiles are those not in range by all of the tiles in the considered complete graph.
        The dark gray tiles are those that are not allowed to share the colors of their adjacent tiles, but which are ignored in regards to the complete subgraph, so a special kind of edge.

      9. @Jaan. That 9-colored hexagon grid looks exactly like the 0,65 diameter example I had posted. Is it feasible to automate this process for different diameters so a graph can be plotted with the date?

      10. Bernhard, sorry, I seem to have lost the track of your reasoning, and I need a time to get it. Some concepts are new for me.
        Did you mean hexagons only or any shapes in your last question?

      11. @Jaan: Any shape would be fine. If there’s a shape that would be particularly easy to work with we should go with that, but I don’t know what would be easiest. If there’s anything unclear let me know.
        I’ll be working through the SAT-solver link that Tom has posted, I’ll no doubt want to get up to speed on that front now as well.

      12. @Tom: Somehow I had always thought this would take longer and be more complicated, but you made it look easy. Thanks!

        I’ll be taking a look at the JS code myself so I understand how you did it. With this out of the way it should be possible to plot some interesting curves, possibly even generalize it for multiple tesselations. Now I’ve got even more to study to get up to speed but I’m excited to see how far we can go with this.

  4. Maybe I have found something from other side of the moon. I call it rational tile based coloring. (Yes, another wet term. I’ll try to explain, what I mean, and we could change it if there will be a reason.)
    A pair words of introduction. Why do we have a feeling sometimes that we are near the 6-coloring? (I assume tile based approach.) Because we can fill about 99.98% of the plain with 6 colors using 7-colorable Pritikin’s style design. Every cluster (repeatable set of tiles) of such design contains 6 large tiles and 3 small tiles (called diamonds) which use 7th color and occupy only 0.02% of area. Yes, using such coloring we reduce the relative area of 7th color, but we increase the number of tiles in a cluster. It is worthy to note that every diamond is used to resolve some conflict and therefore is unavoidable. In fact the coloring similar to Pritikin’s one increases the number of tiles of unwanted 7th color and this is something in an opposite way to the task of removing it.
    We can move in other direction and try to reduce the relative number of 7th color tiles. The idea is to remove 7th color bit by bit changing the recurrence interval of 7th color tiles. For example, the appearance period of 7th color tiles could be twice the period of all other colors and we could call such situation as 6\frac12-coloring conventionally. In general one can define rational coloring number k as a ratio of number of tiles in a cluster to the median number of tiles of the same color in a cluster. Such definition leads to some problems (I see the two at least) but we will ignore them here. I hope the backbone idea is clear: the rarer appear 7th color tiles, the nearer is such coloring to true 6-coloring.

    First question now:
    Is it possible at all? Can we find the tessellation and the coloring scheme where 7th color will be repeated more rarely than other ones?
    The answer: yes, it is possible. The example of such coloring is shown below (if I’ve done everything right).
    In a shown tessellation one can distinguish a cluster with 16 tiles. Two of them are always colored with 7th color, other colors are used 2 or 3 times (on the average 2\frac13 times) per cluster. Coloring period is 48 tiles, tiles 1…6 appear 7 times, while 7th color tiles only 6 times. Rational coloring number is thus k=\frac{48}{7}=6\frac67. Averaged exclusion number (number of neighbor tiles that cannot have the same color) is 17\frac34.

    The next question is:
    Can we do better? Can we increase the period of 7th color tiles more?

    1. Nice! I think we might be able to do a bit better using my pentagonal tiling:

      for which the exclusion sets are of size only 16. I can’t immediately see a neat way to get one colour down to a low density but I feel sure there must be one!

      1. I found a periodic tiling of 28 tiles as well, and it looks slightly different. I tried some other period tilings, but they all failed, so I’m not optimistic for a low density 7th color either.

      2. Interesting. My coloring also has vertical period of seven 4-tile rhombi. But every next neighbor rhombus has shifted color in every position as opposed to your coloring.

      3. @Tom: I was thinking more about this and I wonder if you could use your SAT method, but with wraparound to seek a periodic tiling. I’m thinking that you could define the tiling as an m*n rectangle of of 2*2 squares, each of which contains eight tiles, and with the option of shear on one of the dimensions (wrapping the first square on the bottom row to the ith one on the top row). Then the SAT question would be whether a 7-tiling exists with just one tile coloured 7, and then two tiles, etc. As you increase m and n you would identify an optimum periodicity. Does that seem feasible?

      4. https://imgur.com/a/Cv7L8zf

        My tiling is based on the pinwheel shape (see blackened tiles above). It was just the simplest for me to define in my framework. I do wrap-around by defining 2 “basis vectors” (shown with yellow arrows). All tiles connected by a basis vector are now equivalent. So instead of just an m*n rectangle, I can try a parallelogram shape. (Sorry about my poor math-speak!).

        I’m not too hopeful about any coloring where some color appears less than others. If this were possible, I think I would have found more wrap-around solutions with my attempts. The SAT solver was reasonably fast with ~80 tiles (20 pinwheels), but larger instances were too slow. Only the 28-tile pattern gave me a solution.

        I curious why you don’t use a SAT solver? Maybe we can help set it up for you.

      5. Both colorings are left-right “rhombus” tiles permutation equivalent.

        @Tom: I’d like to learn SAT solvers too, but I don’t know how to start. Do there exist any guides for it?

      6. Here’s a colouring in which the density ratios are 6:6:6:6:6:5:5, giving (according to Jaan’s definition) a rational chromatic number of 40/6.

        I think this may be the best possible for this tiling. This raises a question: in tilings where all tiles are “large”, i.e. no two tiles lie within each other’s annulus of exclusion, can we ever colour as many as 1/6 of the tiles the same colour, even completely ignoring how we colour the remaining tiles? I don’t think we yet have an example.

      7. Famously, Aubrey! But I think you have found one weakening of my definition. I knew about it. Another example is 7-colorable triangle tessellation with tiles ratios 4:4:4:3:3:3:3, which should give everything we want for rational coloring number from 6 to 8. Otherwise, my definition doesn’t work in a case when more than one color has different period. And I don’t know how to extend the definition on such case.
        Another problem of my definition is the extension on small tiles case. Example is 7-colorable Pritikin’s style tessellation.

      8. Also I see we use different small-large tiles terminology. To be sure, do you mean something like both 2-flower tiles below as example of small tiles?

      9. Perhaps a more useful thing that the rational chromatic number could be the difference between the mean and the minimum in a patch that periodically covers the plane. So that would be 6/7 in your original tiling, or 5/7 in mine, or 4/7 in the triangular case. The triangular case is of course an example of what I just asked for (a colour used by 1/6 of the tiles); can we find an example where the colour is used by strictly more than 1/6 ?

        When I refer to small tiles I refer only to things like the diamonds in the 7-colorable version of Pritikin, in other words tilings in which there are pairs (or more) of tiles such that the whole of one tile is less than 1 from any point within the other tile. (That’s also what I mean by lying inside each other’s annulus of exclusion.)

      10. @Tom – thanks for your offer regarding SAT solvers. My own problem is not so much one of access to software as one of time committed to my day job… The only software I currently use is Mathematica, which has very easy-to-use SAT-solving functions “SatisfiableQ” and “SatisfiabilityInstances” that serve the purpose pretty well – I have used that in developing the ideas that Boris is now exploring (with faster hardware) regarding grids – but since you had already developed not only the SAT code but also the nice graphical output I decided to appeal to your better nature 🙂

      11. Hm, interesting question. 7-coloring assumed? It seems you are right. One need to think.
        But how did you get 6/7, 5/7, 4/7?

      12. 6/7 is (7+7+7+7+7+7+6)/7 – 6, 5/7 is (6+6+6+6+6+5+5)/7 – 5, 4/7 is (4+4+4+3+3+3+3)/7 – 3 (except that it isn’t! – I should have said 3/7 there). No, this would work for any number of colours. I’m not sure that it is all that useful though.

      13. But it could be useful. It could give some constrains for 7- and 6-coloring. Anyway it gives other point of view.
        It is easy to get an example of tessellation with density more than 1/6 for some color, if more than 7 colors are used. Take usual 7-colorable hexagonal tessellation and insert a little (not small) tile with 8th color after every 3rd hexagonal tile in every horizontal strip. (I’m 1000 km from my computer, and I cannot provide picture, sorry.) This gives color ratios 3:3:3:3:3:3:3:7 (we could use compressed form of notation 3^7:7) and density 1/4 for 8th color. So 7-colors case is more interesting.

        I cannot understand the meaning of your coloring related number. It gives 0 for regular colorings (hexagonal, rectangular, pentagonal). It gives 1/2 for 3^7:7– coloring.
        I think a “rational coloring number” should have following properties:
        – it should be between k-1 and k if k colors are used;
        – it should be equal to k for regular coloring (same densities of all colors);
        – it should be reduced if some color density grows;
        – (optionally) it should take into account small tiles case (I expect something about 7 for Pritikin);
        – (intuitively) it should be increased if number of low-density colors rises (I expect about 7 for 4^3:3^4-coloring).

      14. About your construction: yeah, I think my challenge needs to be for tilings in which all tiles are “necessary”, i.e. they cannot be smoothly shrunk to zero with all other tiles keeping their colour.

        About rational chromatic number (RCN), well, I guess there is a natural relationship between what you suggest and the quantity I defined. I think we can just say that the RCN is the standard chromatic number minus my quantity, so in other words it is 43/7 for your tiling, 44/7 for mine and 46/7 for the triangular one. I’m not quite sure what you mean by “it should be reduced if some color density grows” – surely that should depend whether the colour whose density grows starts out being below the average density or not?

      15. Apologies, I thought about increasing period, not growing density.
        What will we get if period of 7th color will be 9, 10, 11 and so on with your RCN? For period 8 you give 43/7 already.

      16. Well, there may be a problem that “period” is defined by one dimension whereas “density” is defined by two. is “period of 7th colour = 9” the same as “density ratios are 9:9:9:9:9:9:7” ? If so, the RCN by my definition is 7 – (61/7 – 7), so 37/7, which is probably bad because it’s less than 6, but I don’t see a more natural definition.

      17. Actually, perhaps the definition can be normalised to be greater than the chromatic number minus 1. For example we can say that if the density ratios are n:n:n:n:n:n:m then the RCN is 6 + m/n, and if they are n:n:n:n:n:m:m then the CN is 13/2 + m/n, etc.

      18. No, no. Imagine hexagonal tessellation with standard 7-coloring. Take one strip of hexagons. Color sequence will be: 712345671234567…The coloring of neighbor strip will be the same, except some shifting.
        Then let 7th color be a special one and increase its period. Initial period was 7. Period 8 gives my tessellation. Color sequence of some tiles strip will be 71234561723456127… and so on (48 tiles per period). Neighbor strip will have the same but shifted color sequence. Look at my tessellation to check it.
        Period 9 will give color sequence 7123456127345612347561234567 (27 tiles per period) and color densities 4^6:3. Period 10 will give ratios 3^6:2. Period 13 will give ratios 2^6:1.

      19. Got it. Well, so still the question is, what definition would be useful? I think we are looking for a formula that gives a number close to 6 for tilings that are, in some sense, nearly 6-colourable. But… what sense? Not area, because Pritikin already gets us very very close. So, low density of some colour when differences of area are ignored? Maybe… but I don’t see any strong argument for any particular definition. My 13/2 thing was just a random suggestion.

      20. How did you get 13/2? By definition? Next will be 20/3? What about common case with ratios a:b:c:d:e:f:g? For example, 17:16:15:14:13:12:11.

      21. Yes, we take into account only color periods here, not area, meaning initial task of partial (gradual) exclusion of 7th color. The task itself could answer the question: does there exist some unavoidable obstacle on the way towards 6-coloring?
        It would be nice to have something like single rational coloring number, covering all possible cases, but it is not the main task. Instead one can use color ratios to decsribe every specific coloring. To add small tiles one can find all neighbor small tiles with the same color and consider them as one large tile (Pritikin’s diamonds are combined in threes).

      22. Returning to your question (to get minimum color period instead of maximum in my task).
        I have found two other tessellations with color density 1/6 (as I guess, you know already about them):
        1. Extended tessellation of Philip with color ratios 4^3:3^4, see https://dustingmixon.wordpress.com/2018/06/24/polymath16-eighth-thread-more-upper-bounds/#comment-4937
        2. Modified Pritikin’s tessellation with color ratios 5^6:6. To get it take 7-colorable Pritikin’s design, then exclude some diamonds in each line of diamonds cyclically using following sequence: 1-1-0-1-0, where 0 means excluded diamond, then combine neighbor 1-1-diamonds into single tile.
        Both tessellations could be used as a starting point for attempts to increase color density further.

        Now one could try other decimation sequence for modified Pritikin’s design: 1-1-0-1-0-1-1-0-1-0-1-0. It should give density 5/29 for 7th color. After decimation and diamonds merging there appear eveve-chain conflicts (red-edge-blue-vertex-red-edge-blue-vertex-red-edge-blue), which could be resolved by changing edge to the vertex in the middle of the chain. This leads to infinite v-chains (…-red-vertex-blue-vertex-red-vertex-…) and some distances constraints. But it seems, it it possible to get such tessellation. So, if I am right, the density of some color could be more than 1/6 even for 7-coloring.

      23. To clarify (as I hope) two last constructions I can show more strings of 7th color tiles sequencies with shifting.
        1. Dash-dot 5^6:6-coloring:
        — – — – — – — –
        – — – — – — – —
        — – — – — – — –

        2. Dash-dot-dash-dot-dot 4^6:5-coloring:
        — – – — – — – – — –
        – — – – — – — – – —
        — – — – – — – — – –

      24. I suggest following definition of RCN (rational coloring number):
        k_r=k-1+d/d_k, where k is number of colors, d_k is density of special k-th color, d is mean density of all other colors.
        It seems to be natural, compatible with previous definition, it covers any large tiles coloring and gives following values, for example:
        k_r=7 for any regular 7-coloring,
        k_r=6\frac67 for my 7^6:6-coloring, your pentagonal 6^5:5^2-coloring, triangle 4^3:3^4-coloring,
        k_r=6\frac34 for 4^6:3-coloring.

      25. It is equal to:
        k_r=(k-1)\frac{n}{n-n_k}, where n_k is number of k-th color tiles in cluster (pattern), n is number of all tiles in cluster.

      26. To support small tiles one can decimate them to large ones by following procedure. Take some small tile and delete all same color neighbors inside of its exclusion ring. Do it for all remaining tiles. In so doing one should minimise the number of tiles at the end of procedure. After that one can use RCN, defined earlier.

      27. I improved my code and got max-SAT to work. I found some other ways to make a color use only 1/8 of the tiles (6:7:7:7:7:7:7 pictured above), but didn’t find a way to use less than 1/8.

      28. It’s quite remarkable how many ways we have found that have one or more colour used for exactly 1/8 of the tiles but none for less than that. We have various 7,7,7,7,7,7,6, a 6,6,6,6,6,5,5, and a 4,4,4,3,3,3,3. Can we do better with one ofthe Pritikin variations? Jaan – your post with dots and dashes failed – it only has the dashes.

      29. But it has long and short dashes;) Tomorrow I will be back to my computer and clear pictures. I’ll jump to 11th thread.

  5. This follows on from the discussion of small areas covered by 4-chromatic UD graphs, but I’m starting a new chain because it is a bit of a departure. Now that we have quite a few shapes of area less than 2 that contain such graphs, and thus that cannot be 3-tiled, I’m wondering whether there is a way to use these shapes to constrain a search for 6-tilings. For example, can we cover a region of the plane with 1x\sqrt 3 rectangles and show that if none of those rectangles is 3-tileable then the complete region is nt 6-tileable? A stretch maybe, but worth some thought?

    1. This is something difficult to understand. You could take a number of such rectangles and cover some region of 6-worm (strip) for example. Nothing will happens (until you’ll cross the borders). So such approach won’t help (or I completely misunderstand the idea).

    2. As I understand, you want to exclude tile based 6-coloring. And you use here 4-graphs and 4-tile sets. Too long jump, isn’t it? Maybe it will be better to proof that such sets lead to exclude 4- and 5-colorings first?

    3. Not sure I understand this either.
      If I remember correctly Philip Gibbs and to some degree also you were also attempting at ruling out a 6-coloring with tiles in the previous threads, right?
      And this is a very different approach I assume?

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

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 )

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