Polymath16, fourteenth thread: Automated graph minimization?

Posted on by Dustin G. Mixon

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.

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

    Reply

    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?

      Reply

      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?

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

    Reply

    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.

      Reply

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

    Reply

    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.

      Reply

    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.

      Reply

      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. But there is reason to think that this is a real trend. We can recall Golomb as an analogy.

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

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

      Reply

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

    Reply

    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.

      Reply

      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.

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

    Reply

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

    Reply

    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.

      Reply

  10. 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].

    Reply

    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

      Reply

      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.

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

      Reply

      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.

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

      Reply

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

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

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

    Reply

      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.

    3. I’m really impressed that you have found a way to search for these. Can you give a brief summary of your algorithm?

      Reply

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

      Reply

      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.

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

      Reply

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

      Reply

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

      6. I’m a bit late to the party here (both in the thread and in the project, but I’ve been lurking a bit), but this piqued my interest… A 5-chromatic graph without any moser spindels. I spent some time today searching Jaan’s thin graphs for small 4-chromatic subgraphs.

        I can’t show it’s the smallest 4-chromatic subgraph, but this one is elegant at least, and has only 10 nodes and 19 edges. It’s height is sqrt(33)/3.

        Here’s a simple ‘proof’ of it’s un-3-colourability.
        Without loss of generality, arbitrarily assign colours A, B, C to the triangle formed by 0,1,2. Let the colour of p0 be A.

        Next, observe that p8,p9 must contain colours B,C in one of two ways.

        1. p2 = p9 (symmetric colouring)
        This breaks in a forced sequence (choosing the only available colour) after colouring p8 then p5, p7 and p6, p3 showing that p3 = p7

        2. p2 = p8 (asymetric colouring)
        This breaks similarly after colouring p9 then p4 and p5, p6, and p3, p7 showing again that p3 = p7

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

      Reply

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

      Reply

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

      Reply

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

    Reply

    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?

      Reply

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

      Reply

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

    Reply

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

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

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

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

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

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

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

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

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

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

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

      Reply

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

      Reply

      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.

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

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

    4. Aubrey, you used two classes of Golomb triangles in your construction: 1) with distances between all three vertices about one and 2) with one of the distances near zero. Will this construction work if you leave only the triangles of the second class?
      You can think of the Golomb triangle (with connection edges) as a (expanded) Reuleaux triangle with bichromatic arcs (with the colors of arcs 12, 13 and 23). The position of the center of the triangle changes slightly. Moreover, in a triangle of the second class, the probability of the same color in the region of convergence of the arcs increases. Does this make it possible to use a probabilistic approach?

      Reply

      1. I guess it might work, but if so then the decline of f with increasing m would probably be very slow. I’m afraid I don’t understand your Reuleaux idea!

      2. So, most likely, it does not work. Just in case, I will try differently. Let’s start with the Golomb triangles. Their key property in 3-coloring is to prohibit monochromatic triples of vertices. You said that you observe a pattern when coloring your graphs: three almost same-color sectors. But then it is not clear how the first class triangles can help here (their ends already fall into different colors)? Maybe they work in some more subtle way? So I thought it would be nice to check if they work at all.
        Next, you had a question how to determine the position of the Golomb triangle. I thought it might be more convenient if you start not from the three given vertices, but consider all possible vertices that can be covered by the Golomb triangle with its three free edges. The latter form unit circles around each of the vertices of the Golomb triangle, and the arcs of these circles form a Reuleaux triangle, that is, a geometric object with a fixed shape. Since we are looking for an asymptotic solution, the set of possible motions of Reuleaux triangle is very limited: these are rotations and small movements relative to the center. It seems that with a probabilistic approach I made a mistake, again focusing more on your pattern.
        In general, I still do not understand why your design works exactly. And mine. Btw, this one too: https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24357

      3. Concerning your first point: ah, no, a misunderstanding. If we do not add any Golombs at all (of either class), i.e. we only have the chain of triangles, then no, even if we do the neat Exoo thing of placing alternate chain-vertices on two different circles and thus allowing edges between free vertices, we do not seem to get any particular pattern in the 3-colouring. In other words, the pattern of three nearly-120-degree regions occurs AFTER adding the class 1 Golombs, so for sure they add value.

        I should add some more detail. Firstly I only added class 1 (because I had not even realised that class 2 existed), and the solution that was found was two intervals covering nearly 120 degrees and two other, equal-length, intervals covering a bit more than 60 degrees. (Obviously the small intervals are the same colour and the large ones are the other two colours.) This works fine for any m, so we need something more. At that point I realised that class 2 exists and I added them. The only interesting finding arising (other than the main one, that the minimal f declines as m rises) was that the colouring that we get when f is too small is not quite the same as when we only have class 1: specifically, the two short intervals diverge i length, with one of them growing to nearly 120 degrees and the other one becoming small.

        I am still confused about your Reuleaux idea. Since all three vertices of the Golomb triangle move when any one connected vertex moves, I don’t think we can infer anything from examining the sets of places that the connected vertices can be for a given positioning of the triangle.

        I too do not have an explanation for why this works! All I can really say is [waves hands really hard] that the original Exoo-based construction is probably pretty restrictive for 3-colourings already, such that pretty much anything we do to constrain it further is likely to end up randomly eliminating some of the few admissible colourings. The only reason these Golomb triangles are useful is then the boring reason that we happen to be able to add a lot of them without increasing the disk diameter much.

        I wasn’t able to download the Huddleston paper so I can’t immediately say anything, but please email it to me and I will see if I can help.

      4. Thank you Jaan for sending me the Huddleston note. I don’t understand it yet, but I wanted to comment first on the proof given immedately beforehand, authored by one Marian Tetiva from Romania (Dan, do you know the name?), that d(1,Sqrt[2]) is at least 5, i.e. the plane cannot be coloured with four colours in such a way that no points of the same colour are either exactly 1 apart or exactly Sqrt[2] apart. It is an even nicer proof than the one given by Dan and Geoff in their excellent paper showing several new such distances. To summarise it, since the text is (as you say) hard to get: Tetiva exploits the fact that d(1,x) = d(y,xy) for all y. The presumably VERY versatile trick that Tetiva uses is to identify a graph with edge lengths 1 and y and just one vertex pair at distance xy, where d(1,x) is already known to be greater than k. In such a graph, all that is needed in order to show that d(1,y) is also greater than k is to show that the graph cannot be k-coloured if the vertices at distance xy are forced to be the SAME colour. The logic is that in any hypothetical colouring of the plane where no pair of points at distance y is mono, there must be some pair at xy that is mono, so we just pick one, and then we build the rest of our graph around that. Tetiva gave such a graph with y = Sqrt[2] on only six vertices, namely a unit square plus its diagonals and with unit triangles on two opposite edges. The tips of those triangles are 1+Sqrt[3] apart, which is Sqrt[2] times the easy distance (Sqrt[6]+Sqrt[2])/2 which we already know (e.g. Geoff/Dan’s section 2) is available as x. So neat! – basically the converse of spindling, and in some sense a special case of the probabilistic method. And surely very widely applicable.

      5. Ah, apologies to Dan and Geoff – I see they cited the Tetiva work in their latest paper. Nonetheless, I think it is worth bringing Tetiva’s trick to our attention – it feels to me like a very powerful new trick in our toolbox.

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

    Reply

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

    Reply

    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?

      Reply

  16. “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.

    Reply

    1. Thanks. So things seem to be behaving as they should, i.e. the finer the granularity the more faithfully the setup reflects reality. The true reality is that we definitely need six colours, so it will be great if we can push the system far enough to falsify five colours. I’m wondering whether there are additional ways to speed things up – I think there should be ways to specify the boundary between two tiles in ways that don’t prohibit anything…

      OK I just tried something along those lines. I first made a whole square zero (seems like you fixed an octagon but I was too lazy for that) and then I fixed just two additional pixels, neighbouring two adjacent corners of the zeroes square, and made them both 1. That sped up the discovery of a solution by a factor of 20. I don’t have as much compute power as you; maybe you could try this sort of thing? I think the granularity you’re using, of around 1/12, may be enough to prohibit 5 colours – I’m getting an immediate solution for a grid of overall height and width 1.9 but no termination when I go to 2.0, and that’s about in line with reality. (Ah, it just found a solution after 10 minutes!)

      Boris and I did try connecting opposite edges, some time back, but it didn’t make things any better.

      Reply

  17. OK guys, I think I have a route to a proof (i.e. I have not remotely worked out the details – and I’m afraid I will not have time to do so today) of a tight bound of 2/Sqrt[3]. Putting it in a new post because it draws multiple earlier ideas together.

    To recall: the big insight thus far has been that the Exoo graph is (the simplest example of) a trick to introduce a degree of freedom into the positioning of a cycle of triangles encircling the origin so that all vertices are somewhere near 1/Sqrt[3] away from the origin. Specifically, if all the “chain vertices” (the ones of degree 4 joining two triangles) are placed at the exact same distance from the origin, then they must sit at the vertices of a regular polygon, so the distance of the “free vertices” (the ones of degree 2) from the origin is fixed, whereas in the Exoo graph and its generalisations to longer chains, the chain vertices are placed alternately at two different distances from the origin. These distances are not independent, of course (each defines the other), but they can vary continuously (that’s what I mean by a degree of freedom), and the effect is to allow those radii to be chosen so as to make certain distances between free vertices equal to 1, i.e. to allow some extra edges.

    Now, we have found that adding masses of Golomb triangles to this base structure seems to give what we need – but we only have empirical evidence for convergence to a tight bound, and I’m pessimistic that we could develop a proof.

    However, what we certainly CAN do is introduce additional degrees of freedom. For example, if we index the chain vertices from 1 to m with m divisible by 4, we could have all the odd-numbered vertices on a circle of radius X, but then place the others on either of two circles of radii Y and Z depending on their index mod 4. This would give rise to two circles of free vertices, and thus to 15 options for distances that are exactly 1 (between vertices on the same circle or on different ones), and we could choose X,Y,Z to satisfy two (any two?) of those.

    So now, suppose m is large and we continue this process and end up with quite a lot of circles and quite a lot of degrees of freedom. Then pick a bunch of triangles located far apart on the overall cycle, but chosen so that they are nearly coincident in the embedding. Label the triangles’ vertices Ai,Bi,Ci where i denotes the triangle. Within a given triangle, choose which vertex to label A etc so that the letters are clustered, i.e. the Ai are close together etc; it’s not going to matter whether (for example) the same letter is assigned to all the free vertices.

    Now, my tentative claim is that, assuming we have introduced enough degrees of freedom, we can choose radii in such a way as to be able to add more edges between these vertices, creating a graph whose valid 3-colourings all have most (all?) vertices in each cluster monochromatic. I don’t yet have such a graph – the barrier is that we can’t have, for example, any quartet of vertices A1,A2,B1,B2 with all four Ai-Bj edges existing, because that can’t be unit-distance. But I feel sure that this can’t be hard. Can anyone here identify such a graph?

    And once we have such a graph, all we need to do is iteratively repeat the whole construction, using all but one of the triangles we just used and a new one. (If our initial graph only has most vertices in a cluster mono, not all, we will need to do this with each original vertex replaced by a new one.) In this way we can step our way around the circle until the latest Ai is close to the original B1, etc. Either arrange things so that Ai actually IS B1, or if that’s not possible then just throw in one class-1 Golomb.

    Does that sound good? All help in completing the proof welcome!

    Reply

    1. Many questions.
      Is it possible to understand the markup into three clusters, for example, like this: all vertices with angles from 0 to 120 degrees receive labels Ai, from 120 to 240 – Bi, from 240 to 360 – Ci?
      What does ” iteratively repeat the whole construction” mean?

      I think it would be worthwhile to place here the image of the Exoo graph, since it is often mentioned:

      Reply

      1. Yes, you have the labelling right. In my vision of the construction, for large m, the first set of triangles have the Ai grouped together very tightly (say between 0 and 5 degrees). By “iteratively repeat” I mean we then drop the triangle whose A-vertex is closest to 0 degrees and add one whose A-vertex is at an angle slightly more than 5 degrees, and if our new graph arising from the set of triangles and addable edges is isomorphic to the original graph then we still have the “mostly mono clusters” property. Thus we can iterate, i.e. keep dropping the one at the smallest angle and adding a new one, so that we creep clockwise until the A’s reach the original B’s.

      2. My misunderstanding is even deeper than I thought.
        How is labeling and coloring related?
        If all Ai are limited by a small range of angles, does this mean that triangles with a repeat of labels (say, two Bi) are allowed? Or you allow many vertices be unlabeled?
        After all, are we only considering triangles of the main chain?
        Does dropping a triangle mean breaking this chain? If not, how does adding another triangle restore this chain?

      3. I’m sorry, my explanation is probably not very good.

        No, each triangle has just one “i”, i.e. its vertices are labelled Ai, Bi, Ci.

        Yes, we are only considering the main chain, except that we have chosen the radii of the circles where the vertices sit in such a way that extra edges are possible, just like the three edges in the Exoo graph that join vertices of degree 3. There are no extra vertices (such as Golomb triangles) here (except that we can allow just one class-1 Golomb triangle at the end of the iteration if we really need it,but I would expect that we don’t).

        Oh yes, many vertices are unlabelled: the only vertices that are labelled at first are the ones in those narrow intervals. And then when we drop the most anticlockwise triangle and add a new triangle that is slightly more clockwise than the others, we label its vertices the same as before, i.e. the vertex that is next to the A cluster gets A, etc.

        We don’t change the chain at all, at any point. The purpose of the labelling is to derive the desired property (non-3-colorability) of the entire chain from a weaker property of the subgraph consisting of the set of triangles that we label plus the extra edges between those triangles that are created by our choice of radii. This weaker property is that in any 3-colouring, the colours cannot be distributed evenly within the clusters: we have to have each cluster mostly one colour. If that property is true in the first subgraph, it’s true for every subgraph, since we are stipulating that they are all isomorphic. Also, in any hypothetical 3-colouring of the overall graph, the second subgraph (which is the first subgraph with one triangle dropped and a new one added) must use the same majority colour for the A-cluster as the first one did, since they share almost all the same vertices. Thus, by transitivity, we end up eventually clashing the colour of the A’s with the colour of the B’s once we creep by 120 degrees, thus disproving (by contradiction) the original assertion that the overall graph is 3-colourable.

      4. Yeah, thanks for the clarification, Aubrey. Now at least the general direction of your thought is clear to me. It remains to delve into the details. (So wait a dozen more questions.)

  18. OK, I get the Huddleston thing. It is just one of those annoying cases of doing geometry but insisting on describing it in terms of number theory. All he is saying is this:

    – draw a regular pentagon with its centre at the origin
    – draw five more pentagons, same orientation, centred on the vertices of the first one, and throw away the original pentagon
    – do that again, three more times (so this is just the Minkowski sum thing we’ve been doing since forever with V_30 etc)

    and then he does a clever thing: he considers the resulting graph as it really is and also the graph arising from not merging coincident vertices (i.e. vertices arising from applying the same vectors in different orders). In the unmerged version of the graph he observes that the total number of vertices of each colour must be equal (because it is just 5^4 pentagons). But then he asks, how many vertices of the unmerged version are merged to form each vertex of the merged version (i.e. the real graph)? And the answer is: for the vertices of the edge-5 pentagon (call these the extremal vertices), obviously there is no merge, because you can only get there with five repetitions of the same vector, but for all the others (call these the non-extremal vertices) it’s a multiple of 5. Now, if each non-extremal vertex of the real graph corresponds to a multiple of 5 vertices of the unmerged graph, any colouring of those non-extremal vertices in the real graph must use up a multiple of 5 of each colour in the unmerged graph. But, the total number of each colour in the ENTIRE unmerged graph (i.e. INCLUDING the extremal vertices) is 5^4, which is ALSO a multiple of 5. Therefore, subtracting, the total number of uses of each colour among the extremal vertices must also be a multiple of 5. And that obviously means one colour must be used for all five extremal vertices.

    Reply

    1. Thanks, Aubrey. Strange thing. At first, I understood Huddleston’s construction, and only then your interpretation of it. The manic desire for a compact presentation and lack of illustrations leads to the fact that you have to sort through a bunch of interpretations of what the author really wanted to say. After everything clears up, it seems that yes, you can’t say better. But something is wrong if you have to spend so much effort on every indistinct detail.

      To illustrate, I’ll show the graph you are talking about. It has 126 vertices and 700 edges (two distances). The term “ordered quintuple” (which became the main snag for me) turned out to be a rather complex object, including the coordinate and color, which are formed as the sum of the five components of the original set of vertices. I did not expect that the concept of sum will be applied simultaneously to two dissimilar quantities, and as for color, this is a modulo 5 sum (colors are just integers in the range from 0 to 4). There were other snags.

      Reply

      1. Yeah, absolutely. But in fairness, I think this is really just a question of familiarity. You and I think similarly (and even then we often do not understand each other at once), but I suspect that professional mathematicians just get used to manipulating these more symbolic ways of doing/saying things and they would actually find Huddleston’s formulation easier to understand than mine. In the end the best thing is probably to work until one understands two very different formulations of something, because that means one REALLY understands it.

      1. Yup. I have to say that even though Dan and Geoff regularly produce fantastic results, I find their work frustrating in one way, namely they always start by pulling a huge rabbit out of a hat and then just showing that it works. When I wrote my paper, at first I thought “what do I even write?” because all I was reporting was a magic graph (my M). But in the end I saw that I could explain several steps that led me to M (starting from T, then U etc). I wish Dan and Geoff would do some of that in their papers, because I think it makes it far easier for others to use similar ideas to obtain their own results. But I’m not really complaining, because I have a feeling that this is another convention of professional mathematicians – I have certainly seen it a lot. It is what it is.

      2. I do think that is a fair criticism though. I may not entirely understand even your initial paper, but there’s still a big difference between getting some basic ideas and thus being able to better interpret related results or seeing a rabbit being pulled out of a hat, and it definitely made it possible for me to see some relevant common threads. As time moves forward and the field of mathematics widens further that problem will also just become bigger, as even professional mathematicians long since aren’t able to just study math in its entirety. I’d say having more step explanations and visual media available for research results would make it that much easier to have people of different field work together and find new results in between.
        I think sooner or later we’ll reach a point where papers should regularly include at least heavy visualization, if not even animated videos.

        I have a hunch at what you’re trying to do and what I’d expect the results to be, but working myself into it would take a prohibitive amount of time. I hope it works out though, I’m curious to see where it’s going.

    3. It seems that the pentagonal graph allows further reduction. I first dropped all vertices with y>0, which gave a graph with 66 vertices. Then I manually deleted a number of other vertices. The result is a graph with 31 vertices and 115 edges, shown below. The vertices 30 and 31 are at a distance of 5. It gives a graph with 61 vertices after spindling. Please check it, I could be mistaken looking at night. If this works, then more compact two-distance 6-chromatic graphs are possible (I got this one manually in single pass).
      https://www.dropbox.com/s/hvjdry971ecd8ci/v31_115.vtx?dl=0

      Reply

      1. I’m sorry but I got lost a while ago. What are the (forbidden) distances here? Also, is there a way to tell where the edges end on this figure? From your reasoning I see that 3 is connected to 5, right?

        Meanwhile, with Peter, we have observed that forbidding 1 and \sqrt{3} or \frac{\sqrt{3}+1}{2} also gives a 6-chromatic graph. The proof [to come] is a simple application of the probabilistic formulation.

      2. The forbidden distances are the ones that are edges around the perimeter, so 1-2 or 2-9. Every line that could be an edge is one, e.g. along 10-8-7-9 every pair of vertices defines an edge except 8-7 and 10-9.

        Great job on the new distances!

    5. It’s funny to notice (when the moderator will wake up) that the spindling distance d=\frac{\sqrt{10}}{2} \sqrt{5+\sqrt5} \approx 4.25325 is almost equal to the diameter of Philip’s 6-colorable disk \approx 4.24852. But this is of course an accident.

      Reply

    6. I wonder if we can find a simple human-verifiable proof that this graph is 6-chromatic. Or, equivalently, in 5-coloring two vertices 1 and 16 have the same color. The graph has only 16 vertices, 28 edges of each distance, only three orbits {{1,16}, {2,3,5,6,11,12,14,15}, {4,7,8,9,10,13}}, a symmetry group of order 48. Where to find easier?

      Here is an example of valid coloring (white-blue-green-red-yellow, I used gray and orange in fact, but it’s better to name them as blue and red):

      Reply

      1. OK. I think it will be quite simple:
        1. We break the set of vertices into the following subsets (layers): {1}, {2,3,5,6}, {4,7,8,9,10,13}, {11,12,14,15}, {16}.
        2. Since the vertices {1,2,3,4,5} make up a 5-clique, we assign different colors to these vertices, for example: 1-w, 2-b, 3-g, 5-r, 6-y.
        3. We notice that the set {4,7,8,9,10,13} has only three independent subsets: {4,13}, {7,8}, {9,10}. We also note that the colors {b, g, r, y} can fall into each of these subsets only once. It means that one of these three subsets will be colored white.
        4. This immediately forbids all vertices of the set {11,12,14,15} to take white color.
        5. It gives a white vertex 16. That’s all.

      4. Yes, thanks, but this is not my merit. You dug a hole, all I had to do was raise this diamond.

  19. Aubrey, I would like to return to your approach of asymptotic expansion of Exoo’s graph on disk. The concept of degrees of freedom is clear. The question is again related to labeling procedure, which I do not understand. So, there is some graph representing a closed chain of triangles and a set of additional edges that limits the variety of colorings. What next?
    Options: 1) we immediately mark all vertices that fall into some small sector as Ai and then we begin to find some vertices in this set that we don’t like, and replace them with others, 2) we mark triangle by triangle sequentially, gradually increasing the number of vertices that satisfy us. Regardless of the option, it is not clear in accordance with what rules we carry out this labeling? Or do these rules have to be defined? Why even drop previously marked vertices? (After all, we are just trying to ensure that the sector of vertices marked as Ai expands and eventually intersects with the sector Bi, so it would be natural to leave all Ai.)

    By the way, do you understand the algorithm from the last Geoffrey-Dan’s article, in particular, the Assign() function? (In general, for some reason I do not like self-calling functions.)

    Reply

    1. First, yes, we label all vertices that fall into some small sector as Ai – or, I would prefer to say, we pick a set of triangles in the chain that do not share vertices (that condition is just to make the labelling concept simpler) and each of which has a vertex in the small sector, and we label those vertices Ai, and the ones 120 degrees clockwise from the Ai as Bi, and the third ones Ci.

      The next step is to check whether the graph on the labelled vertices is 3-colorable in a manner that distributes the colours evenly between the Ai, Bi and Ci. That is the part that is missing from my construction so far: I do not yet have a way to make the overall graph so as to prohibit such a coloring. The precise criterion is that at least one more than half of each cluster is the same colour, so e.g. if we are working with 8 triangles then in any 3-colouring at least 5 of the Ai must be the same colour, and also at least 5 of the Bi and of the Ci.

      Then, the final criterion is that there should be another set of triangles, which consists of all but one triangle from the first set plus one new triangle, and for which all the above is also true. We assume that it is just a different choice of triangles from the graph that is made in the same way, i.e. that it is isomorphic to the first set. If there is such a set, then we know that in any colouring of the overall graph (the entire cycle of triangles) the “majority colour” will be the same for the new set of triangles as for the old set, because so many vertices are in both sets.

      So finally we assume that the new triangle in the new set is oriented just a little bit more clockwise than the most clockwise member of the old set, and similarly that the triangle we have dropped is the least clockwise one from the old set.

      So then, we can repeat this step of replacing our labelled set of triangles with a new set. Our set creeps clockwise, so eventually the Ai start to coincide with the original Bi.

      Is it comprehensible now?

      Reply

      1. Yes, thanks, I think that’s enough. The relationship between coloring and labeling is approximately clear.
        I have a couple of ideas, and I will be back when there is a technical opportunity to test them.

    2. If I understand correctly, you planned to use the following building elements in your construction:
      main closed chain of triangles
      additional edges between free ends of these triangles
      additionally connected Golomb triangles (class1 and class2)
      I want to say that there are certain doubts that these structural elements are enough. The argument here is empirical, not entirely reliable, but quite tangible.

      First, I want to introduce an auxiliary concept of the asymptotic thickness of a ring containing the set of all vertices of the resulting graph. Namely, I separate thin and thick rings. A thin ring asymptotically contracts to a circle of radius \frac{1}{\sqrt3} as the Euclidean diameter of the graph decreases. All other rings can be considered thick, allowing vertices in a certain subrange of radii from 1- \frac{1}{\sqrt3} to \frac{1}{\sqrt3} (corresponding diameters from 0.8453 to 1.1547). An example of a thick ring can be this illustration: https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24369

      Note that your set of structural elements leads to a thin ring. Now all I can do is check how the real graph behaves when the vertex density increases. To do this, I take some base graph, and, by discarding the outer vertices, I get a 4-chromatic graph that fits on a disk of some small radius. Then I remove the internal vertices that are closest to the center of the graph and find the maximum internal radius that preserves 4-chromaticity. The results are as follows (the row shows the base graph, the inner and outer diameters of the ring):

      2H1: 0.58…2.00
      3H1: 0.58…1.74
      4H1: 0.58…1.59
      5H1: 0.58…1.59

      2H2: 0.91…2.00
      3H2: 0.75…1.48
      4H2: 0.75…1.40
      5H2: 0.76…1.34
      6H2: 0.76…1.34

      2H3: 0.91…2.00
      3H3: 0.85…1.48
      4H3: 0.77…1.30
      5H3: 0.79…1.28

      2H4: 0.91…2.00
      3H4: 0.67…1.44
      4H4: 0.83…1.29

      Here I do not observe a tendency to contract to a circle, that is, as far as one can see the asymptotic sequence of graphs forms a thick ring. So, it requires some additional structural elements.
      Even if we think that no definite conclusions can be drawn from obtained data, we can think about how to correct this test.

      Reply

      1. Yes, I think a reasonable conclusion from your data is that graphs formed by that “H” method cannot create a thin ring. However, I don’t think it tells us anything about graphs formed by my method. The trends that I observed when adding Golomb triangles to a cycle of triangles seemed to be heading towards a thin ring, even though I was doing it in the most constrained way, i.e. with all the chain vertices at the same distance from the origin, so zero degrees of freedom and no additional edges. My newer approach, going the opposite way and having lots of radii (i.e. lots of degrees of freedom) and no Golombs, seems to be more likely to lead to an actual proof that we get a thin ring, but of course we don’t yet have an actual construction.

      2. When you made your observations, you did not determine the position of the Golombs of class 2. Perhaps they cannot be brought closer to main circle, which again gives a thick ring. Or do you have other results?

      3. Ah, I don’t think that’s a problem. I think I avoided that problem by forcing the class 2 Golombs to have two of the connected vertices be extremely close to 1 apart (that was my “f^2” tring). I’m pretty sure (analytically – no data involved) that with that constraint, the Golomb vertices converge to a thin ring if the other vertices do.

      4. Why should f ^2 work?
        Perhaps you`re right. It may turn out that choosing vertices in \mathbb{R} will give a thin ring, while in \mathbb{Q}[\sqrt{3},\sqrt{11}] thick one. We have an example with stripes where we get a thin border, though in both \mathbb{R} and \mathbb{Q}[\sqrt{3},\sqrt{11}]. So this example can hardly be used as an analogue either.
        I bet on a thick ring for now. If only because it gives more degrees of freedom.

      5. Actually I think we can go lower than f^2 – I think any power greater than 1 would work, because that’s all we need to ensure that as f tends to 0 we pull the Golomb vertices towards the ones they are connecting. The only need, then, is to show that f really does tend to 0. And that can (I think, at this point) only be examined empirically, which is why I think it is probably better to try the other option of introducing degrees of freedom.

  20. Here is a short summary of why forbidding the distance set $latex\lbrace 1,\sqrt{3}\rbrace$ or $latex\lrbace1,{\sqrt{3}+1\over\sqrt{2}}\rbrace$ makes the plane non-5-colourable:
    One can do the probabilistic argument the same way for a 5-colouring of the plane (now only forbidding unit distances) as for 4 colours since S_5\times E(2) is also amenable. From here, similarly to http://michaelnielsen.org/polymath1/index.php?title=Probabilistic_formulation_of_Hadwiger-Nelson_problem#Proposition_36 , p_d\lneq{1\over 2} for all d’s at least $latex{2\over\sqrt {15}}$. But then in all of the (1,d)-graphs linked below (all having 6 vertices and 13 edges (1-edges are represented by red segments and d-edges by blue segments)), there must exist at least one pair of vertices having the same colour (as all of them have 6 vertices) and the p‘s of the two missing edges don’t add up to 1, so the event that at least one of the d-edges are monochromatic has a positive probability, so p_d\gneq 0.
    https://drive.google.com/file/d/1zsjsdK2q-HS_YoqevmY3GC3ijgXHKdRT/view?usp=sharing
    (Two of these are the inverse graphs of the other two.)
    Also, the proof described in https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24455 uses that the subgraph spanned by \lbrace 4,7,8,9,10,13\rbrace is a (1,d)-graph on 6 vertices with 12 edges, so it could be quite interesting to find such a subgraph for a general d (for 13 edges there is no such graph as I have written it in Proposition 2.16 in my thesis https://drive.google.com/file/d/1Khp85TYPJ8ehbD9P9Q5qC6U9enChZYDI/view , and similarly, for 12 edges, the only possibility would be three disjoint non-edges as in the graph mentioned above, as otherwise we would find a K_4 in it). After going through a few cases, it seems unlikely that such a graph exists, but here is one with 11 edges: https://www.geogebra.org/m/yhpdwubt (D is movable).

    Reply

    1. Very nice work Peter – congrats! I am immediately wondering whether your method here can be combined with the insight of Tetiva that I paraphrased above:

      https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24436

      to obtain this result for additional distances. We would need a variant of your flexible 11-edge graph in which two vertices are distance 3 apart (here I refer to graph distance rather than Euclidean distance) and can be arranged to be at a Euclidean distance such that they can be assumed to be the same colour. It would need to have 7 vertices rather than 6, and to have two non-edges of equal length that cannot both be bichromatic in any 5-colouring that also has that other vertex pair monochromatic. Any ideas?

      Reply

      1. Peter and me have looked at the Tetiva argument. We believe that it won’t give anything new compared to the probabilistic formulation. For example, what you ask for in the last sentence, would be 2p_d+(1-p_{d'}) to be less than 1, while with our current methods it is barely less than 2.

  21. It took me a while but here’s an additional video seeking to make my previous posts more easy to follow through animation as well as plugging some holes. Hopefully that’s enough, but that remains to be seen and further tested.

    Here’s what I currently think:
    For two or more dimensions, for every 2 n-balls at unit distance, each n-ball contains uncountably infinitely many independent subsets (lines), each with full exclusion of the other ball on their own. An even speckling of such a line has accordingly reduced exclusion (so a third of such a line evenly speckled means a third of the other ball excluded from the same color). There is no way of adding a new speckled line without adding to the exclusion (except shifting densities/making solid intervals, contradictory to speckling). Since a full speckling of a n-ball is effectively taking a chunk out of the available measure uncountably infinitely times we are inevitably converging on 0 usable measure and full exclusion for any positive measure speckling.
    If we have ball K3 and assign a speckling with 3 colors with positive measure to one of the 3 balls, the other 2 balls can’t contain any of those 3 colors, so no efficient coloring while speckling. This generalizes to all proper n-ball graphs too and should get everything that’s not a solid volume of color off of the table.

    Here’s the video (it’s just 5:28): https://www.youtube.com/watch?v=TVb1itT0HWM

    I don’t plan on making more videos trying to prove anything unless something new comes up that would warrant that, but across the next months I’ll work on building a video to create strong visual intuition on tiles and exclusion zones, as well as presenting as many of the tilings discussed in here as I can in animated form as well, but that’s not gonna be done and released until the one or the other month into next year.

    Reply

  22. Finally, the Overleaf file in which Dömötör and I started to write up the results of the project starts to look somehow (although there is still a lot of work with it), so we have decided to share it with others so that everyone can write their part in it (sorry for the delay). E-mail me to get access to the file: my username is agostonp and the domain name is cs.elte.hu.

    Reply

    1. Bravo Peter! Many thanks.

      I had not come across this Overleaf thing before, but at first glance it seems to be fairly easy to use. I will try to find time over the next couple of weeks to write up the parts that most inescapeably fall to me. I think that basically means the tile-based colouring and higher-dimensions sections. I would be delighted if Philip could return to the fray and help with these, since much of the key work was his.

      There are at least two things we should include that I don’t see in your sketch:

      – proportion of the plane that can be k-tiled: Jaan improved this number for k=5 and 6. This could be a subsection of section 3, if section 3 is renamed “k-colouring of subsets of the plane”.

      – Domotor’s realisation that we don’t know how to 7-tile the surface of a sphere of arbitrary radius (or even of sufficiently large radius). This is a bit of an orphan in that we have no new results regarding the surface of any sphere (right?), but it seems a pity not to draw people’s attention to it. Perhaps I can come up with a subsection under “Higher dimensions” that includes miscellaneous things like this.

      Concerning tile-based colouring, I am confused by what you say about Thomassen’s result. You seem to be saying that he showed that the only way we might be able to 6-tile the plane is with Siamese tilings (in which some pairs of tiles of the same colour lie within each other’s annuli of exclusion). But I thought Thomassen actually showed that the only way we might be able to 6-tile the plane is with “unscaleable” tilings, in which some tiles have diameter exactly 1 and some pairs of tiles of the same colour are exactly 1 apart. Can you explain?

      Reply

      1. Thanks, indeed I forgot that condition from Thomassen, now it’s fixed.
        Regarding spheres, we also wanted to include them, the only question was whether they should go to Section 3 (different shapes) or to Section 9 (higher dims).

        A technical question: Should the write-up discussion happen here, or on a separate thread or even at an entirely different place? I don’t care either way, if anyone has some preference, they should speak up.

      2. I was thinking about how to 7-color a sphere. No success, but I’ll share my ideas since it’s been quiet.

        Color an icosahedron and then project it to a sphere. First pick a color for each vertex of the icosahedron (12 vertices). Opposite vertices get the same color (6 colors). Find a coloring for one face of the icosahedron and then each other face gets the same coloring, but with colors permuted relative to the vertex colors. I tried SAT-solving, but got poor results.

        I tried making a “simulation”: https://youtu.be/LPtMyQeWa4Q
        Particles of 7 different colors repel each other when they get close. Particles of the same color repel at an even greater distance. After running the simulation, the colors are nicely spread out and the Voronoi diagram of the result looks promising, but it doesn’t work.

      3. So, the 7-color hex tiling works great on a plane, but on a sphere you need a pentagon tile somewhere. In the scenario above, I’m already stuck. Only 5 blank hexes can be filled in with the existing colors, and the 7th color can’t fill in the remaining.

        So, maybe there’s no 7-coloring of the sphere with polygonal tiles?

      4. Right. I’m pretty sure that if there is a 7-tiling then it is of the “unscaleable” variety in which some tiles have two neighbours of the same colour, one touching only at a vertex. I think a good place to start is Philip Gibbs’s 6-tiled disk of diameter slightly over 4, but I haven’t had any luck extending it.

      5. @Tom Yes, my observation was the same, that on a sphere we always have a pentagon becaue of the genus is smaller. I think right now Peter is working on whether Thomassen’s argument can be modified to prove that 8 colors are needed with his conditions.

      6. OK, I modified the simulation. Given a graph like on the left, it’ll find the dual graph and figure out which pairs of vertices need to be at most/least length 1. Vertices are incrementally moved for each violated constraint. The results tend to be good even with sloppy input.

        I applied the simulation to some past graphs here:
        https://groups.google.com/forum/#!topic/hadwiger-nelson-problem/J_Tw1_hUxQI

        It’s a useful tool for quickly exploring tiling ideas. (It should be easy to modify the simulation to work on a sphere)

      7. Wow, amazing! I can’t imagine how many months it would have taken me to code such a thing.

        I’m going to write a proper reply on the new thread.

  23. I’d be happy to roll the thread over. Does Overleaf provide a link to a read-only version of the pdf that updates automatically? If so, I’d like to include it in the next thread.

    Reply

    1. We’ve discussed this with Peter, and we were not sure if such a link for the working version should be made public, especially until the write-up is in such a preliminary stage. But if you think we should, it can be done.

      Reply
  25. Pingback: Polymath16, fifteenth thread: Writing the paper and chasing down loose ends – Short, Fat Matrices
  26. Pingback: Can planar set contain even many vertices of every unit equilateral triangle? – Math Solution

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s