Diffusing domino tilings: questions from the audience

The other day I showed a “quick” sketch of a dynamic domino tiling of a square. I had mentioned in passing that I think the dynamics I had implemented—where arbitrary pairs of “snug” dominoes (which form a square next to one another) are rotated 90° in each step—was sufficient to achieve every possible domino tiling of a given region. At least for squares, and possibly for some (or many?) other convex regions that could be tiled.

Here’s the “snug domino rotation move” I implemented in my Quil sketch. You’ll recall that in the simulation, in every step I first pick a random domino, and look at all the adjacent dominoes. If there are any, then one of the first domino’s “snug” neighbors—meaning one with which it shares a long edge—is picked at random, and the two are moved like this, depending on whether they’re in a horizontal or vertical orientation:

I thought, based on some stuff I’d skimmed, this was enough to reach any possible domino tiling of a region. This is still exploratory for me, recall. This is “Learning in Public”.

---

John Barnett, in a back-channel discussion, wondered whether these rotation dynamics would ever get you to, for example, a herringbone tiling of a region. Finite or infinite.

This is a good question, since it certainly doesn’t feel as if a herringbone, or even a large-scale running bond (aka “stretcher” or “standard brick wall”) pattern is possible. Since in infinite tilings of those types, there’s no pair of “snug” dominoes anywhere to pivot. But I don’t know if we can tile a rectangle with either of those.

It’s also a good question because I’ve fostered a similar concern for finite regions that, for example, may have little one-cell-wide sections. If I can tile such a thing once, but that tiling has no “snug pairs” of dominoes forming a square anywhere, then it seems it would be hard to obtain that tiling, and also to escape it, if the only “move” is impossible. For example, these:

That’s one region of a square lattice (a 5x3 rectangular region, with a 3x1 hole in it), tiled in the two possible ways with dominoes. Admittedly, the region I’ve chosen has some topological differences from the solid rectangles and squares I’ve been talking about so far, having a hole and all, and that may make a difference. And when I squint and imagine it with the hole in the middle removed (by shifting it, for example, to a 6x2 rectangle), then all of a sudden we actually do have “snug pairs”, so that (lacking the hole) all possible domino tilings may be reached by rotation moves. But the presence of a simple counter-example opens the prospect that there could be more subtle rules in play. Maybe certain one-cell-wide bridges, for example, would be a problem.

So I’ve gone to some basic references to see what they can tell me.

The first hit I found just now is a preprint that I realize I’d actually bookmarked years ago—and which to be honest might have started my interest in domino tiling dynamics, especially in the long-range effects of one region on a very distant part of the same tiling. It’s this hefty-but-readable little number titled “Local statistics for random domino tilings of the Aztec diamond”. In that piece, it’s mentioned in passing that the rotation move of what I’m calling two “snug” dominoes is sufficient to reach all tile patterns in an Aztec diamond. By reference to the original 1991 paper which proved that very point.

The rotation move paper is this one. Here’s a line from the introduction, which seems particularly noteworthy at the moment: “It will be shown that any domino-tiling of an Aztec diamond can be reached from any other by a sequence of such moves[….]”

Now these papers, and indeed a fair bit of the relatively lively literature of domino tiling combinatorics and dynamics, focus on the Aztec diamond region, as such. Let’s work up to that from where I started.

So squares, huh? We know what a square region of a square lattice is. Here, I’m talking about square (and also rectangular) regions that can be tiled completely with dominoes. So implicit in that is the constraint, ab initio, that—since every domino sits on top of exactly two adjacent cells—any finite region that can be tiled (of any shape) will contain an even number of cells. If there are \(2N\) cells in the region, then we can hope to tile it with \(N\) dominoes.

But that feels necessary, but not sufficient. The region I’m thinking of also wants to be connected. That is, looking only at the sort of “north”, “south”, “east” and “west” Von Neumann neighbors, it must also be true that any cell in the region can be walked to from any other cell, by at least one path, without jumping any open spaces or diagonal corner-to-corner fake-ass adjacencies. So the “region” must also, itself, be a polyomino. I guess? There’s surely a less-concise way to define a connected region, but we have already been talking about polyominoes, and they’re defined as being “composed of squares connected edge-to-edge”, so for you and me, this will suffice. And given that we are tiling a polyomino-shaped region with dominoes, and given that the region contains \(2N\) cells, then to me it feels like there’s a slightly better chance to tile the region with dominoes.

But given that a polyomino can be domino-tiled (can I verb that?), it doesn’t follow that it will necessarily have enough (or any) “snug” pairs of dominoes. So we’re still not to sufficiency. Hmmm.

It seems to be true that any rectangular polyomino with \(2N\) cells can be tiled with dominoes, and that if it can be tiled with dominoes then there inevitably will be, somewhere in the rectangle, a “snug pair”. I’m not going to try to prove this, but it seems to involve the lack of holes, as in the holey polyomino I showed above. As long as the edges of a rectangular region are straight—which, you have to admit, is kinda the definition—then we can tile it with dominoes, placed all in the same orientation (layers or stacks), as long as at least one dimension of the rectangle is even. Oh, and because there are \(2N\) cells in the region, at least one dimension must be even. “Boom”, as they say among the Math Gangs: I just went and proved it accidentally.

And it also seems to be true, by pretty much the same argument, for any Aztec diamond. Here are two regions that are kinda Aztec-diamond-ish, but note that by definition only the one on the right is in fact an Aztec diamond. The one on the left, with its single horizontal “equator” row, doesn’t count. It’s interesting because, as you can see, I am able to tile it with dominoes, but there are no “snug” pairs anywhere to be seen.

As a consequence of having no “snug” pairs in the stretcher brickwork arrangement I’ve used in the left region, it turns out that I can’t change this tiling into any others by that single move. Ahh…. but how many “others” are there?

None. That’s the one tiling that’s admissible for this region.

If that’s not clear, shrink the diagram down to something more like this one:

There aren’t any other tilings (with dominoes) because (somehow) of those single squares sticking out at the “equator” row. That word “somehow” is interesting, and it will come up again later, it feels like.

Contrast this with the proper, two-equator-row Aztec diamond region, which I have conveniently animated because it was fun, below:

If you’ve been reading from the top, this has probably been diffusing things around for a while. If you want to see it from an initial state of relative color-organization, reload the page.

Unlike the narrow-equator non-Aztec diamond above, there are many tilings of this one with dominoes. I start here with all-the-dominoes-are-horizontal, and you can see (if you squint and watch for a while) that in some sense the “snug” pairs “spread” out into the top and bottom corners of the diamond. But slowly. Indeed, it’s interesting to watch the top and bottom corners stay, for long long times relative to the center of the diamond, more or less untouched. Meanwhile, the “east” and “west” poles of the diamond quickly “melt” and “re-freeze” in stretcher pattern (rotated 90°), “locking in” an overlapping tiling at the corners themselves.

This is not only interesting to watch, it’s the reason so many smart folks find the Aztec diamond so interesting in the first place. While it’s true, as with the regular old rectangle, that every possible domino tiling can be reached from every other one, by rotation moves, it is not true that over a series of rotation moves every such tiling is likely. For example, it’s remarkable, if you watch a few times, how consistently the poles lock into a stretcher pattern, and how changeable the central core of the diamond is.

It’s interesting enough that it has a name. The “frozen” corners of the diamond form an “Arctic circle” around the diffusive core. It’s why this particular pattern is such a big deal, and there’s a lively literature (some of which is reviewed, and illustrated prettily, in this 2013 slide deck from Filippo Colomo and his talk at this workshop). Something “about the edges” is capable of propagating, through a cascade of constraints, inward for a certain distance, and affect the number of locally permitted tiling patterns.

To paraphrase: It seems that while every tiling pattern can be reached by a series of rotation moves of “snug” pairs, in most of the possible Aztec diamond tilings, “snug” pairs will only occur near the middle. There could be a “snug” pair at any position on the very edge of a diagram, but such edge-located pairs are extremely rare, compared to the frozen stretcher tilings we see near the corners and along most of the edge.

Isn’t that weird? Why is that so weird?

Well, compare with the rectangle, huh? The rectangle isn’t showing off. The rectangle is just kind of diffusing away, bubbling like a boiling pot. But the Aztec diamond, “because of the stair-step edges”, is qualitatively different.

Interesting.

So for John’s question about whether a herringbone (or even just an infinite stretcher pattern) is reachable from just rotation moves of “snug” pairs of dominoes… well, it seems like it depends. Say we have an infinite lattice; then unless it is everywhere-herringbone or everywhere-stretcher, then it seems as though somewhere there will be a snug pair, and the whole thing can unravel from there. And since it can unravel, then by reversing the order of moves, it can be constructed as well. But it does feel as though you can’t construct (or break) an infinite tiling of stretcher/herringbone dominoes.

I think. I don’t know.

But if it’s true, then given the proofs nodded towards above, and as long as somewhere there is a snug pair, rotation moves of snug pairs are enough to reach every possible tiling that is not a global herringbone or stretcher.

How about the other direction? Well, there’s something interesting about a herringbone tiling (and, I suspect, the regular stretcher tiling) that is related to the one-row Aztec diamond thing. You can’t tile a square with herringbone dominoes. Stuff sticks out all over the edges. Here’s a 6x6 square I’ve tried to herringbone:

If I was going to try to describe the subjective feeling of building this picture by hand, I’d say it was something like “wherever I tried to tidy an edge, a lone block would poke out somewhere else.” The edge effects, again. But somehow, here, the edge is “reaching” all the way across.

Very interesting. All I’m able to say for now is this: if

1. there are \(2N\) cells in the region, and
2. it’s a polyomino, and
3. it hasn’t got any holes, and
4. if there are no one-cell-wide sections (internal bridges, or edge blocks), and
5. if there is even one domino tiling of that region that has two “snug” dominoes…

then a series of rotation moves will get you to any possible tiling. But I’m still not sure whether #5 follows from the first four, or not. I don’t know if there are any domino-tileable regions, lacking both one-cell edge bumps and snug pairs.

As I said, John has asked a good question. Good questions create more good questions.

Why I care

Well, the first section of this arc sketched a series of questions about tilings with colored dominoes. Specifically, whether blue-and-orange domino tilings of regions that can be domino-tiled could be arranged into “any” pattern of blue and orange polyominoes. I already knew that the answer was “no”, but the follow-on question is of course “which ones, then?”

I’m taking a pretty atypical approach here, with these animated little diagrams and stuff, that I like to call “looking to see.” I’m happy to have analytical closed-form expressions to stare at, especially somebody else has typeset them, and thrown in a bit of English-language motivational exposition here and there. But to be honest I get a bit more out of writing code and discovering the points where the Mangle resists my assumptions first hand.

Suspicion that my question is ill-formed isn’t a worry for me, as it would be if I were a big-S Scholar. It’s the point of the exercise. Whenever the thing I’m making—in this case, the algorithms by which I draw pictures and animations, and the animation dynamics themselves, and the narrative I build around the animations, and the responses I get from preliminary readers, and even my damned computer’s insistence that for certain sizes of domino tiling animations the laptop fan will be running and I will burn your CPU from the inside—resists me, it’s a message for me. I’m willing to treat the Thing Made as proxy of the world, including the social world of the audience that includes John. It’s an agent, acting, resisting on behalf of the network of all kinds of other agents it represents.

When I notice, I have a chance to accommodate that resistance. Redirect my designs, revise my understanding of not only what I “hypothesized” (to use an old-fashioned bullshit word from the inagile past) and—probably most crucial—reconsider the next most valuable thing to do. “Resistance”, in this Manglish sense, is how value is realized. If I had merely picked up front some “valuable” thing to study, maybe with an eye to teaching you a lesson about best practices and helping you with your professional skills, and then behind the scenes before I even set to writing I’d just imagined what was best and then implemented that?

How fucking boring would that be? Super fucking boring. It’d be like a cooking show where the chef doesn’t fuck up the recipe. Who would watch that? That’s just pornography.

Most published academic papers map very well to pornography. The people who appear in them are impossible idealizations, and they are constantly interesting and remarkably creative, and nobody ever makes any mistakes. Things are done in a modest amount of time, and there’s nothing really to clean up afterwards. For the adventurous, there’s even a “Future Work” section, like Hey that was fun! What shall we do next?

See? Porn.

---

I’m here for the mistakes and the mess.

I’ve learned a few things about making animations of domino tiles. I’ve noticed, with John’s question, a lot more about what can and cannot be captured by this “simple” rotation move. Square tilings, which were sufficient to make me believe the representation worked, weren’t enough to capture the things John had asked about (since rectangles aren’t brickable). Only by revising my simulation and representation to take into account a more arbitrary region could I look into these things the literature threw up in response, these Aztec diamonds.

Next time, because of a question Ron Jeffries asked, I’ll have to do some more rewriting. Because the “resistance” my code is expressing, right now, is that I didn’t actually write the code I thought I had written. I unconsciously cut some corners, and undermined the representational model I was so proud of having uncovered in my sketches.

This is all a different sort of conversation from the one we imagine academic-style research publications represent. This is the stuff that happens “behind the scenes”, and it’s me acting as though I am literally carrying on a conversation with stuff. Code and citations, correspondents and insights. All that stuff happens, I suspect (and whether the participants acknowledge it or not), in “regular science and engineering”. But it gets erased, hidden away, masked.

But more practically: I care about these Aztec diamond things, and the unusual long-range effects of edges of various kinds on the tilings we can make far away in a region, because my motivating question here involves tilings. I originally came at this from an existence proof sort of direction: Can you build a colored domino tiling that “draws a picture” in a given region, for any picture? Early napkin-back sketches pointed out that no, you couldn’t. So my accommodating maneuver is then to say

1. When can you, and when can you not?
2. Can an algorithm notice when you can and cannot, given a target picture?

That last one is particularly motivating, and feels as if it’s crystallizing into a self-contained “project” sized blob. What would it mean “show a tiling” to an algorithm (it would be an argument to a function?), and for that algorithm to “determine” that it could or could not be built by tiling two-colored dominoes?

It might be a good place to start if it counted the cells of the two colors in the target pattern, and “check” whether they were even. Because we’re asking the picture to be made from dominoes with one orange and one blue block on each one (and, for now, no others).

It might be good to see that the region can be tiled with dominoes at all. That might be slightly different from the sub-task above.

From my initial sketches, it looks as if certain larger polyomino tiles—like a 3x3 square, for example—cannot possibly be made from two-colored dominoes. So it might be smart for a checker to “look for those” disqualifying tiles.

And then there’s a little pile of more stuff, which I haven’t quite gotten around to writing about:

Does every (plain) domino tiling of a region permit every two-colored derived tiling of the same region?

Are there derived tilings that are more common than others, in the sense that they will be easier to make, because more tilings are possible? Look at the Aztec diamond thing above; there are just fewer arrangements with snug blocks at the edges.

And the big resistance-and-accommodation, which I’m happy to embrace if it comes along. If it turns out that tiling with two-colored dominoes is boring, we can start to talk about “relaxations”. More colors, more polyomino tiles, and—as I start to produce real derived drawings and have a chance to look to see—better-abstracted descriptions of what I mean by “derived tilings”.

Shortly maybe we’ll see.

Next time: Ron’s question

He said he’d “like to see the ‘set-theoretic’ steps to get neighbors”. As I mentioned above, I had those steps in my head as I started writing my code, but in fact I slipped up quite a bit as I implemented it, and fell back quite a bit on the old habit of using a notional two-dimensional square lattice. So I’ll have to do some rewrites and revisions to tidy things up. Then I think I’ll be able to talk about domino tilings of arbitrary graphs, polyomino tilings of lattices, and so forth.