Polymath16, fourteenth thread: Automated graph minimization?

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

The biggest development in the previous thread:

The method used for finding this graph is vaguely described here and here. It seems that the method is currently more of an art form than an algorithm. A next step might be to automate the art away, code up any computational speedups that are available, and then throw more computing power at the problem.

Advertisements

112 thoughts on “Polymath16, fourteenth thread: Automated graph minimization?

  1. Here I give a short summary of the proof of MCNP>=5, building on Falconer’s main idea, but using the 5-chromatic graph with a bichromatic origin (we have such a graph G with just 24 vertices). We mainly use the following lemma derived from Falconer, which is a simple modification of a lemma of Croft.

    Lemma: If G is a graph with bichromatic origin o, and E is a non-empty measure 0 set, then we can place G on the plane such that E contains exactly one of its vertices, o. [Moreover, for almost any rotation of G from o this holds.]
    The proof of the lemma roughly goes as follow. If some L0 is not a good choice for o, then on some circle centered around L0, E has positive outer measure (1-dim, circular). Any point L1 of this arc could also play the role of o, so we can also find an arc around each of these. Now any point L2 of such a new arc, can be derived in a bounded number of ways from L0, i.e., there is are a bounded number of possible L1s that could be the parent of L1. This implies that the set of L2, thus E, has positive outer measure (2-dim), contradiction.

    We also need the following well-known result.

    Lebesgue’s density theorem: The density of a measurable set is 0 or 1 in almost every point. This means that if one picks a “random” point p, then any small enough disk around that point will be either 99% filled with the set, or will contain at most 1% of it.
    Remark: Points where the density is not 1, is non-empty, if the measure of the set and its compliment is not 0. (This is also proved in Falconer.)

    From here, we can finish very easily.

    Claim: MCNP>=5.
    Proof: Suppose by contradiction that there’s a measurable 4-coloring. Let E be the collection of points where the density of red is not 0 or 1. Using the above results, place our G with the bichromatic origin o such that o is G’s only vertex that falls on E.

    Take a small enough disk around o where the density of blue points is, say, >1%. We know that o has <20 neighbors in G. Since each neighbor is mapped to a density point, we can take small enough disks around them that are 99.99% filled with the same color. Then if we shift G with a random vector selected from the smallest of these disks, we get that o will shift into a blue point, while the color of the neighbors will be unchanged with probability 1-0.2=0.8%. But this would give a 4-coloring of G where o is bichromatic, a contradiction.

    1. Whimper…

      -1) “Measurable” means “having positive measure, not zero measure”. Right?

      0) Let me recall that “G is a graph with bichromatic origin o” refers to a particular number N of colours, and it means “G has two N-colourings that assign different colours to o but not to any other vertex”. Right?

      3) I’m pretty sure I get the last part. You’re saying that we can translate the entire graph G into a location G1 where o is very likely to be blue or into a location G2 in which o is very likely to be red, but that all other vertices are in the same “almost certainly red” or “almost certainly blue” region in both such graphs.

      But I’m having trouble elsewhere:

      1) “If G is a graph with bichromatic origin o, and E is a non-empty measure 0 set, then we can place G on the plane such that E contains exactly one of its vertices, o.” There is nothing in your proof that refers to being bichromatic and I took a while to work it out, but I think you’re appealing to the fact that if L0 doesn’t work for o then that means every rotation of G around o, by any number between 0 and 2^pi, places at least one additional vertex in E. Since there are infinitely many such rotations and only finitely many vertices in G, either there is a continuous arc at some constant distance from o that is all in E, or else … hm, can’t there be a finite set of sets of numbers, one set for each of the the radii of your circles, whose union is the entire range from 0 to 2*pi, but each of which has zero measure? If not, why not? The term “outer measure” is new to me and I was totally bemused by the Wikipedia definition.

      2) “Lebesgue’s density theorem”… I have a problem here too. Intuitively, all this seems to say is that the boundary of a tile has zero area. But I badly suspect that it says meaningfully more than that and that that is why we still have the possibility that MCNP=5 even though we know that tile-based coverings of R^2 require at least 6 colours. What does it say about non-tile-based colourings?

      1. -1) NO! There are sets that are measurable (including the ones whose measure is 0, like the set of rational numbers) and sets that are not (like the Vitali set). But every set has an outer measure, which is the measure of a ‘smallest’ measurable set containing it.

        0) Yes.

        1) Here indeed we only use that G is a graph with a special vertex. Since there are only a finite set of numbers, if we divide a positive (outer) measurable set into finitely (or even countably) many parts, then one of the parts will have a positive outer measure (but it is possible that none of the parts will be measurable).

        2) For tiled based coloring, i.e., for Jordan sets, indeed this doesn’t say much, but now we cannot suppose that this is the case. About non-tile based colorings it says that for almost all red points, most points around them will be be also red.

        3) Yes.

      2. Many thanks Domotor. I am still really far from understanding all this, but I will work on it.

      3. [The term “outer measure” is new to me and I was totally bemused by the Wikipedia definition.] Although I think I understand the term, particularly after domotorps clarification, I have to agree that the wiki page cuts so damn straight into the finest details that the general picture isn’t clear at all.

        @domotorp:
        So the Lebesgue density theorem counts for fat cantor and other speckling in general too, right? I went through the formulas myself until they made sense, and I guess I can kinda see it… But it’s still one of these things that isn’t obvious at all on first glance. Assuming I got it right even.

        I’ve got another simple question related to your big sets looking small thread.
        I think I faintly remember having dealt with m-big at some point, but I can’t remember what it’s about, nor where to look it up, google isn’t being helpful in the least for once. A pointer to some explanation please?

  2. The proof I previously attempted to use for n-ball graphs equivalency was conflated and relied on the attempt to translate graph properties from K2 upwards. Only ball K2 itself had an explicit proof.

    Thanks to domotorp in the last thread I’ve become aware of some already proven math I’ve been missing. Here’s a shot at establishing the same kind of solid iterative proof shown for ball K2, but for any ball in any type of valid ball graph. No intermediary steps required this time.

    One ball being at unit distance to another is to be shown equivalent to two finite vertices sharing an edge, and a monochromatic vertex is supposed to yield a monochromatic ball. The question is whether that’s the case or if speckling is possible in such ball graphs.

    Every ball has the same n-dimensional measure m.
    Every ball has a boundary S with (n-1) dimensional measure w, such that its exclusion zone fully covers all connected balls.
    Given two balls A and B all points of ball B are in the exclusion zone S_{A}. The exclusion zone of S_{A} covers the entire measure m of B.
    Further there are arbitrarily many concentric rings arbitrarily close to the boundary (S_1, S_2...), whose exclusion of other balls is also arbitrarily close to full m.

    First let’s go with a concrete example. Assume disks (2-balls) A, B and C with some small radius at unit distance, in disk K3 (exact constructions were already discussed). We attempt to speckle disk K3 evenly such that A contains 1/3 m red, the same goes for S_{RA} which contains 1/3 w.
    This speckled red subgraph S_{RA}, even when fully disconnected, will still have an exclusion of at least 1/3 m for B and C respectively.
    It follows that we’re left with maximally 2/3 m of B and C to color red.
    So far so good, we only need 1/3 for B and C to keep the speckling up, but we also merely colored a part of the boundary with the desired speckling, which is an infinitely small measure compared the whole ball.

    We continue with S_{RA1} having an exclusion arbitrarily close to 1/3 m itself in B and C. This exclusion is evenly spread across the 2/3 we had left for color red, leaving us with just 4/9 m in B and C (multiplicative 2/3).
    Take S_{RA2} and we’re down to 8/27 m left for speckling red in disks B and C which is already less than the needed 1/3 m for even speckling.
    K3 can’t be evenly speckled.

    Further there are arbitrarily many such steps that can and have to be taken in the attempt of a full speckled coloring, whereas we only need a finite amount of steps to reach a contradiction to any attempted amount of speckling. We can tell the limits of these steps too, as the measure m in other balls at unit distance we can assign the same color gets arbitrarily close to 0 for any positive speckling in S, S_1, S_2... let alone the entire ball.
    Monochromatic vertices equate into monochromatic balls, where no speckling is possible. I hope that’s better.

    Now, there’s an obvious question I have to ask here myself. What about non measurable speckle sets? I’m fairly certain their existence isn’t a problem as the above scenario will work for any positive measure speckling, even arbitrarily small so long as it’s positive at all, and we’ve got some well-defined measure we need to entirely cover with color from the start. There’s pretty likely no such thing as some finite non-measurable sets without positive measure that add up in a union into a full measurable set.
    Although if there were such a thing that’d be fascinating too.

    1. This has proven to be a very interesting direction to take, and in trying to make the results even clearer and expand upon them I’ve asked myself more questions.
      Most notably above I claimed a 1/3 w evenly speckled boundary to “have an exclusion of at least 1/3 m”. The “at least” in there came from me expecting it to be actually larger than that, which I can now demonstrate and explain too since indeed it is.

      First of all in n-ball graphs, as already shown, there are subsets of balls that have full exclusion of certain other balls all by themselves. The two specific examples I named are the boundary, and a line pointing towards the ball that is to be fully excluded.
      Let’s generalize this and see why. Take disks A and B at unit distance. For all points in A the unit distance circle around those points passes between the closest and the furthest point of B (except of course for the equivalent closest and furthest points in A, whose respective circles only connect directly to the same 2 points in B).
      That in turn means that every 1-dimensional line connecting the closest and the furthest points in B has full exclusion m in A and vice versa. That’s also how we can construct as many specific and completely separate sets of full exclusion as we want. This generalizes well into higher dimensions too and clearly doesn’t work in just 1 dimension.
      Now why does a boundary itself, speckled 1/3 w evenly with one color, already exclude more than 1/3 m in all other balls? The boundary has 2 such separate lines connecting all furthest and closest points for all balls at unit distance, going around the ball in either direction.

      Now it’s tempting to think that maybe there is such a speckling that the respective 1/3 m exclusions of these two lines don’t union in such a way to reduce the measure available for speckling in the other ball below 2/3 m.
      First assume we have one part of the boundary speckled already, the other not yet, then we can figure out what exactly it would mean for a point in the other part of the boundary to not cause additional exclusion. All of the points in the arc of exclusion of this point would already have to be excluded by our previously speckled boundary arc. Which is actually possible in one specific way… with a solid interval. Precisely the one thing we want to avoid if we want to speckle. This of course holds for all the points in the second part of the boundary, meaning we can demonstrably prevent precisely none of them from adding to our exclusion without instantly giving up speckling altogether.
      So then we’re down to 4/9 m with 3 colors using speckling on just the boundary. All of which is demonstrable with the according geometry.
      It doesn’t change afterwards either. On the third iteration a given point can be added without adding to the exclusion if either of the first two has a solid interval which we still don’t want.
      We can also try shifting densities, but neither do we can or want to do this in an even speckling, nor would it actually help as we’d just have more excess exclusion elsewhere, as any places with lower density of one color just need a higher density of another color.

      So no matter what I tried with this in mind so far, I can’t find a speckling that can’t be shown contradictory to itself in a finite number of steps this way, using concrete geometry and measures. Trying even speckling for 3 colors it’s 3 steps until contradiction. For 7 colors it’s 13 steps. I suppose this would be a good topic for animation too, but there’s more things to test, and I also want to wait and see if more questions or issues appear.

  3. I’ve just had a go at comparing Jaan’s latest 510er and Marijn’s 517er. For anyone else who wants to do this, please note that the number of vertices that they have in common rises a lot if you rotate one of the graphs by 60 degrees. After doing that I am seeing 26 vertices in Jaan’s graph that are not in Marijn’s (and therefore 33 that are in Marijn’s and not in Jaan’s). All the differences are in the large part. But, Marijn noted that he had found a dozen 517ers, and maybe Jaan also has multiple examples, so maybe there are members of the two sets that are more similar than that. It might be useful to identify the most similar ones so as to see what are the essential changes that allowed the number to be reduced.

    1. Oh dear – I think I may have deleted Jaan’s and Marijn’s vertex files from the dropbox! I can’t figure out how to get them back. Apologies to both of you – please repost them.

    2. Done. No problems.
      Of course, I also got many graphs with 510 vertices, or more precisely, large subgraphs with 375 vertices. Now I won’t say how much, I didn’t count, just posted the one with the smallest number of edges. In Marijn’s large subgraph there are no two key orbits, which made it possible to further reduce a graph. Interestingly, they exist in the 2167-vertex graph.
      Additionally, I can say that I also got many graphs with 376 vertices, including graphs with 6th order symmetry. There are also 379-vertex graphs with 12th order symmetry. I haven’t tormented the small subgraph yet, I took it from Marijn’s graph, adjusting it to my one, hence the rotation by 60 degrees, nothing mysterious.
      It seems that the basic algorithm is looming a little. For training, I restarted with a large graph and used other type of connections between the large and small graph. To make it more interesting.

      1. Cool that you are now down to 510. I checked out your graph and noticed that my method was not able to go down to 510, because the size of the UNSAT proof is larger for the required key orbits. I turned off the heuristic that prefers runs with short UNSAT proofs. That allowed me to find roughly 1400 large subgraphs with 375 vertices. The smallest ones have 2504 edges (when combined with the small subgraph to obtain a 510-vertex UD graph). I put one of them in my repository. (The link is in my prior message. I don’t repeat it here to avoid the moderation.) The 379-vertex large subgraphs with 12th order symmetry sound much more interesting then decreasing the number of edges. Could you share one?

      2. Our graphs coincide in a set of orbits. I did not spend much time to get a large number of 375-vertex graphs (to minimize the number of edges). I got them as an almost free add-on when searching for graphs with 3-fold symmetry with the number of vertices less than 376 and asymmetric graphs with the number of vertices less than 375.
        The question arises, how confident are we that we have squeezed out everything that is possible from this type of graph? How much time (CPU hours) did you need to get your first graph with 375 vertices? How much time did you spend then searching for a graph with fewer vertices?
        I spent something about three days on searching for a graph with the number of vertices less than 375 until I was tired of it, and considered almost all the possible options in the framework of my method, though somewhat unsystematically. Therefore, if there is a graph with fewer vertices, then I either overlooked it inattentively, or I need to introduce some kind of modification like the one you did with your method.
        An example of a graph with 379 vertices and 12-fold symmetry:
        https://www.dropbox.com/s/k5e6brt3r77otkt/v379.vtx?dl=0

      3. Thanks for the graph. I don’t see why this has a 12-fold symmetry: the graph maps onto itself when rotating it by 120 degrees and has a reflection symmetry. That should be a 6-fold symmetry, right? I thought you referred to a graph with a rotation of 60 degrees with reflection symmetry.

        For me the challenge to find graphs with a large part of 375 vertices had nothing to do with computational resources, but I needed to adjust the parameters of my scripts (I tweaked them during two evenings). Most importantly I had to remove the part that preferred short proofs of unsatisfiability. Once I had the right settings, I was able to find quite some of such graphs in a few hours running on 120 CPUs. Last night I focused the search on large graph with only points in G_2167 and found about 800 of them with 375 vertices. I also expect that there is little to further squeeze out of this type of graph.

      4. Nevertheless, this graph has 12th-order symmetry. There is an additional not so obvious symmetry. You can find it, for example, using the function GraphAutomorphismGroup[] in Mathematica.

        Could you publish a graph that is the union of all your graphs with 375 vertices (while the small subgraph is fixed)?

      5. The union has the same orbits as the large subgraph of 510. It has 403 vertices and I added it to the repository (L403). My runs mostly focused on the 400 vertices of that graph that occur in G2167. Is your union larger? In that case I would be interested to experiment with it.

      6. Yes, I broke off on a graph with 433 vertices (it includes your 403-vertex graph), but I tried to reduce the graph while maintaining 3-fold symmetry, so not all orbits of the combined graph can lead to a 375-vertex graph. Here it is:
        https://www.dropbox.com/s/n1t8i1nd86ul864/v433d.vtx?dl=0

        What is your conclusion about the possibility of further reduction based on (in addition to the fact that there are a large number of options for obtaining 375 vertices)? Or maybe you already got graphs with fewer vertices?

      7. I ran some experiments last night using the graph with 433 vertices. I found a few additional large subgraphs with 375 vertices, but they only used points occurring in the subgraph of 403 vertices. Apparently my method cannot find some of your large subgraphs with 375 vertices. It would be good if you can describe in detail how you obtained those graphs so a mechanized approach could be explored.

        I am currently out of ideas to find a graph with fewer than 510 vertices. There may be some graphs that are similar to the current one that use a few points less. One potential method that I only briefly explored is to have a large subgraph that includes all 12 points at distance (3*Sqrt[11]-Sqrt[3])/6 and (3*Sqrt[11]+Sqrt[3])/6: {0, (3*Sqrt[11]-Sqrt[3])/6} {0, (3*Sqrt[11]+Sqrt[3])/6} and the copies when rotating by 60, 120, 180, 240, and 300 degrees. The current large subgraphs have only 6 of them. If all 12 are included then a small subgraph can be reduced by 3 or even 4 vertices.

      8. I am not surprised by the results with a 433-vertex graph. As I already noted, I tried to maintain 3-fold symmetry, that is, included in the combined graph all the obtained graphs with 376 vertices.

        A few days ago I had the same thought about the orbit you are talking about. One can call it the connection orbit (with a small subgraph). I have not gotten to testing this idea yet, and I will probably wait for your results. Instead, I tried another option for trimming the connection orbit to 6 vertices, namely, I left all its vertices with a minimum radius. I was able to reduce resulting large subgraph to 388 vertices maintaining 3-fold (and even 6-fold) symmetry (I did not check the asymmetric version). Btw, an interesting effect is observed: a large subgraph still tends to take a “triangular” shape, despite the fact that the connection vertices are located in a hexagon.

      9. Could you test this option too? I have a suspicion that I could provoke this triangular trend artificially.

      10. I tested the 6 vertices with a minimum radius quite some while ago and noticed that the current 6 vertices allow for smaller large subgraphs. That is why I continued working with those vertices.

      11. I mentioned that in the CP article: the graph minimization algorithm frequently produced in graphs that were almost symmetric by using a rotation of 120 degrees. That does not seem to be a coincidence.

    3. Yes, there may be confusion in terminology. I started with a high order graph with a different type of connection between a large and a small subgraph (in Marijn’s terminology).

  4. I wrote my MSc thesis under the supervison of Dömötör as it was already mentioned in https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/ . Partly because of a comment of Dr. de Grey https://dustingmixon.wordpress.com/2019/07/08/polymath16-thirteenth-thread-bumping-the-deadline/#comment-23760 , I decided to upload my thesis here, as it might be interesting for the probabilistic formulation part of the project (and possibly for other subjects too, although a lot of the topics covered in the thesis aren’t directly connected to the Hadwiger-Nelson problem, but are more about UDGs in general). This is in chapter 4, and it contains a few things that haven’t been uploaded anywhere else. If someone is interested in it, I can expand it further (I already made a few changes in it recently). Chapter 5 is about related problems (3-dimensional and spherical cases), but it is a lot shorter and less comprehensive.
    https://drive.google.com/file/d/1Khp85TYPJ8ehbD9P9Q5qC6U9enChZYDI/view?usp=sharing

    1. Many thanks Peter, and congrats! One thing to note is that your graphs 15 and 16 (figures 1. and 1.10) are, to my knowledge anyway, the only ones known with e^3 exceeding v^4. It is known that the edge density can only exceed this by epsilon, so it is very interesting to ask whether any larger graphs break the strict bound.

      1. I don’t know of any other UDGs for which e^3 exceeds v^4, but in the diploma work of Carsten Schade, which I used in my thesis, there is an example for a UDG with 27 vertices and 81 edges, where e^3=v^4. It seems not to be a rigid graph, but still, I didn’t manage to add a single edge, neither a new vertex with degree at least 5 (the latter doesn’t seem that surprising, but given how symmetric the graph is, first it seemed plausible that the center could have degree 6 for some unit distance representation of the graph), the best I managed is to add 3 vertices with degree 4, but that isn’t good enough. Still, it gave better bounds for v=29 and v=30 as the ones given by Schade, but they still lack one edge each to achieve e^3>v^4. All these can be found in the folder https://drive.google.com/drive/folders/1UvgH4ASqMVyOuWc9Y8brI3-zNJB3pyZr
        In the GeoGebra file Schade27.ggb, B is the movable vertex, and the center of the drawing is fixed, although I made the assumption that the three cube graphs on the sides of Schade27.png are axially symmetric (I am still not sure, if it is necessarily true).

        If you are interested in the diploma work of Schade (written in German), I can send it to you privately (it was sent to me privately too by his supervisor, so I guess I am not allowed to make it public).

        Note: I don’t (yet) have a mathematically precise proof for the above, but they are very clear from the GeoGebra files.

      1. Yes (I guess). For a d for which p_d\neq 0, we can choose two points with distance d so that they have the same colour. Then all the points of the union of the unit circles around them have different colours from this colour, but if this union requires at least 4 colours, then along with the centers, we need 5 colours. For me it seems likely that such a union is always 3-colourable and I am working on a proof for this for a while now. I am not yet done with all the cases, but if I will be, I will post it here.

  5. Woah, neat! Damn, I feel we could have found that – it’s a reasonably natural refinement of Jaan’s strip.

    Also I’m confused by Bock’s statement (from his ref 3) that “epsilon-colourings” have a lower bound of 6. Aren’t these precisely what we have been calling “scaleable” colourings, which were shown by Thomassen to need seven colours? What amI misunderstanding?

  6. Just for fun I’ve derived an exact formula for the width of Bock’s four-colourable strip. Thanks to the miracle of Mathematica I find that it is the square root of the largest real root of a fabulously unpleasant octic polynomial:

    822083584 x^8 – 2831155200 x^7 + 5243797504 x^6 – 6719913984 x^5 + 6544488704 x^4 – 4778761472 x^3 + 2086053600 x^2 – 355368400 x + 893025 = 0

    (which I don’t think factorises at all, though Mathematica is being ambiguous to me about that – if anyone can check it with Maple please shout), and to higher precision the value is 0.9587376106963147.

    One feature that may not be instantly obvious from Bock’s depiction is that the parallel lines forming boundaries are not exactly equidistant: the blue/green boundary is slightly further away from the other two than they are from each other. However, everything else is critical (i.e. whenever a distance looks as though it might be exactly 1, it indeed is).

    1. For verification purposes I should probably provide the other coordinates. Place the bottom edge of Bock’s strip on the x-axis, and place a blue-green point of the upper edge on the y-axis. Then:

      – the period of the tiling, i.e. the x-coordinate of the next blue-green point on the upper edge, is about 1.5685848884250153744, being a root of 3408 + 5440 x – 2384 x^2 – 3308 x^3 – 967 x^4 + 412 x^5 + 1584 x^6 – 816 x^7 + 112 x^8

      – the x-coordinate of the first blue-green point on the x-axis is about 0.15672921989110954549, being a root of 72345 – 433880 x – 350360 x^2 + 1095744 x^3 + 167248 x^4 – 592512 x^5 – 51200 x^6 + 124928 x^7 + 28672 x^8

      – the x-coordinate of the first internal green-red-yellow point is exactly 1/2 more than that of the first blue-green point on the x-axis

      – the y-coordinate of the internal green-red-yellow points is about 0.33834631324673685967, being the square root of a root of 1 – 8 x – 40 x^2 – 272 x^3 + 5648 x^4 + 2816 x^5 – 70144 x^6 – 98304 x^7 + 200704 x^8

      Everything else is as it seems from symmetry. In particular, the x-coordinate of the green-yellow point on the upper edge is the sum of those of the blue-green and green-red points on the lower edge, and the internal yellow-red-blue points are a blue-green point on the upper edge minus the first internal green-red-yellow point.

  7. I just took another look at this and I have realised that Bock actually incorporated an unnecessary (and unstated) assumption into his tiling, namely that the blue/green border is straight. Actually, in his construction that border is not precisely perpendicular to the line between a lower three-colour point and the next-but-one upper three-colour point, with the result that if we make it straight then the distance between those two points ends up being slightly more than the required minimum value of 2 that Bock notes in the last of his inequalities. We can thus obtain a fractionally wider strip by making the blue/green border zigzag accordingly (i.e. making a central section exactly perpendicular to that other line) and making corresponding small adjustments to the shape of the blue and green regions’ opposite boundary. The increase in the strip’s width is so tiny that it actually doesn’t show up at all at the precision Bock gives – it rises from 0.9587376 to 0.9587628 – but hey, a record is a record!

    This also means we can express the width in (slightly…) nicer exact terms than before. We can write the constraints as the following system of six equations in six variables:

    d – 2f = 1
    (y-z)^2 + (w-f)^2 = 1
    y^2 + f^2 = 1
    (d+e+f-w)^2 + z^2 = 1
    (y-z)^2 + (d+f-w)^2 = 1
    (2d-e-1)^2 + (y-2z)^2 = 4

    where:
    – in Bock’s Figure 1, we set the x-coordinate of the leftmost point on the upper edge to zero
    – d is the period of the tiling
    – e and f are the x-coordinates of the leftmost two points on the lower edge of the strip
    – y is the width of the strip
    – w is the x-coordinate of the leftmost upper three-colour point
    – z is the distance of the lower three-colour points from the lower edge of the strip

    and this readily simplifies to:

    4y^2 + (d-1)^2 = 4(y-z)^2 + d^2 = 4z^2 + (d+2e+2)^2 = (2d-e-1)^2 + (y-2z)^2 = 4

    which means that the width, i.e. y, is now “merely” the square root of a zero of a sextic polynomial, which Mathematica gives as:

    187142400 x^6 – 922107024 x^5 + 1869792121 x^4 – 1990975958 x^3 + 1168879585 x^2 – 356290800 x + 43560000

    and the value is 0.95876282534485063321.

    As before, the formula for the period, i.e. d, is rather less horrid: it is about 1.5684147947995704317, being a zero of 3420 x^6 – 9078 x^5 + 5893 x^4 + 1020 x^3 – 2198 x^2 + 714 x – 59, and y is simply Sqrt[1 – (d-1)^2/4].

    1. Correction: the four-variable system should have been:

      4y^2 + (d-1)^2 = 4(y-z)^2 + d^2 = 4z^2 + (d+2e)^2 = (2d-e-1)^2 + (y-2z)^2 = 4

      The rest is still correct. FWIW this means that z = Sqrt[1-(d+2e)^2/4] and e = 1-3d+Sqrt[5 – 42d + 49d^2]/2, so that the equation for d is:

      (5d-2)*Sqrt[2d^2-2d-3 + 2*Sqrt[(d-3)(d-2)(d+1)(d+2)]] + Sqrt[(d-3)(d-2)(d+1)(d+2)]) = 11d^2-10d+2

      1. That’s my “d” above, 1.5684147947995704317. It’s the horizontal distance between consecutive blue-green boundaries. (Of course the red and yellow regions swap sides each time, so if we take colours into account the period is actually 2d.)

      2. Ah: I withdraw my claim that Bock miscalculated. Early in his paper he twice gives a width of 0.959, but towards the end he adds a digit of precision, giving 0.9588. If he had actually enforced that the blue/green boundary is straight, he’d have got 0.9587. Thus, his mistake was actually just in not noticing (or at least not noting) that that boundary needs to zigzag.

      3. Addendum: I wrote to Bock notifying him of the above and he has just replied. He confirms that he did not enforce straightness but that he then forgot to incorporate the zigzag into the statement of the construction.

      4. The zigzag indents in the strip piqued my interest, as they seem to be deeper than an unit radius arc, meaning there is definitely some overexclusion there. But it doesn’t look to me like that could be turned into any improvement, and I’m definitely not deep enough in the matter of colored strips to reasonably try and make anything out of that, if possible at all. Interesting result though.

    2. I tried to check your solution and got confused in the notation. Could you express your variables in terms of the coordinates of the points shown in Figure 2? (If necessary, add some more points.)

      1. If we use Figure 2, then all my x-coordinates (in other words, the values of d,e,f and w) are increased by f, which is just Sqrt[1-y^2] where y is the strip width.

    3. Does not work. I tried to solve your system of equations, and got a different answer. I don’t see where the error is. I have doubts about the last equation, but I tried different options, all without success. Please check if I understand your six equations correctly (order is the same):
      1. |U_4-U_3|=|L_4-L_3|=1
      2. |M_4-L_3|=|M_3-U_4|=1
      3. |L_3-U_2|=|U_3-L_2|=1
      4. |M_4-U_6|=|M_3-L_1|=1
      5. |M_4-L_6|=|M_3-U_1|=1
      6. |M_7-M_3|=2

      1. I used Maple. Mathematica is busy with other calculations. I am observing an interesting effect. If I use evalf (solve ()), that is, the exact solution, then the answer is different. If I use fsolve (), then the answer matches yours, with d-w = 1/2. If I use fsolve (), but the sixth equation I have is (w-e/2)^2+(y/2-z)^2=1 (it seems to me that such a notation is more correct), then the answer is different again. I do not like it. Something here is wrong.
        Maybe, instead of a system of equations, one should solve the optimization problem with a set of inequalities.

      2. I neither have nor know how to use Maple, but just to be sure I have now worked through all the algebra and it checks out: I obtained the stated polynomial for d by hand, without any reliance on Solve magic.

  8. One can go from the other side and see what strip width is enough to place the 5-chromatic graph. In other words, get the upper bound for the 4-colorable strip w_4. (Note that for 2- and 3-colorable strips the exact width is known, w_2=0, w_3=\sqrt3/2.)
    So far I have got the estimate w_4\le 1.55 (this is less than the lower bound for w_5\ge 9/\sqrt{28}\gt1.7).
    With decreasing width of the strip, computation time increases rapidly. Even with a moderate number of vertices of the order of 10000, the calculation time in both glucose and yalsat exceeds 10 hours for some graphs. Here supercomputers would be very useful. There are also doubts about Marijn’s conclusion that the time of SAT calculations is usually comparable to the time of preparation of the CNF file. Apparently, here the graph structure has a great influence. So, for example, we can expect that if the graph does not contain sufficiently large clusters of triangles and / or Moser graphs, the computation time will be large (even for 4-coloring).

      1. Yeah we came across this some time ago. As I recall, one needs to write “& g t ;” (without the spaces, obviously) to avoid being parsed as (broken) HTML.

    1. Yes, it’s easy. Same approach is used for any number of colors. We take a long chain of graphs connected by vertices that have the same color. The ends of the chain are connected by an edge. The chain is placed inside a strip of a given width.
      Thus, the problem is reduced to the search for a graph with a monochromatic pair for a given number of colors. Now a suitable base graph is taken, a strip of the required width is cut from it, and then a check is made to see if the monochromaticity property for a given pair of vertices is preserved.
      A specific result was obtained by cutting a strip y \in [-0.775,+0.775] from the graph \oplus^4 H^{\left\{-3...+3\right\}} with pair of vertices (0,0) and (8/3,0). The notation described here: https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23602.
      I have not yet tried to cut the strip at some angle or take other mono-pairs, for example, from the set k\cdot8/3^{n/2}, latex k,n\in \mathbb{Z}$. Perhaps this will improve the result.

      1. Yeah, that makes sense. I was more expecting that you would remove vertices one at a time that are on the edge of the strip, and if the mono property is lost you would then seek new vertices within the strip whose addition restores the property. But I have no idea how efficient that would be.

      2. So far the problem is that each check takes a very long time. Therefore, it is better to immediately have more vertices that could restore mono property.

    2. Refined estimate: w_4\le 1.5. Calculations in glucose took 30 hours for a graph with 6456 vertices. (It took 4 hours to evaluate 1.55, and 5 minutes to 1.6.)

    3. Last result: w_4\le 1.4. And this is already really interesting, since it requires 5-chromatic graph without Mosers. (If I’m not mistaken, the minimum width of the Moser spindle is w_M= \frac{\sqrt{3}}{2}+\frac{\sqrt{11}}{6}\approx 1.4188.)
      Some additional details. In the calculations, the following are set: the base graph G, the coordinates of a pair of mono-vertices a and b, the coordinates of a rectangular window x and y, the angle \alpha of window rotation around origin, the minimum degree of vertices d. I also tried some transformations that improve the symmetry of the graph, but they have not yielded a positive effect. Window rotating also did not improve the result. An improvement (obtaining a 5-chromatic graph and speeding up the calculations) is caused by an increase in the length and shift of the window, as well as an increase in the order of the base graph. Calculations in glucose are usually faster than in yalsat, even when the graph is 4-colorable (e.g. in case y \in [-0.4,+1.0], 11104 vertices, 4 hours).
      A specific graph with 34590 vertices and 234724 edges was obtained with the following parameters: \oplus^4 H^{\left\{-4...+4\right\}}, a=(0,0), b=(8/3,0), x \in [-1,+11/3], y \in [-0.1,+1.3], \alpha=0, d\ge 7. The calculations took 20 hours.
      The file with the list of vertices “v34590.vtx” placed in the dropbox of the project for verification: https://www.dropbox.com/s/qiq0ikc74hqh803/v34590.vtx?dl=0
      Figure will follow.

      1. Outstanding! I agree with your minimum Moser width. Can you pull out an example of the smallest 4-chromatic subgraph of your graph?

      2. Not now. I need to think about how to do it. Do you have any ready-made offers? The second question, for what purpose? Do I guess correctly that in this way you want to make out some kind of structure, some kind of graph frame made up of diamonds?

      3. No “offers” (guesses), no. No single purpose either – there could be several. One is that it might reveal a way to derive even narrower strips without calculating the CN, as some sort of transformation of this one. A more ambitious purpose could be to find new building-blocks for the search for a 6-chromatic graph.

      4. The shortest diamonds path between points (0, 0) and (8/3, 0) for 34590-vertex graph is 2 diamonds, i.e. 7 vertices. Obviously, this is the smallest 4-chromatic subgraph (more precisely, its 8/3-length section). Point of diamonds connection is (\frac{4}{3},\frac{\sqrt{11}}{3}) .

    4. A graph with 34590 vertices is shown below for fun. The origin (0, 0) coincides with the center of the cave, the appearance of which is explained by the way of vertices numbering.

    5. I launched in parallel (in different threads) a check of several graphs that differ in the density of the base graph, the size and position of the window (with a width of 1.3, 1.35 and 1.4). From the moment of launch, from 2 to 4 days have passed, the calculations have not yet been completed anywhere. In this sense, it can be considered good luck that a solution was obtained for the 34590-vertex graph. I’ll wait another day, then interrupt the calculation. The situation is complicated by the fact that in glucose there is no way to monitor the relative progress of the calculations (yes, the log file periodically displays what is indicated as “%”, but this value does not change from the beginning until the end of calculations). Maybe one can tweak something in the options, but I can’t decide what. No ideas?

    6. The calculations for some graphs with strip width w_4\le 1.4 are completed:
      12839 vertices, G = 4H3, -0.2\le y\le 1.2, 111 hours, 4 colors
      12842 vertices, G = 4H3, -0.15\le y\le 1.25, 82 hours, 4 colors
      35435 vertices, G = 4H4, -0.2\le y\le 1.2, 78 hours, 5 colors
      34590 vertices, G = 4H4, -0.1\le y\le 1.3, 20 hours, 5 colors
      Here we use the simplified notation for the base graph nHm=\oplus^n H^{\left\{-m...+m\right\}} (no need to use TeX now).
      Thus, the following results are confirmed:
      1) it is possible to construct a 5-chromatic graph without Mosers
      2) graph density matters
      In other words, it makes sense to increase the density of the base graph to obtain new extremal properties. Note that to obtain a 5-chromatic graph, it is sufficient to use 3H2 and even 3H1 (graph of Tamas V_A\oplus V_A\oplus V_A). And this can be a useful observation on the way towards the 6-chromatic graph. (This seems to be obvious, but one more confirmation is encouraging.)

  9. Not sure everyone has seen it, so let me post it here that if we forbid 1 and 2, then CNP>=6: https://arxiv.org/abs/1909.13177

    Also, it seems that the topic of writing up the obtained results and (partly) closing the project has disappeared from the agenda. As the blogging took a very slow pace, with the same handful of people commenting, I think it is time to move on. Aubrey proposed Dustin to start the write-up, but I’m not sure about how enthusiastic he is. In case nobody wants to start, let me volunteer my grad student, Peter, to make an overleaf file where we can start to collect the results.

    1. New result: neat! I had not known about the earlier CNP>=6 result (their ref 9).

      Writeup: I am in favour. Dustin, what do you think?

      1. Indeed, with Peter we also have some further d for which we can prove that without (1,d) you need 6 colors, using the probabilistic formulation. This will also go to the write-up, I guess.

    2. Could somebody help me with construction of Huddleston? What are sets S and Q? What is “the sum of its entries”? Why points distanced by 5 should have the same color?

  10. One can use similar approach (large graph trimming) to fit k-chromatic graph into the disk and minimize its Euclidean diameter d_k. Initial calculations give d_5\le 2.

    An interesting question: is it possible to find 4-chromatic graph with diameter d_4\lt \sqrt3? It seems that disk coloring is harder than strip coloring. So for 4-coloring of the strip we have the same bounds \frac{\sqrt3}{2} \le w_4 \le \frac{\sqrt3}{2}, but for disk known bounds are different, \frac{2}{\sqrt3} \le d_4 \le \sqrt3. Or I’m wrong?

      1. I am sure that it is possible to make the construction of Exoo (the original graph with 12 vertices) even more compact in the sense of the Euclidean diameter.

        Using the dense graph trimming approach, I got the following upper bound on the diameter of the 4-chromatic disk: d_4 \le 1.29 for the 4H4 grid (the notation is explained a bit higher). This is not so far from the lower bound d_4 \ge \frac{2}{\sqrt3} \approx 1.1547 .
        Below is an image of the corresponding graph with 4368 vertices (I’m sure, it can be greatly reduced, but I didn’t try).

        Btw, one need to correct 5-colorable strip width (\frac{9}{\sqrt{28}} instead of \frac{13}{8}) on wiki page.

      2. Great job again Jaan! I don’t see a way to squeeze the 12-vertex graph, but maybe there is a way. But I bet you can beat 1.29…

      3. Thank you, Aubrey. But I think it would be more elegant to develop the approach of Exoo. If this succeeds, then it will immediately give convergence to the lower bound in the limit. In my opinion, you need to take the same pairs of triangles and just reduce the angle between them (the number of pairs will increase, but this is not important). Or do you immediately see some fatal limitations of this approach?

      4. I had the same thought when I saw the Exoo graph, actually. I constructed a counterpart of the 12-vertex graph that has 20 vertices, five of them in an inner pentagon and the rest in an outer ring (not quite all on a circle), which is otherwise similar (the inner vertices and five of the outer ones have degree 4, the other ten have degree 3) and which indeed has a smaller diameter (and yes, as we continue along this idea the diamater keeps falling, though I’m not totally sure it is asymptotic to 2/Sqrt[3]). But unfortunately it turns out to be 3-colorable! I have not studied it enough to understand why. The edge set is:

        {{1,7},{1,10},{2,6},{2,8},{3,7},{3,9},{4,8},{4,10},{5,9},{5,6},
        {6,11},{6,16},{7,12},{7,17},{8,13},{8,18},{9,14},{9,19},{10,15},{10,20},
        {1,17},{1,15},{2,18},{2,11},{3,19},{3,12},{4,20},{4,13},{5,16},{5,14},
        {15,18},{14,17},{13,16},{12,20},{11,19}}

        If you have a different vision of how to develop the Exoo graph, please explain.

      5. You used a pentagon as a base. I think that we should always stay in the Moser lattice (can I call it so?), just make it denser by adding rotations on \arcsin \frac{1}{\sqrt{12}}. Thus it is very likely that the “free ends” of the triangles will be connected by edges with other triangles, as required.

      6. The graph of Exoo is isomorphic to the following graph, from which it is clear why three colors are not enough: some pair of opposite edges of the outer C6 cycle turns out to be bichromatic. Increasing the number of triangles removes this restriction, so three colors are enough.

      7. Jaan, what an elegant proof. I wonder whether we can proceed using similar ideas. A cycle of triangles can be wound together in lots of ways that have small Euclidean diameter and create unit distance between the third vertex of triangles k apart in the cycle, where k is not necessarily half the length of the cycle, so maybe there is a way to do it that prohibits a 3-colouring in a manner similar to what you noticed. I can’t see anything yet though.

      8. Thank you, after such a high assessment I want to roll mountains (or at least triangles).
        I was playing with cycles of triangles of various lengths m, connecting the free ends of triangles with various steps d (m=6, d=3 for graph of Exoo). Interesting (finite) sequences were obtained. For example, for d = 3, graphs are 4-chromatic for m \in \left\{4, 5, 6, 8, 10, 11, 13, 15, 17, 20, 22, 29\right\}. However, there are doubts that it will be possible to get at least one such unit distance graph and fit it inside a disk of small diameter. Until I figured out how to develop the procedure for such fitting.

      9. Cool. My failed pentagonal attempt was m=10, d=5 of course. With any even m, we can emulate Exoo and have the vertices that are shared by two triangles lie on two concentric circles, whose relative radii determine the radius of the circle of “free” vertices. Thus, if there are any even m for which we can have larger d (probably not equal to m/2), I think we have a chance. I don’t see any other way to generalise the Exoo graph.

        Ah, yes I do – can we go Golomb? The “free” vertices lie in a circle of diameter greater than 1 (or else we can’t do this sort of thing at all), so lots of triples of them can be joined to the vertices of a triangle that sits well within the desired disc. Thus we can prohibit a lof of triples from being monochromatic. In fact, there’s no reason to restrict this construction to the free vertices. This seems mighty promising – I bet (with no evidence :-)) there is a parmetrisable construction that works and gives an asymptotic diameter that is really good.

      10. I’ve been playing with this and I think it has promise. For any even m that does not divide by 6, we can create an analogue of the Exoo graph that has the usual two rings of m/2 vertices of degree 4 (I’m going to call these the chain rings) and one ring of m vertices of degree 3 (I’ll call this the free ring). If we temporarily delete the edges between vertices on the free ring, we can vary the radii of the chain rings continuously – one defines the other, but they can be arbitrarily close together. We can also make the chain rings have diameter asymptotically close to 2/Sqrt[3] as m rises, by making the cycle of triangles encircle the origin Round[m/6] times. Moreover, as m rises, if we set the chain ring diameters to be equal then the difference between that diameter and the diameter of the free ring also declines asymptotically to zero. So far so good. Then I have tried to do two things:

        1) Find the pair of diameters of the chain rings whose difference is minimal subject to some pairs of free-ring vertices being at distance 1. There will be either m or m/2 such pairs. In practice I think (but have not quite proven) that the case where there are m of them is always degenerate, i.e. the free-ring vertices coincide in pairs (and also coincide with the vertices on one of chain rings). This also SOMETIMES happens in the m/2-pairs case, but I have not yet worked out exactly when.

        2) Find the minimum value f such that if we Golomb every trio of vertices no pair of which is at distance 1 but all pairs of which are at distance between 1-f and 1+f, we get a 4-chromatic graph. In other words, in any 3-colouring of the original graph, at least one such triple is monochromatic.

        The hope is that as m rises, f falls asymptotically to zero, so that the vertices of the Golomb triangles also converge on a circle of diameter 2/Sqrt[3] and we achieve a tight value for the size of a 3-colourable disk. So far the best I have is m=22 and f~=0.46, but I haven’t fully automated the search yet.

    1. d_4 \le 1.25 with 5H4 lattice (22185 vertices), but the test took 15 hours (vs. just one minute for d_4 \le 1.29). By the way, one test (d_5 \le 1.9, 4H4 lattice, 10032 vertices) is running already a week, and there is no end in sight.

    2. OK, it looks like this works. It does NOT work with Golombing described as in my previous post – basically if we set f much below 0.5, there is a simple colouring that works for any m (and in fact the minimal f actually RISES with rising m, asymptotically to 1/Sqrt[3]). However, a Golomb triangle can also be guaranteed to lie close to the annulus of interest if two of the vertices to be prohibited from being monochromatic are close together and the third one is about 1 away, just so long as the isolated one is extreeeemely close to 1 away from one of the close pair – basically, within f^2 – otherwise, two of the three Golomb vertices end up a long way from the annulus. Using this strengthened version I am getting a nicely decreasing minimal value for f as m rises. Here:

      (assuming I am remembering how to upload figures… apologies in advance to Dustin otherwise) is the graph (without the Golomb triangles) for m=70, which is the first value for which I get f down below 0.3. (Empirically I find that the degeneracy mentioned in the previous post always occurs when m=2 mod 6, so I’m only checking m=4 mod 6.) The chain circles have radii about 0.565885 and 0.569708 and the free circle has radius about 0.596972. I haven’t yet figured out an efficient way to compute the positions of the Golomb vertices for three arbitrary points (anyone know a nice algorithm for that?), so I don’t yet know the overall diameter of the entire graph, but there are 30170 trios of vertices that get a Golomb triangle, so assuming there are no coincident vertices the overall graph has 90650 vertices and 181265 edges. I think the overall diameter must challenge Jaan’s 1.25 value, depending just how far outside the three main circles the Golomb vertices ultimately stray.

      By way of evidence for the f=0 asymptote, pushing further I get f below 0.25 for m=106, with the free circle down to a 0.590377 radius. (I’ll probably try to get to 0.2 overnight, but my laptop is already threatening to max out.) Of course this is not a cast-iron proof that the bound of 2/Sqrt[3] is tight – for that we would need a provable upper bound on f that is asymptotic to 0 as m rises – but I’ll leave that to someone else 🙂 (Actually though, there may be a clue in the colourings that I’m finding for just-too-small f, which are always three monochromatic regions each subtending just under 120 degrees and one region that seems to subtend a progressively smaller angle, though including a progressively larger number of vertices.)

      1. Update: it actually seems that the aforementioned degeneracy is less of a bug than a feature. Surprisingly, there is a somewhat more rapid reduction in f with rising m if our core graph has just one chain ring (which, it turns out, is what the degeneracy amounts to), meaning no edges between free vertices (since the radius of the chain ring is no longer flexible). Remarkably, the Golombs do enough, and they do it even more effectively than when we have inter-free edges. I think this may be because having all the chain vertices on the same circle means there are more pairs of them at distance very nearly equal to 1 (hence permitting the second type of Golomb attachment that I described in the previous post). Anyway, current status is I’m down to f=0.19 with m=70. m no longer needs to be even, of course; seems that m=1 mod 3 works better than 2 mod 3 but no preference for even vs odd.

        Also, I’ve realised that we can compute a probably very good upper bound on the radius of these graphs without actually computing the positions of all the Golomb vertices, just by identifying the worst-case distance from the origin in terms of f and the radii of the main circles. I haven’t got around to that yet though!

      2. OK, with the new system of only one chain circle I got down to f=0.15 overnight with m=154, i.e. 308 vertices and 462 edges. This uses 59290 Golomb triangles. The curve of f with m is pretty smooth – I decremented f by 0.01 starting from 0.3 and m went 16,31,34,40,43,49,52,58,67,73,82,91,103,118,133,154, so there is some oscillation but I would bet good money that it is asymptotic to 0.

      3. Wow, great! But I did not quite understand your construction. Could you explain again which vertices in the chain of triangles do you connect with Golomb triangles? Can you show for clarity a graph with a short chain of triangles and several Golomb triangles?

      4. The Golomb-joined trios are in two classes. Class 1 is the easy one: it is just points that are close (i.e. +/- f) to being a unit triangle themselves, so that the Golomb vertices are each quite close to one joined vertex. Class 2 consists of two vertices A and B close together and one vertex C about 1 away, so that one Golomb vertex, D, is close to A and B and is joined to C. The difficulty with this case is that the location of the other two Golomb vertices is very sensitive to the exact locations of A and B: basically, small changes to A and B cause a large rotation of the Golomb triangle (D doesn’t move much but the other two vertices do). This is avoided if we require (say) A to be very close to 1 away from C (much closer than +/-f; I used +/- f^2), because that forces the Golomb vertex that’s connected to A to be close to C. I’m not sure exactly HOW close, but I am sure that it falls to zero as f does.

        Sorry for no diagram – I still didn’t have tome to write code to construct Golombs.

      5. Thank you, I think I get it. The exact position of the Golomb triangles is not tracked, but only assumed? Or do you control that they all fit onto a disk of some small diameter and discard all those that do not fit? More interestingly, is the resulting graph vertex critical or does it allow the removal of some Golomb triangles? (If the latter, then it is possible to trace, at least by the example of a small graph with large f, which triangles actually work.)

      6. Not tracked, only assumed – and I have not checked for criticality.

        But thank you for asking questions, because when writing my previous answer I had some doubts, and I now realise that my f^2 constraint doesn’t work if A and B are too close. I now think the criterion needs to be that Abs[AC-1] is less than f*AB. I will rerun my code with that change and report back!

      7. And whew: f is still falling with rising m, though of course more slowly than before. I will let it run for a while, but I’m already pretty sure that f will not bottom out at a positive asymptote.

      8. Wow Tom, that is just spectacularly cool, especially the video. (And welcome back!) I had actually never looked at this question enough even to realise that there can be more than two triangles… I last wrote C nearly 30 years ago, though, so I think this will be more use to others than to me – and anyway I think for the current purpose we are already in good shape from just having a way to bound the distance of the Golomb vertices from the origin by restricting which trios to attach to.

        Since I have your attention, though: do you fancy having another go at using SAT on a grid, to find tilings? I refer you to the discussion with Boris in which I came up with a way to do it that in principle can find “unscaleable” tilings where distances and diameters are both exactly 1. Boris never got it to go, though, and it’s one of the more conspicuous loose ends here.

      9. Ah right, yes – we came to the same conclusion, but that was because we were looking at square tiles, which inherently can’t get us to unscaleable tilings. My trick to get around this was to just use grid points. The thing to satisfy is: for every neighbouring pair A,B of points, for every third point C that is more than 1 away from A but less than 1 away from B (or vice versa), do not allow all three points to be the same colour. You also need to include the constraint that every point has at least one neighbour the same colour.

  11. It seems that I have finally solved all the cases in the problem of Dömötör from https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24165

    I made a GeoGebra applet which shows the solutions (the distance of the centers can be changed with the slider in the bottom and in the bottom right it also shows the interval for which the construction is good):

    https://www.geogebra.org/m/vqetks4u

    We also had the idea that if we have points A and B on one circle (centered O), and a point C on the other one so that C has distance 1 from O’ (defined as the reflection of O to the midpoint of A and B) and we are sure that A, B and C have three different colours in any colouring, that guarantees that O’ has a fourth colour and if we can prove this for two points with distance 1, that also gives us a proof for the plane being not colourable with 4 colours (of course, it still only works if p_d>0 for the distance d of the center of the two circles).

    As for the Overleaf file, we are already working on it, and it will most likely be released shortly, when we will have at least a draft of what should be written in it.

  12. Here’s a 5-coloring of the plane with the exclusion set shown. I specified some of the central points to be 0’s to help speed up the search. It looks like a noisy hexagonal tiling with 4 colors, with the color “1” sprinkled in.

    1. Woah, looks like you have got it to work! – brilliant trick to put those zeros in. Let me be sure I understand your exclusion set: does a line between two neighbouring grid points simply denote that the unit circle around the central point passes between those two points?

      And of course – what happens when you try it on a larger grid? In both senses – larger dimensions with the same granularity, and same dimensions with finer granularity. Or have you maxed out your computational resources?

  13. “The thing to satisfy is: for every neighbouring pair A,B of points, for every third point C that is more than 1 away from A but less than 1 away from B (or vice versa), do not allow all three points to be the same colour.”

    In the exclusion diagram, the central point is C, and each line segment shows an A,B pair.

    “Let me be sure I understand your exclusion set: does a line between two neighbouring grid points simply denote that the unit circle around the central point passes between those two points?”

    Yeah, that’s an equivalent way to understand the exclusion set.

    In the image above, there’s a 4-coloring for a less granular grid.
    There’s also a 5-coloring for a more granular grid (4-coloring failed). The asterisks denote a 11×11 square of hard-coded values (to speed up the solver). This grid size is near the limits of what I can compute.

    It’s also possible to search for tile-able colorings by connecting the top/bottom and/or left/right of the grid.

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