Tag: complete combination coloring

Can 3½ Colors Suffice?

~ munizao ~ 2 Comments

The loan seemed like an incredible break. You got back on top of your mortgage, even had enough to put your oldest into a decent private school. And all they asked you to do was solve puzzles.

The puzzles were actually fun, for a while. But they got harder. And when you couldn’t solve them fast enough, the threats started. And that’s how you ended up here, wherever here is, kidnapped, bruised and bloody, on a floor covered with grit and sharp angular tesserae.

There’s a note. Another puzzle. In order to leave, you’re going to have to pick out some of the tesserae and use them to tile a shape. And no two tiles of the same color may touch. Pretty basic.

And then you realize that it’s too dark for you to be sure what the colors of the tiles are.

There’s a real problem with constraining the number of colors in a colored tiling as an additional challenge: our options just aren’t very granular. Literally everything (on a plane, which sometimes we aren’t!) can be 4-colored, a small proportion of things can be 3-colored, and almost nothing that isn’t highly contrived can be 2-colored. If only there were some options in between!

To our relief, and our hero’s consternation, there can be. Observe that we can make a graph with colors as nodes and edges connecting colors that are permitted to touch. For an n-coloring, this is simply the complete graph Kn. But there might be other graphs (we’ll call them color graphs) that produce interesting results. For example, consider this one:

We might consider one color graph to have greater “coloring power” than another if it can be used to color a proper superset of the graphs that the second graph can color. This graph turns out to have a coloring power intermediate between those of K2 and K3.

Here’s a tiling of the 2–5-iamonds colored according to the above graph. (Kadon sells these shapes as its Mini-Iamond Ring puzzle.)

There’s a reason I showed the color graph as a pentagram, even though you could rearrange the nodes into a pentagon and get rid of the crossings. Let’s take a simplified model of color where allowed instances lie on a circle of hues. From the perspective of our hero with color vision reduced by darkness, nearby colors around the circle might be too similar to safely place next to each other.

As we raise or lower the level of light in this dungeon, the minimum distance between colors that can be allowed to be adjacent in a coloring will change. We can make arcs along the circle that correspond to hues that can be legally adjusted to the hue at the center of the arc. Finally, we connect the nodes for the arcs that don’t overlap to make a color graph.

For arc lengths (as a proportion to the circumference of the circle) that are fractions of the form 1/n, we get the complete graph, Kn. But for other rational arc lengths, we get different graphs. Here’s the one for an arc length of 2/5:

What’s nice here is that the reciprocal of the arc length describes the coloring power of the corresponding graph. For the above graph, the reciprocal is 2½, and this does in fact mean that its coloring power is stronger than 2-coloring and weaker than 3-coloring. This type of coloring is called a “circular coloring“, and it extends our usual definition of chromatic numbers into “circular chromatic numbers”. The graphs that are formed by this process are “circular complete graphs”.

Here’s the color graph for a circular chromatic number of 7/2:

This one can also be useful for coloring polyform tilings. Consider this tiling of the 21 5-rects:

It is not 3-colorable, as we can see by starting at the starred pieces and following the colors that are forced until we come to the checkered yellow pieces. But it is “7/2 colorable”!

One nice aspect of this coloring scheme is that we can get balanced colorings of sets that have a multiple of seven pieces. There are undoubtedly balanced 3-colorable solutions to the above tiling problem however, so this isn’t necessarily the “best” coloring possible here. A solution to the following problem might have a good claim to the title though: Problem #57: Find a tiling of the above figure with the 5-rects that has a 3-coloring and a 7/2-coloring such that all 21 color combinations occur exactly once.

Now, you may be grumbling at this point about my title being inaccurate and click-baity, because there are clearly seven different colors here, not three and a half. And certainly, there are for you and I, who have plenty of light to see them by. But for the poor soul toiling with ambiguously colored pieces in my basement some entirely hypothetical dungeon, it really does feel like having somewhere between three and four colors available.

This is just the beginning of a rabbit-hole that can go a lot deeper than this blog post can contain. A curious person might wonder: what about other color graphs? Playing around a bit shows that a lot of different color graphs have the same “coloring power”. For example, any even cycle graph can color exactly the same graphs as K2. If you number the nodes around the cycle, even colors may only be adjacent to odd colors, (and odds to evens) and the even and odd sets of colors can color exactly the graphs that the 2 nodes of K2 can color.

In more standard mathematical terms, what the last paragraph says is that even cycle graphs are homomorphic to K2. Generally, homomorphically equivalent color graphs have the same coloring power. Every graph is homomorphically equivalent to a so called “core”, a minimal graph that captures the information we need for coloring. (In the previous example, K2 was the core.) So we can restrict ourselves to just cores when we’re looking for interesting color graphs.

The circular complete graphs we looked at are cores. Other cores exist, but they don’t fit nicely into the ordering that the circular complete graphs do, and so don’t give us meaningful chromatic numbers. But they could still be fun things to apply to polyform colorings. (Or even problems of actual mathematical import. In 2018, the lower bound of the Chromatic Number of the Plane was improved to 5. Perhaps a unit distance graph with a circular chromatic number of 11/2 could be found, effectively improving the lower bound for an extended version of the problem.)

And that’s all I have for now, although I expect that this won’t be the last time I visit the subject of colorings. Until next time, be well, and beware loan sharks bearing puzzles.

Complete combination colorings on the torus

~ munizao ~ Leave a comment

I posted previously about my talk at Gathering for Gardner 12 on colorings of pentomino tilings. One unexpected consequence of that is that my work has now been cited in a very prestigious… um… coloring book. Alex Bellos and Edmund Harriss previously collaborated on Patterns of the Universe, a mathematical coloring book for adults, and were looking for material for the sequel. They were attending G4G12, and saw my talk, and thought that they had found some. They wanted to use something like the strict complete combination 3,4-coloring of the pentomino tiling that I showed, but for the purpose of a coloring book page, they needed something with more shapes to color. Could I come up with such?

It seemed to me that the problem called for a pentomino tiling of a torus, which they could use as a wallpaper-like pattern, repeated as many times as they needed. The choice of the particular torus to use is a matter of taste, but I thought it would be nice to maximize the minimum distance between two images of the same point. (I haven’t proven that I succeeded, but it’s close.) In coding the solver for this, I used a shortcut: instead of directly checking whether a given tiling had a coloring of the correct type, I checked whether each pentomino bordered exactly six others. This turns out to be a necessary condition, but not a sufficient one, so I manually checked a few such tilings until I found one that worked. This is the pattern that appears, in user-colorable form, in Visions of The Universe by Bellos and Harriss.

The hexiamonds were the other obvious set of 12 polyforms to try to tile with this coloring scheme. Here, there is one torus with maximal symmetry. Amazingly, my solver found just two tilings where every piece bordered 6 others, of which exactly one had the right coloring properties. Recall that the solution for the pentominoes on the 6×10 rectangle was also unique. It seems incredible to me that this problem type has yielded two instances that were so finely balanced as to be solvable, but only by the barest of margins.

The Happiest and Saddest Tilings

~ munizao ~ Leave a comment

(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I was looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

  1. Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
  2. Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
  3. Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:

5-omino-6x10-happiest

This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

Total Balanced
4-colorable, non-strict 2339 2338
4-colorable, strict 2339 2320
3-colorable, non-strict 1022 697
3-colorable, strict 94 53

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:

5-omino-6x10-saddest

Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.