Graph Coloring by Simulation

[Tom Sirgedas]

I'm interested in the problem of 7-coloring a sphere. It seems important to use tiles with some vertices exactly a unit distance apart.

Here, Philip Gibbs presents a nice 6-coloring:

I wrote a program that lets you construct graphs like this. It will find the dual graph and detect which vertices in the dual graph must be kept near (unit distance or less) and/or kept far (unit distance or more). As the simulation runs, pairs of points are brought together or push apart in an attempt to meet these contraints. If you change the colored tiles into vertices and place an edge between adjacent tiles you get a graph like this:

A nice feature is that the graph can be a bit sloppy.

Here is what the simulation produces for the above graph:

Here I show the vertex pairs that must be exactly a unit distance apart:

You can perturb the points in the simulation:

[Tom Sirgedas]

Here I drag the tile vertices around, and violations are shown with faint red/green lines:

[Tom Sirgedas]

Some example graphs from Polymath16 and the result from my simulation program:

4 and 5 coloring example:   [link]

Impossible to color:   [link]

Impossible to color:   [link]

Infinite ribbon:   [link]

[Tom Sirgedas]

Here's are various tile colorings from Polymath16 alongside the simulation versions:

[Link]

[Link]

These last two are fairly flexible, but there is a kind of square lattice preventing too much warping. My simulation initially was a bit "folded up", and I manually dragged out the folds.

[Link]

[Link]

[Tom Sirgedas]

Jaan's modified Pritikin tiling:   [Link]

[Tom Sirgedas]

[Tom Sirgedas]

Pritikin (?)

[Tom Sirgedas]

Video showing the user interface: https://youtu.be/LStdBtMO2EM

[Tom Sirgedas]

I made a Windows EXE in case anyone is interested in playing with this app.

Download link: https://drive.google.com/open?id=1WGVY40cZL7gH0DUKVGEQx2J1N7x04Suk

Instructions:

- Build a graph in the large gray area

  - To add a vertex: Move your mouse to somewhere in the gray area, and press a number key 0-8 or one of R,B,Y,P,G,O,C,W,K

  - To remove a vertex: Move your mouse over a vertex and hit <Del>

  - To move a vertex: While holding the M key, drag the vertex around

  - To add/remove an edge: While holding the E key, click on a vertex and drag to another vertex (and then unclick)
- Press [Retile] to calculate/refresh the dual graph

- Press [Play] to start the simulation

- Press [Color Polygons] to see the colored tiles of the dual graph

Experimental:

- Press the "equals" key (=) to recolor your vertices. The app will attempt to find a coloring that provides valid tiles using the fewest colors (up to 9 colors). Sometimes tile edges will collapse. Larger graphs may cause the app to hang.

[Tom Sirgedas]

When coloring a graph, my search currently requires 

- polygons have unique colors

- each vertex has unique color neighbors

- no sequence like this  `[a><b][a><b]`

- rigid lines inside a polygon must intersect

These rules can produce decent results, but multi-tile conflicts are possible:

[Tom Sirgedas]

I wrote some code to take a triangle graph as input and SAT-solve to output a colored subgraph. Edges may be removed by the solver, but no triangle can have more than one edge missing.

The SAT rules prevent a lot of degenerate tiles. One advanced SAT rule is that a single tile is not allowed to have "rigid lines" which don't intersect.

However, in this example result, the output graph is still invalid. In this example it seems that it's the combination of many tiles causing the problem.

(Maybe it is best to allow the SAT solver to output many answers, in the hopes that some don't have multi-tile conflicts?)

[Tom Sirgedas]

Interesting coloring starting from Jaan's graph

[Tom Sirgedas]

So, SAT-solving finds lots of solutions that don't actually work. For small graphs it doesn't cause much trouble, but once the the graph reaches Gibbs' graph size and larger, you get multi-tile contraints which cause the SAT solution to not actually work.

Now I'm taking a different approach, inspired by Aubrey's suggestion to explore 6-colored discs.

Given a graph with one vertex fixed on the origin
- Find the vertex on the perimeter of the graph that's closest to the origin

- Close off that vertex with an edge (possibly split the edge into two edges)

  or

- Attach a new polygon (triangle or quad) to the graph, where the new polygon includes that vertex, and the "next" vertex on the perimeter

By repeating these steps and also backtracking, this sort-of enumerates all planar graphs that are comprised of only triangles and quads.

Each new generated graph is simulated. If the simulation fails to settle into a valid solution, the graph is discarded. Otherwise, it's recorded and recursively extended.

[Tom Sirgedas]

For 5-coloring my enumeration unfortunately doesn't consider the "previous best", because it has a pentagon (there's a vertex where 5 colors meet).

However, it found another configuration which seems slightly better from a crude measurement.

[Tom Sirgedas]

Currently my searcher is starting with a triangle (vertices 0,1,2 above) and expanding from there. Above are some interesting finds so far. Nothing toooo close to Gibbs' tiling yet.

[Tom Sirgedas]

Finished searching with a quad & triangle as starting points. The quad found 247744 graphs, and the triangle found 36757 graphs. The graphs are a bit sensitive to the exact geometry of the starting graph.

Anyways, the best found results are basically Gibbs' graph with some extra junk on the perimeter. The searches took ~20 hours on my home machine.

[Tom Sirgedas]

Currently searching for 6-colorings again, but this time with a better estimate for achievable radius for the graphs it's finding. I think the above solution doesn't quite work, but it's close! And the radius is pretty close to Gibbs' solution.

Anyways, I'm not too happy with my current search technique. I'm growing a graph, and at each "step" I'm checking if the graph can be turned into a valid tiling (the dual graph, like in the image above). The positioning of the vertices in the underlying graph is a arbitrary but it affects the results a bit. Also, the whole search process will be much too slow for larger graphs.

It seems that the "rigid" edges (those that must be unit length, drawn in black in the image) are most important, and the tiling follows from that. But, in my current search technique the rigid edges are a side-effect of the search instead of really driving the search. Is there a search technique that can explore unit graphs like the rigid edge graph above? This could allow constructing good tilings more directly.

[Tom Sirgedas]

(click to see full size)

Some of the better resuts from the search so far.

I'm think most/all of these have flaws, but they're still kind of interesting.

[Tom Sirgedas]

Is there a search technique that can explore unit graphs like the rigid edge graph above?

I think I should just get rid of the underlying graph and construct the tiling directly. This will benefit automated searching quite a bit. Also, rigid edges (constraints) can be considered as the tiling is being built. Anyways, this should get rid of one level of indirection that's causing many problems for no (?) benefit.

(Half-baked idea...) If there are enough constraints, maybe even the tiling vertex coordinates can be calculated more directly instead of simulated. E.g. maybe fixing an angle between two rigid edges will make it easy to solve for many other coordinates. The fixed angle could be searched for numerically.

[Tom Sirgedas]

My search found this Pritikin-style tiling, but again it doesn't quite work. Ugh.

Currently working on creating tilings more directly. I'm keeping in mind that rounded edges and  need to be handled better. (Also same-colored tiles separated by more than one tile.)

[Tom Sirgedas]

My old search found a nice result and I made it symmetrical here. It's flawed, but so pretty!

[aub...@sens.org]

Hi Tom - very nice! But what is the "flaw"? - I can't see anything wrong with this tiling.

[aub...@sens.org]

Ah, scratch that, I see the problems now :-)

[Tom Sirgedas]

It was hard for me to eyeball, but a clear way to tell is with the white line. The curved purple tile forces the white line to have length 2, and the two rigid edges connecting the same vertices. This trick helps show that the second diagram is invalid, just barely. I'll try to get my new simulation to handle curved edges a little better once I get the search working.

[aub...@sens.org]

Yep. That isn't quite how I saw the problem but it's similar. My way is as follows: basically, if a tile (such as your most-central purple tile) has two neighbours of the same colour (blue in this case), then not only must at least one of them touch the purple tile only at a point (call it P) rather than a line, but also, if one of them touches at a line, the other one must have at least the same (non-zero) angle occupied by a third colour (green in this case) between it and the purple tile as the angle subtended at P by the blue/purple line. In this case the green tile occupes zero angle at P, so we fail. Maybe this way of saying it is something that can more easily be built into your code? But actually, your way of doing it looks pretty codeable too.

[Tom Sirgedas]

Does your logic also apply to the diagram on the right? The green/blue line subtends 60 degrees at P. So the purple tile needs to be at least 60 degrees?

The right diagram doesn't have nice symmetry, so I think the logic doesn't work there. But maybe I'm missing something.

[Tom Sirgedas]

Here's some detail about my new search approach. The tile graph is built incrementally, one tile at a time. You start with a single (degenerate) tile that connects two vertices. You don't decide up front what the final shape of your tile will be.

To add a tile, you look at the perimeter of your tile graph. Decide what part of the perimeter your tile attaches to. Critically, your options are very limited. The perimeter only has a few vertices, and you can attach your tile spanning any two vertices on the perimeter. You can also attach on the perimeter *between* two adjacent vertices. This creates a new vertex.

That explanation probably isn't very clear, so here's a video of me constructing a small graph with this method (in my partially working new simulator):

https://www.youtube.com/watch?v=n3fLfdAvbRA&feature=youtu.be

At each step I'm deciding the tile color and where on the perimeter the new tile belongs.

The payoff is that the possible tile graphs can be searched by incrementally building them up with limited choices at each step. If a graph can't be embedded in the plane successfully, then we backtrack. This is great, because we can abort a search early, without deciding unnecessary info like how many neighbors each tile will have.

[aub...@sens.org]

I think it applies there too, yes. (Of course the purple tile indeed is 60o for other reasons.) Basically, if we draw unit-radius circles centred on each of the upper blue corners, they will pas through P but they must not intersect the lower green tile.

[aub...@sens.org]

That sounds very sensible and efficient. Are you incorporating the constraints described on the wiki? I mean the eight constraints listed near the end of the "tile-based" section here:

http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem#Tile-based_colourings_.28tilings.29

[Tom Sirgedas]

Oh, yeah, I think I see that. So the purple tile is required to be 60 degrees or more and it's exactly 60 degrees. So green tiles are okay there, it's just the blue tiles that are slightly too close.

[aub...@sens.org]

Um - you're referring back to the left-hand disc now, right? There, yes, the most-central blue tile is too close to the one above it (and similarly for the analogous red and purple pairs). But in the right-hand disc I can's see any flaws at all.

[Tom Sirgedas]

No, I'm talking about the right-hand disc.

The blue tiles are slighty too close. The white arrow shows this: the top part contained in the blue tile must be exactly unit length. The rest of the arrow must be at least unit length, so that the blue tiles are far enough apart.

But, there are two rigid edges that together almost coincide the white line, but they bow to the left a little. So those two rigid edges plus the white line create a skinny triangle. Since the two rigid edges don't form a straight line, the white arrow must be less than 2 units in length. So, the two blue tiles are slightly too close together.

[aub...@sens.org]

Ah, of course, got it. So my condition is too weak -- yours is better.

[Tom Sirgedas]

I sort of understand the 8 constraints, but I'm not sure if they apply exactly to what I'm doing. In my graphs I know the structure of the graph already, and I figure out which pairs of vertices need to be kept at most a unit distance apart, at least a unit distance apart, or exactly a unit distance apart. For each edge, I figure out which vertex it needs to curve away from (if any). If a vertex wants to curve away from more than one point, the graph is invalid. Also, I make sure that a polygon's rigid edges all overlap.

It seems like the wiki rules are trying to figure out some contraints without a specific coloring in mind.

[aub...@sens.org]

Exactly - yeah, so I guess they are not really useful for your implementation.

[Tom Sirgedas]

I got the new simulator running with a searcher. I found a nice way to "hash" the tile graph so that equivalent graphs (permuting vertex indices and colors) map to the same hash value. This lets me search by extending a graph and discarding children whose hashes have been seen before.

When I added in that distance-2 rule I noticed that the 6-color searcher was struggling to find nice discs. I everything is below 1.9 radius so far, ugh. At least the solutions it finds aren't all flawed like before.

Above is a  pretty 1.82 radius disc that I manually cleaned up just slightly.

I'm a bit disappointed that the searcher hasn't gone through all the graphs. It's analyzed 209,000 graphs, and only a ~200 so far are 1.8+. Of those, there are only like ~3 different graphs, but with lots of boring inconsequential variations on the perimeter.

And my search isn't even exhaustive. It even fails to find the 1.158 radius 5-coloring. Hmm, maybe I'll dig into that.

[Tom Sirgedas]

I'm thinking that some theory might be useful for searching these tilings. Maybe there's some nice invariants.

Good discs tend to have curved edges curving away from the center of the disc, at least for the outer tiles. A curved edge adds possibilities on the inside of the curve, and removes possibilities on the outside. For 6 colors, it seems that as you grow a disc you slowly lose possibilities -- you need to consume more possibilities than you can leave for the next layer of tiles.

Look at the green arrow from the picture in my last post. The entire yellow edge there can only be green (and even then the curved edge of the nearest green tile interferes). Some blue or red would have been fine if the nearest blue/red tiles weren't already curved the "wrong" way.

I feel like there's some elegant way to formalize this idea, such that it can show no 6-tiling of the plane is possible.

[Tom Sirgedas]

diagram showing curved edges for Philip's disc, and the 1.82 radius disc

[aub...@sens.org]

I would definitely start by focusing on 5-tilings and recovering your 1.158er! Far fewer cases to explore, and it's clearly a bug.

I agree about invariants, but I have a feeling that the invariant is simply the configuration of the inner tiles. There is probably always going to be a large number of alternative ways to do the outer tiles that lead to similar disk sizes.

As for other theory, I think the question of whether you indeed consume options as you move out is more or less what the eight rules on the wiki are trying to encode.

But wait - are you now including tilings where five tiles meet at a vertex? Seems like that matters, if the 5-tilings are anything to go by.

[Tom Sirgedas]

Yeah, five tiles can meet at a vertex, but haven't that in any of the best results.

In the diagram with the white arrows -- each quad in the graph "emits" an arrow for each of its degree-5 vertices. I think I can show that an infinite 6-color graph would have 80+% of its edges curved. Not sure if that's theoretically useful, but it maybe it could help search graphs in a smarter way.

If all the infinite graph has all degree-5 vertices, and only triangles & quads, then 1/3 of the polygons will be quads. Each quad emits exactly 4 arrows (curved edges).
N vertices 
2.5N edges

.5N quads

N triangles

2N curved edges

So, 80% of edges are curved here. I doubt allowing pentagons helps, because a pentagon will emit 10 arrows instead of 4 for a quad. Allowing a degree-4 vertex can prevent curved edges adjacent to that vertex, but I think it creates another quad/pentagon.

With such a high density of curved edges, maybe they can help find in a proof.

[t.sir...@techsmith.com]

same logic, but with 5-coloring:

assuming all degree-4 edges, and only quads:
N vertices

2N edges

N quads
4N curved edges (4 per quad)

so 200% of the edges are curved, so a 5-coloring is impossible.

If we assume a less-than-4 average degree, say, 3.8:

N vertices

1.9N edges

,9N polygons

then polygons on average have (2*1.9N)/(.9N) = 4.222 edges, which I think isn't allowed, because pentagons mean 5 colors are meeting a vertex, and you can't color a unit disc around that vertex.

If we assume there are a bunch of non-quads, then we'll have triangles and pentagons, and pentagons are no good.

So, I think this shows that a 5-color tiling is impossible

[aub...@sens.org]

Unfortunately, the fact that tile-based colourings need 6 colours was already known :-)

In fact, it was known in full generality (concerning tilings - specklings could still deliver 5), whereas we must remember that the approach you are taking does not consider the case of what I've termed "Siamese tiles" - small tiles that lie entirely within each other's annulus of exclusion (i.e. all points in one are <1 from any point in the other). Such tilings of the plane with 7 colours do exist that cannot be trivially flowed into tilings without such pairs of tiles. But that's fine - a proof that we need 7 colours unless there are Siamese tiles would still be a really big result.

[Tom Sirgedas]

Ah, ok, I was just excited to apply the curved edge counting idea!

[Tom Sirgedas]

I've been seeing if I can do an exhaustive search of 6-colored graphs, but without trying to actually embed them.

Above, I was interested in starting with a hexagon (6 colors meeting at a vertex), and then doing a search to "enclose" vertex 0, then vertex 1, ..., then vertex 20. I was hoping that it would be impossible, but solutions are found.

So far, here are the rules (from the perspective of graphs like at the top of the image, where each vertex has a color):

1. no vertex can have the same color neighbor

2. no polygon can have two vertices with matching colors

3. if vertex A and vertex B are connected by an edge, B can have a diagonal* of A's color, OR A can have a diagonal of B's color, but not both (in terms of the bottom diagram, an edge can't curve away "both ways")
4. in terms of the bottom diagram, no polygon can have rigid edges that don't intersect

*diagonal = (in terms of the top image) two vertices on the same polygon, but not neighbors  (0's diagonals are {2,3,4,7,9})

These rules apparently aren't enough.

Rule 3 should be more general, since it fails to prevent this scenario in its current form (note the blue-red edge needs to curve "both ways").

Instead I tried preventing enclosed vertices from having only 3 neighbors. This produced the results in the first image. I'm not sure if there are simple rules to prevent the conflicts in the first image?? 

[aub...@sens.org]

Hm. Not sure what to suggest. I have a lot on this week but I'll think more about it soon.

[t.sir...@techsmith.com]

No worries, I just like writing down my thoughts and progress in case they're useful/interesting! I'm interested in any feedback, but don't feel any pressure

[Tom Sirgedas]

Another way to prove a graph is impossible is just from the rigid edges. Bigger 6-color candidates like this are found to be degenerate in the simulator, but I'm not sure how to prove it.

Maybe counting degrees of freedom is helpful? (Not in the example above, though, I think?) Maybe on an infinite graph?

On the "hexagon" example in the previous post, the rigid edges form enough triangles that you can figure out the exact coordinates, but I'm not sure that works very well in general (like in the above example).

[Tom Sirgedas]

Starting with a quad (vertices 0,1,2,3), I searched for planar graphs with degree 3-5 that enclose the starting vertices. I found 1,679,616 results. Here are 1/40000 of them:
https://imgur.com/a/ECLeGBV

I thought if there weren't too many results, a color-less search like this might be handy.

[Tom Sirgedas]

I can use the simulator to help figure out what rules are missing. I load up a graph that my searcher finds and simplify the graph as much as possible (and make sure the graph is still un-embeddable)

Here the white dotted line is effectively a rigid edge because of the other edges.

And then the black dotted lines aren't long enough. They're not rigid, but they're connecting two vertices already connected by two pairs of rigid edges (forming a rhombus), and the black dotted lines are on the outside of this rhombus.

[aub...@sens.org]

I'm not getting that one. The short edge of the red triangle needs to bend out (my terminology is that it is "red-fat") because of purple tiles, but I don'tsee what makes the dotted white line rigid.

But I definitely like the general ideaof identifying new rules by using the simulator!

[t.sir...@techsmith.com]

It might be hard to see the rigid edges in the picture.

But, fix the purple triangle. The green rhombus's top is translated from the bottom. The top-right pink edge is translated from the purple/pink edge that same amount. So the white dotted line is just the third purple edge, translated by the same amount.

It took me a bit to realize this, but playing in the simulator makes it easier to see how the rigid edges interact.

[aub...@sens.org]

Ah, yes, got it! That's subtle.

Actually I was also slightly thrown by the fact that your previous pic had eight colours :-)

[Tom Sirgedas]

Haha, yeah, it's often useful to quickly substitute a color to see if it's involved in the conflict I'm looking at. Hmm, I should make a "null" color.

[Tom Sirgedas]

I'm making a new graph searcher. This one searches tile graphs as described here.

The colored lines surrounding the tiling above tell you where on the perimeter is it legal to add what color polygons. You can see that below the orange tile with vertices 29, 30, there's no way to add a polygon. (So, the search that produced this tiling is at a dead end and must backtrack. The early detection of a dead end saves a lot of computation!) Similarly, no polygon can be added that shares an edge with the blue tile and vertex 27.

My searcher does a simple depth first search. It finds the lowest index vertex on the perimeter and adds a polygon that includes that vertex and the half-edge on the perimeter clockwise next to it. So, if we weren't at a dead end, we would explore two options at vertex 17: Add new vertex 32 to the yellow polygon and attach a purple polygon from 17 to 32, OR add a new vertex to both the blue and yellow polygons, and attach a purple polygon on the perimeter spanning those two new vertices.

[Tom Sirgedas]

I have the usual rules in my searcher, and added a simple new rule:

If vertex a has 4 neighbors vertices, it cannot have rigid edges to two opposite vertices.

In the diagram above, vertex a has 4 neighbor vertices, including rigid edges to opposite neighbors b, c.

This is prohibited because the 4 neighbor vertices form a quadrilateral, and one of the "paths" along the quadrilateral from b to c will be greater in length than path along the rigid edge.

[Tom Sirgedas]

After enumerating 20,000,000 graphs over ~20 hours, the tiling above encloses the most vertices (69) so far.

Loading this tiling in the simulator makes it clear that there are quite a few violations that aren't covered by the rules. Even so, no search path has expanded to infinity* which makes me hopeful that the search will terminate.

*Well, I did have trouble where I'd get large infinite graphs with a perimeter of 2, where 2 polygons would together enclose the entire graph. I still got very large graphs with tiny perimeters (5 or less polygons on the perimeter??). I added a rule to the searcher to abort any search where

# polygons on perimeter SQUARED < # polygons

This seems like a reasonable constraint, but I'll have to revisit this idea once I can get the search/enumeration finished in reasonable time.

[aub...@sens.org]

That's progress! Do you have any way to estimate how many graphs remain to be examined?

True about the violations. I guess that means it is worth continuing to look for more rules.

[t.sir...@techsmith.com]

I don't have a good estimate, but it would be pretty easy to get a very rough estimate with the current search technique. (Just run the same search, but never search deeper than ~10 polygons -- If this has say 100,000 steps, then the full search can print progress relative to these 100,000 steps).

But, I think a powerful idea is to check if the current graph has been considered before (with a different permutation of vertex indices & colors) -- this can be done pretty efficiently. If the graph HAS been seen before, that means that it was a dead-end (otherwise we would never have back-tracked to reach the current graph). I'm hopeful that this makes the search MUCH faster.

I'm not too eager for adding more rules, unless they're very simple or very effective! In the end I'll be eager to remove rules if they don't help too much (it'll be easier to prove that the code is correct).

[aub...@sens.org]

Ah, that's a very cool way to do the estimate. I think you should do that at once.

Very true also about graphs considered before.

Not sure I agree about rules though. I think the true minimal set of rules is likely to be quite small , i.e. you will indeed be able to remove rules that don't help at all and can be proven never to do so, but only by first finding the better rule, which in turn is achieved by identifying a tiling that needs it.

[Tom Sirgedas]

OK, so search has been printing a status line (basically the current depth of the search) each time the current depth of the search (basically # of polygons added to the tiling, in addition to the starting 2) is less than 12, and there are ~1.4 million status lines so far.

I did a quick search where anything with depth >= 8 gets aborted, and here are the approximate hit counts for each depth: (these values got printed each time the last element reached a multiple of 100,000, so it's not exact)
CT = {1,6,49,382,4166,20220,72047,270000}

Based on that, I'd guess very roughly 20 million for a depth of 12, so my search is very roughly 10% done, which is great!

[aub...@sens.org]

Indeed, fanastic! I see that the ratio of consecutive numbers in that series bounces around really a lot, so I won't be surprised if it ends up closer to only 2% done, but still.

I think this constitutes sufficiently tantalising preliminary data that the group should be informed, given that there has been quite a long time since any activity there. Agree?

[Tom Sirgedas]

Hmm, I think it's still too early to share, but hopefully soon! 

I want to prevent some decent evidence for my claim and not just "trust me".

[aub...@sens.org]

Sure, totally up to you to make that call.

But meanwhile, I'd love to see (just here or in email) a list of the rules you're curently using for the search. Can you share?

[Tom Sirgedas]

Rules for a valid graph:

- vertex can't have duplicate color neighbors

- edges can't curve away from more than one vertex

- a polygon can't contain two rigid edges that DON'T intersect

- the diamond rule from yesterday

Search rules:

- # vertices must be less than or equal to # of perimeter vertices SQUARED

- new polygons are added one at a time, to some contiguous portion of the perimeter (starting/ending at an existing vertex or creating a new vertex)

[Tom Sirgedas]

counts before/after checking for "duplicate" graphs

0,0,1,6,49,382,4166,20220,72047,270000

0,0,1,4,24,153,1435,6768,25383,90175,(274767,684124,1726566)  (took 15 minutes)

So, 9x improvement for graphs with 9 polygons.

Here are the 153 unique tilings with 5 polygons according to my searcher: https://imgur.com/a/OxpsLzp (unfortunately the drawings are mostly degenerate when the tiling perimeter has 2 vertices, or when such a tiling is expanded)

Now running a full search overnight -- it's already on the 15th 5-polygon tiling out of 153, so a good sign so far.

[aub...@sens.org]

Um, I think you've stated some of those rules in terms of the graphs you're searching, which are actual graphs whose vertices are the centres of tiles, and you've stated other rules in terms of the tiles. Right? Rule 1 is the former, but rules 2 and 3 are the latter, right? Can you state all the rules in terms of the tiles? I'm pretty sure that your rule 1 is implied by your rule 3.

I am trying to see whether/how your rules depart from those on the wiki. First, isn't your "diamond rule" the same as the thing you noted on Feb 4th with the white dotted line? I think it goes like this:

- define a pair of tiles as "edge-neighbours" if they share an edge
- define a pair of tiles as "vertex-neighbours" if they share a single vertex (so, not an edge)
- define "fattening" to be the required curving of an edge when a tile has an edge-neighbour and a vertex-neighbour that are the same colour
- define a pair of vertices of a tile to be "rigid" if there is a colour meeting the tile at both of them (either as a vertex-neighbour or as an edge-neighbour)

Then:

- a tile cannot have a neighbour (of either type) that is the same colour as itself (you don't list this as a rule but I think it is implicit)

- two tiles that are edge-neighbours cannot both have vertex-neighbours that fatten the shared edge. (This is your rule 2)

- if a tile has two rigid pairs of vertices, AB and CD, with A,B,C,D all distinct, then they cannot appear in the order ABCD or ABDC working clockwise around the tile. (This is your rule 3 and the wiki rule 4. It also implies your rule 1, i.e. that a tile can have at most one edge-neighbour of a given colour)

- the graph of rigid EDs must be embeddable as a planar unit-distance graph. Thus, for example, there must not be vertices A,B,C,D,E in which all six EDs {A,B}<->{C,D,E} are rigid. (This is a generalisation of both your rule 4 and the wiki rule 3)

I can't easily see how the wiki rules encompass your rule 2, but we were certainly using it when I wrote those rules so it may just be an omission.

[Tom Sirgedas]

My rules are in terms of tiles, but I think I wrote rule #1 very awkwardly, sorry! In code, my tiling is stored as a list of vertices, where each vertex has a list of neighboring vertices/polygons(tiles) in clockwise order, so tiles adjacent to a vertex are "neighbors". So rule #1 is "polygons of the same color can't share a vertex".

- define "fattening" to be the required curving of an edge when a tile has an edge-neighbour and a vertex-neighbour that are the same colour

This rule doesn't cover this situation, where the green/blue edge is curved. The green tiles make two rigid edges in *different* tiles (red&yellow).

Though, reading my code, I might not detect this either (I'll check it out later).

- the graph of rigid EDs

What's ED? edge?

This graph only has 5 rigid edges that easily coexist, but the diamond rule applies here.

[aub...@sens.org]

OK, several things...

0) The mixing of terminology is a huge issue here - let's fix it. The actual tiling is a planar graph, i.e. it consists of a partitioning of (some part of) the plane into regions which you've been calling polygons but which are more traditionally called tiles. Tiles have:

- vertices where betweeen 3 and 6 tiles meet;
- edges, which are lines that join two consecutive vertices; and
- diagonals, which are pairs of vertices that are not consecutive and are not joined by lines.
- colours.

("ED" meant "edge or diagonal" - part of the problem is that you're using "edge" to mean that.)

So, let us define the corresponding terminology for your graphs. These graphs are also planar, but in this case colours are not assigned to tiles but to vertices. So let us just make up new words. Let the regions be called "tyles", and the vertices be called "vyrtices", and the edges and diagonals be called "ydges" and "dyagonals". Then a fattened edge corresponds to a directed ydge (as denoted by your white arrows).

So now...

1) You say "In code, my tiling is stored as a list of vertices, where each vertex has a list of neighboring vertices/polygons(tiles) in clockwise order, so tiles adjacent to a vertex are "neighbors"." Wait, you're mixing terminology again. What are "tiles adjacent to a vertex"? I think what you're saying is that the graph on the left needs to have a proper colouring, i.e. one in which no two vyrtices of the same colour are joined by an ydge. In my terminology, that is the same as saying that no two tiles of the same colour can be edge-neighbours. But that's not what you say you're saying - you say "So rule #1 is "polygons of the same color can't share a vertex"." But the graph on the left doesn't create that prohibition at all - it only says tiles of the same colour can't share an edge. The way to say "polygons of the same color can't share a vertex" in terms of the graph on the left is to say that the vyrtices of a tyle must all be different colours. Right?

2) Hm. My rule, stated in tyle terms, says that an ydge is directed from vyrtex A to vyrtex B if A is a vyrtex of a tyle that has another vyrtex C (where {A,C} is a dyagonal, not an ydge) that's the same colour as vyrtex B. But you're right, it is possible for two tiles (not tyles) to be juxtaposed like the green tiles. (Though you haven't actually drawn the corresponding white arrow!) I think I can state this as a new rule in tyle terms: if there are two vyrtices A1 and A2 that are both joined by directed ydges to vyrtex B, and those directednesses are both caused by the same vyrtex C, then the ydge shared by the two tyles that have dyagonals {A1,C} and {A2,C} must also be directed, towards C. But hm, that's pretty horrid...

3) You say "This graph only has 5 rigid edges that easily coexist, but the diamond rule applies here." I must be misunderstanding which are the rigid EDs (edges or diagonals) here. You originally said "vertex a has 4 neighbor vertices, including rigid edges to opposite neighbors b, c." So AB and AC are ridid. If A's other neighbours are called D and E, then I thought you were saying that the problem that gives rise to the diagonal is that BD, BE, CD and CE cannot all be rigid, which makes six rigid EDs. Which are the five that you're saying coexist but still invoke the rule?

[t.sir...@techsmith.com]

[Test]  (my new messages are getting deleted)

[Tom Sirgedas]

0) Okay. 

Yeah, I've been saying "polygon instead of "tile"

Yeah, I've been saying "rigid edge" instead of "rigid ED"

For the rules, so far I've been talking about tile graphs and not tyle graphs. I added the "graph on the left" as an aid, but I hadn't referred to it.

1) 

> "In code, my tiling is stored as a list of vertices, where each vertex has a list of neighboring vertices/polygons(tiles) in clockwise order, so tiles adjacent to a vertex are "neighbors"."

Yeah, 

vertex 5 "neighbors": vertex 6, (red tile), vertex 1, (purple tile), vertex 4, (null tile)

vertex 0 "neighbors": vertex 1, (red tile), vertex 2, (yellow tile), vertex 3, (blue tile)

so, vertex 0 "neighbors" a red tile, yellow tile, blue tile, which are unique colors, which satisfies rule #1

2)

> Though you haven't actually drawn the corresponding white arrow!

Oh yeah, you're right. The simulator drew that image and doesn't detect this case.

My code is in terms of tile graphs, not tyle graphs!

3)

Yeah, there are five rigid EDs drawn with a black line: AB, AC, and then the white, red, and orange tiles have a rigid ED (bottom-left to top-right diagonal in each).

The dotted lines BD, BE, CD and CE are all length <= 1. AB and AC are length 1, so one of the dotted line "paths" from B to C must be length > 2, which is a contradiction. (This is the "diamond rule"). It's not important if BD, BE, CD and CE are rigid or not, just that they're length <= 1.

[Tom Sirgedas]

Ugh, the search got to 5-tile graph #57 out of 153 in 2 hours or so, but it's still searching it after 18 hours. So, my progress estimation isn't accurate at all! I'm not sure how to get accurate progress.

Also, my searcher doesn't detect this fattened edge! I'll add that.

[aub...@sens.org]

1,2: OK got it.

3) Ah, I hadn't seen that there were black lines obscured by the dotted green arrows! But I still don't get it. Your definition of the rule was "If vertex a has 4 neighbors vertices, it cannot have rigid edges to two opposite vertices.". I agree with that, but it arises precisely from my rule about embeddability (so in this case that AB,AC and the four dotted-green diagonals cannot all be rigid, but any five of those six can). I don't understand what you're denoting by putting the particular rigid diagonals that you have. It still looks to me to be just like your Feb 4th construction. There, the central vetex only has three neighbouring vertices, not four, but the configuration of the (six) rigid edges is exactly the same (three black lines, two ditted black lines, one dotted whiteline). Right?

[Tom Sirgedas]

3)

(so in this case that AB,AC and the four dotted-green diagonals cannot all be rigid, but any five of those six can)

My claim is that if AB and AC are rigid, then the graph is already not embeddable, regardless of whether any other ED is rigid or not. Drawing in the dotted diagonals is just part of explaining my proof.

[aub...@sens.org]

On the undetected fattened edge, ah yes - that's almost the same as my rule 2 from a couple of possts ago that arose from your earlier figure:

"If there are two vyrtices A1 and A2 that are both joined by directed ydges to vyrtex B, and those directednesses are both caused by the same vyrtex C, then the ydge shared by the two tyles that have dyagonals {A1,C} and {A2,C} must also be directed, towards C."

... but not quite! This new figure has white, blue and orange tiles where the earier one just had a green tile. In real life this could arise if the yellow and green tiles aere orange and white respectively. So here goes with another formulation, and it will be a generalisation of your rule 2, which you stated as "edges can't curve away from more than one vertex" and I stated in tile terms as "two tiles that are edge-neighbours cannot both have vertex-neighbours that fatten the shared edge". The new formulation is "we cannot have the case where four rigid DEs form a diamond ABCD, and AC is an edge, and the colours that make AB and BC rigid are the colour of the tile on the D side of AC, and the colours that make AD and CD rigid are the colour of the tile on the B side of AC". Aha, in fact we can even generalise it to incorporate the embeddability rule, or at least the case of it that we're also discussing. We can just delete the "AC is an edge" stipulation and instead say at the end of the rule "and these two colours are different".

[Tom Sirgedas]

In real life this could arise if the yellow and green tiles aere orange and white respectively

I'm confused about this. Are you trying to force the two rigid EDs in the diagram? They are already rigid because of the blue tiles.

[aub...@sens.org]

"My claim is that if AB and AC are rigid, then the graph is already not embeddable, regardless of whether any other ED is rigid or not. Drawing in the dotted diagonals is just part of explaining my proof."

OK then we are indeed saying the same thing - at most three of the dotted green diagonals can be rigid if AB and AC are.

But the discussion was worth it - it has got us to a single rule that covers all four of the cases you've identified recently, as well as the original rule "two tiles that are edge-neighbours cannot both have vertex-neighbours that fatten the shared edge". But there is a further case... so here's my final formulation:

If four rigid EDs form a rhombus ABCD, and the colours that make AB,BC,CD,AD rigid are X,X,Y,Y respectively (X different from Y), then there must be at least two paths (along edges) between A and C, inside ABCD, that do not share any vertex (other than A and C themselves).

Here, of course, a colour that makes an ED {P,Q} rigid is simply a colour shared by a tile incident at P and a tile incident at Q. The geometric interpretation of the formulation is that there is a region inside ABCD that is less than 1 from both B and D and hence cannot overlap a tile coloured X or Y.

[aub...@sens.org]

Ah, of course, yes - ignore me. But still, this case is covered by my latest formulation: the blue/orange edge must be fat because of blue, so it had better not also need to be fat because of orange.

[aub...@sens.org]

""he search got to 5-tile graph #57 out of 153 in 2 hours or so, but it's still searching it after 18 hours. So, my progress estimation isn't accurate at all! I'm not sure how to get accurate progress."

Woah, no, that's exciting! It surely means that that particular 5-tile graph can be extended a lot. Are you still printing when the search backtracks to 12 tiles? Are you also printing the greatest number of tiles reached?

[Tom Sirgedas]

Yeah, well, I'm printing the greatest number of vertices enclosed, which is similar. Also saving images and 'tyle graph' files so I can play with them in the simulator. Yes, also printing when the search backtracks to 12 tiles (which will produce just over 1 million lines of output in the end).

Also for every 100,000 tiling graphs, it prints a histogram of how many graphs had n tiles. Here's the latest histogram (57 graphs with 5 polygons, so far):
{0,0,1,2,10,57,545,2261,5276,11714,29801,85637,244943,364127,326617,302298,371452,515770,589419,536681,488484,555209,665359,745104,827596,885097,999409,1371985,1913679,1806137,1558181,1612387,1641588,1356113,934373,618682,376505,296267,228321,137287,105246,65005,44012,27205,15413,12343,14527,15679,16476,9520,11244,31380,20664,6912}

(Loading up almost any large graph in the simulator quickly makes it clear that it's not actually embeddable.)

[aub...@sens.org]

Bah, I just saw a flaw in my rule. Trying again:

If four rigid EDs form a rhombus ABCD, and the colours that make AB,BC,CD,AD rigid are X,X,Y,Y respectively (X different from Y), and an X-coloured tile and a Y-coloured tile lie (wholly or partly) inside ABCD, those two tiles cannot meet inside ABCD.

(They can meet at A or at C (or even at both), and indeed outside ABCD if they do not both also extend all the way to B and D, but consideration of the interior of ABCD gives us what we need.)

[Tom Sirgedas]

and the colours that make AB,BC,CD,AD rigid are X,X,Y,Y respectively

I'll have to think about your single rule to really understand it, but one nitpick is that a single ED can be rigid because of multiple colors.

[aub...@sens.org]

Ha yes fair enough, so I should instead say "and tAB,BC,CD,AD are made rigid by colours X,X,Y,Y respectively".

[aub...@sens.org]

"(Loading up almost any large graph in the simulator quickly makes it clear that it's not actually embeddable.)"

I'm hoping that such graphs always fail because of breaking my new rule!

[aub...@sens.org]

OK, after a brief interlude I now have an almost-equivalent (and, I think, sufficient) alternative formulation that is much simpler and also (I expect) far easier to incorporate into your code. To wit:

If a tile P of colour X and a tile Q of colour Y share a vertex A, and if P has another vertex B such that AB is rigid because of colour Y, and Q has another vertex C such that AC is rigid because of colour X, then P and Q cannot meet at any other vertex D, other than in the exceptional case where BD and CD are both also rigid.

No rhombi, no inside and outside, no embeddability :-)

[aub...@sens.org]

Gah no, that "exceptional case" throws the baby out with the bathwater - it should say "where BD and CD are both also rigid, and P and Q are not consecutive tiles at either A or D" (i.e., they don't share an edge.)

[Tom Sirgedas]

I added a rule for fattened edges, which turns out to be super useful, but it's flawed:

[Flawed fatten rule]

* Tile T has an edge E, with vertices A and B

* Tile U is another tile, with the same color as T

* If A and B both have a rigid edge to vertices a and b (respectively) on U, then E is fattened away from b

* Each edge can be fattened away from one vertex only

This makes sense when a=b, right?

When a!=b, it's more complicated, but ABba could be a rectangle (no fattening).

Anyways, the search including this rule completed in 10 hours

final _NodeCtForPolySize = {0,0,1,4,24,147,1235,1860,5305,13674,23802,37962,67095,97084,182632,397816,711723,791494,743647,716423,740096,768681,871668,802350,591030,442996,340449,286418,210193,111534,78440,59276,69970,63625,52013,42710,46346,36253,30502,36182,14933,15802,13788,12296,15632,29946,49673,11846,8603,6190,6763,4896,1398,794,2436,288,306,212,312,300,592,3050,935,456,257,400,330,176,183,40,37,15,8}

Elapsed Time = 36423.5

With this "biggest" graph:

Here's the very symmetrical center portion of the graph in the simulator:

Just thought this might be interesting. I'll have to study your notes!

[aub...@sens.org]

Hm, interesting. It's a bit more flawed than that though - basically, only the portion at (for instance) the B end of AB is fattened, up to the point on AB that is 1 away from b. So in principle AB could have its right-hand half fattened upwards from b but its left-hand half fattened downwards from a similarly-positioned vertex above. And you can't tell how to weaken the rule to make it safe, because that depends on the ultimate geometry.

I think my rule gives you the safe version of this. In my rule there is no mention of fattening - we just rely on the fact that any two EDs that share a vertex will form two angles (one at least 108 degrees, one at most 180), and that in either case if there is an edge coming out of the shared vertex that is shared by the tiles that have the EDs, and if the colours of those tiles are (among) the ones that make each other's EDs rigid, we are screwed: if the angle is less than 180 then at least one of the tiles is too close to its own colour, and if it is at least 180 then at least one of the tiles is too big.

[Tom Sirgedas]

Well, I fixed it by making a=b in the rule, but it's not nearly as powerful. Still, there are only 1.0 million 12-polygon tilings instead of 1.7 million, (and .067 million with the flawed rule). I started a full search, but I know it won't finish in 10 hours again.

I'll try to understand/apply your rules

[Tom Sirgedas]

https://dustingmixon.wordpress.com/2018/05/29/polymath16-sixth-thread-wrestling-with-infinite-graphs/#comment-4690

In my rule there is no mention of fattening - we just rely on the fact that any two EDs that share a vertex will form two angles (one at least 108 degrees, one at most 180), and that in either case if there is an edge coming out of the shared vertex that is shared by the tiles that have the EDs, and if the colours of those tiles are (among) the ones that make each other's EDs rigid, we are screwed: if the angle is less than 180 then at least one of the tiles is too close to its own colour, and if it is at least 180 then at least one of the tiles is too big.

So similar (the same?) as Gibbs' rule? 

[aub...@sens.org]

Not exactly Gibbs's rule, no - stronger. Gibbs's rule is the same as my original rule "two tiles that are edge-neighbours cannot both have vertex-neighbours that fatten the shared edge". What I'm doing with the current version of the rule is I'm essentially looking at the ends of the shared edge separately. (I didn't mean 108 above, of course, I meant 180.) Doing the ends separately is what allows the rule to subsume the other gnarly cases that you've identified, like diamonds and so on (and more).

[Tom Sirgedas]

If a tile P of colour X and a tile Q of colour Y share a vertex A, and if P has another vertex B such that AB is rigid because of colour Y, and Q has another vertex C such that AC is rigid because of colour X, then P and Q cannot meet at any other vertex D, other than in the exceptional case ##EDIT## where BD and CD are both also rigid, and P and Q are not consecutive tiles at either A or D (i.e., they don't share an edge.)

This rule doesn't seem to apply here because "P has another vertex B" isn't true ??

[aub...@sens.org]

Hm, interesting. You have your C and D switched relative to the notation in my rule. Let me assume that is fixed below, i.e. C is the bottom vertex.

Then, OK, yeah, this is a more complicated case. In my rule, the prohibition is when there is exactly one edge meeting A between the EDs AB and AC; in that setup, the edge must be an edge of P and also an edge of Q. What you're showing is that if there are two or more edges meeting A between AB and AC, there is still a problem if colours X and Y meet at any one of those edges. So yes, that's a valid generalisation of my rule. Moreover, I think we can actually say it more simply than before:

If two rigid EDs, AB and AC, share a vertex A, no edge incident at vertex A can involve a colour that rigidifies AB and a colour that rigidifies AC.

Cute!

[Tom Sirgedas]

In code, the graph is stored as a list of vertices, where each vertex knows its edges & tiles in clockwise order.

From this, you can know the perimeter of the graph, the vertices of each polygon, which EDs are rigid, which polygon (if any) touching vertex #27 is red. Also, which edges are curved.

My currently implemented curved edge rule: 

- Tile P has edge AB

- Tile Q is another tile with the same color

- Tile Q has vertex C

- If AC and BC are rigid EDs, then the tile edge (AB) is curved centered on C 

If you try to curve an edge, and it's already curved with a different center, the graph is invalid.

I'm not sure how to implement your (earlier?) version, but I'll give it some more thought.

[aub...@sens.org]

plus of course A, B and C cannot all be vertices of the same tile :-)

[aub...@sens.org]

Right, that's true, and it's Gibbs's rule, but it doesn't cover most of the gnarly cases we've been discussing. Here's my rule using notation and wording as close as I can get to yours above:

- Tile P has edge AB

- Tile Q is another tile with the same color as P

- Tile Q has vertex C

- Tile R has vertices A and C (AC can be either an edge or a diagonal)

- Then AC is rigid and the A end of AB is curved centred on C

- A graph is invalid if an edge is curved AT THE SAME END centred on more than one vertex.

Note that I'm not enforcing anything about BC - there doesn't need to be a tile with vertices B and C, so BC could be greater than 1.

[aub...@sens.org]

Actually the last line should say:

- A graph is invalid if an edge is curved at the same end in respect of both the colours than meet at that edge

Is that doable with your code?