# Polymath16, fourteenth thread: Automated graph minimization?

This is the fourteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The biggest development in the previous thread:

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

## 33 thoughts on “Polymath16, fourteenth thread: Automated graph minimization?”

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

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

We also need the following well-known result.

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

From here, we can finish very easily.

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

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

1. ag24ag24 says:

Whimper…

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

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

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

But I’m having trouble elsewhere:

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

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

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

0) Yes.

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

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

3) Yes.

2. ag24ag24 says:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. ag24ag24 says:

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

1. ag24ag24 says:

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

2. Jaan Parts says:

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

1. Marijn Heule says:

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. Jaan Parts says:

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. Marijn Heule says:

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. Jaan Parts says:

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. Marijn Heule says:

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. Jaan Parts says:

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. Marijn Heule says:

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. Jaan Parts says:

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. Jaan Parts says:

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

10. Jaan Parts says:

But there is reason to think that this is a real trend. We can recall Golomb as an analogy.

11. Marijn Heule says:

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.

12. Jaan Parts says:

Yeah, but what about the “triangular” shape? Have you not noticed it?

13. Marijn Heule says:

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. Jaan Parts says:

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

4. Péter Ágoston says:

1. ag24ag24 says:

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

1. Péter Ágoston says:

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.

2. ag24ag24 says:

Thanks. I think that 27-vertex graph is the Hamming(3,3) shown in Wikipedia’s UDG page.

5. Is the union of two unit circles always 3-colorable? If no, this would show CNP>=5 if $p_d\ne 0$ holds for their centers.

1. ag24ag24 says:

Just making sure – you mean unit radius, not unit diameter, right?

1. Péter Ágoston says:

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.