Reminding myself about hypergraphs and tiling

Today I have other things to attend to, but I wanted to spend a few minutes to capture the internal stuff that’s been happening in my head as I think about the questions I raised in the previous two episodes of this arc.

You’ll recall from yesterday’s summary that I’m exploring a nascent mathematical recreation and/or puzzle involving tiling a square lattice with colored dominoes, and then looking at the derived patterns we get from the colored squares on those colored dominoes, in that tiling arrangement. The interesting questions seem to be forming around the reverse path, of course—because that’s the way most interesting questions arise from play. For example, if I want to form a particular pattern of colored squares, does any domino tiling exist that could possibly match it?

Anyway, I realize that one of the chunks of mathematics I’ve picked up from the Math Gang on the street is stuff that a lot of people I encounter don’t seem to know about it. I guess the Math Gang in my neighborhood was pretty hipster, or something, because they were prone to scoff at “mainstream” Graph Theory stuff, and immediately start talking about hypergraphs whenever you started doing anything in combinatorics like this. And I guess I picked that up, and so whenever I start drawing on a napkin or something, a lot of people who have only ever heard Graph Theory on the Math Radio or whatever don’t seem to know what the fuck I’m talking about.

What can I say? I have a tendency to pick up these hipster memes I guess.

Yesterday I actually was sketching on a napkin—though I admit in this case it was an imaginary napkin in Inkscape—and this morning I realized that the little diagrams I make when I doodle about tilings are possibly very different from the ones you’ll draw. So I guess I should drop some background here, before I dig that hole much deeper. Nothing very long or rambling, just an explanation of what the pictures I might use might mean.

hypergraphs and lattice tilings

You’ll recall that I was looking into some very simple conditions, sussing out the “edges” of the interesting part of the problem. So I was comparing domino tilings of squares with I-tromino tilings of the same squares. And I had noticed that sometimes I could tile a region with dominoes and get I-trominoes in the derived pattern, but that there were also some I-tromino tilings I could construct, but which could not be colored with dominoes.

This is me thinking about the “overlaps” of two tiling patterns, so I started sketching some abstract structures on little squares.

Here’s a sketch I made of “empty lattices”:

In the top row you’ll see a little 3x3 square of squares. That’s the region I started thinking about.

To the right of the square, you’ll see a little circles-and-lines graph I drew. This is the graph of adjacent squares in this small region of the lattice, taking into account which squares are next to (in the sense of sharing edges, not sharing corners) other squares. Each square is a node, and each line connecting two nodes represents “neighbor” relations.

That’s the Graph Theory drawing most people would draw of a square lattice.

In the top right is a “hypergraph drawing” of the exact same structure. Every graph is also a hypergraph, so don’t get too spooked by the change. But it looks different because what I’ve done is drawn outlines around every set of squares that could possibly hold a domino. In other words, this is a diagram of all the places, on an empty square region, where I could put a domino. Each oval outline surrounds a pair of cells that would be covered by some domino.

It’s a hypergraph in the sense that each “edge” here is a subset of the whole set. In regular old Graph Theory, an edge is typically defined as a kind of relation or thing that “connects two nodes”. In hypergraphs, the “thing that connects” is represented as a set of nodes. If you squint, and maybe zoom in, you can see that every two nodes connected by an edge in the graph drawing in the middle, are surrounded by a “subset oval” in the hypergraph drawing on the upper right.

Why is this worth doing? I don’t really know, it’s just my habit. But it feels worth doing.

Here’s part of why I think that: Suppose I want to [try to] build a domino tiling of this 3x3 square. I start by placing a domino somewhere, right? If I were coloring it on the squares, I’d just have to remember that on every “move” I can only color two squares, and they have to share an edge with one another, and they can’t be squares I’ve colored previously.

On the graph diagram, we have an extra tool we can use: the edges themselves. Indeed, the presence of edges gives us a new way of viewing a domino tiling: as a perfect matching. I won’t quote the definitions there, because I don’t think they’re salient past this point, but I do notice an interesting turn of phrase:

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

It gathers so much up into that one passage, which feels like it might be better unpacked some other way. The edges are non-adjacent, meaning they can’t share a node. But there isn’t anything “in” a graph representation that explicitly talks about whether two edges are attached to the same node or not. It’s implicit in the structure, sure, but it’s not something you can just ask the objects about. Look at the common representations of graphs as data types, and think about how you’d “ask” an adjacency list whether two edges are adjacent, without also interrogating an incidence matrix. There’s a lot of overhead and transformation, in practice.

Now let’s look at the hypergraph drawing I made. It’s the same structure, but instead of representing it as a bunch of arrays and matrices, I’m going to think about it as a set, with some subsets.

The region contains nine items. Let me call them \(s_1\) through \(s_9\) for now. And the square lattice is a hypergraph that looks something like this:

\[\{\{s_1,s_2\},\{s_2,s_3\},\{s_1,s_4\},\{s_2,s_5\},\dots,\{s_8,s_9\}\}\]

I’m still going to be doing the tiling with the same definitions, and I’ll probably even use graph stuff internally to implement code, but now look what happens to the definition of a perfect matching on a hypergraph (rather than a graph): A perfect matching is a subset of the hyperedges in the original hypergraph, such that the intersection of each pair of edges in the matching is empty, and the union of all the edges with one another is the union of all the edges in the original hypergraph.

Everything is included, but only in one bin.

That feels better somehow. You may wonder why.

In the second row in the diagram, on the right edge, I’ve drawn a similar hypergraph “spaghetti diagram”, but this time the outlines surround collections of squares in rows of three.

This is a “graph” of all the places where an I-tromino can be placed on the 3x3 square region.

You’ll notice that there’s no graph with circles-connected-by-lines to its left. That’s because I have no damned idea how to “draw” a graph representing the relations between the nine positions in the square lattice, and places where I can situate an I-tromino.

But I can draw the hypergraph. I like that.

I can see, having gone from dominoes to I-trominoes this way, that I could also draw an (admittedly horrifying) spaghetti diagram that shows all the places where an L-tromino, or a T-tetromino, or whatever could be placed. I could, arguably, draw a hypergraph for the situation where I want to tile with some mixture of dominoes and monominoes (there would be subsets with one member each), or dominoes and trominoes (it would be all adjacent subsets with two or three elements) and so on.

It might be that by doing so, I’ve pushed the “hard work” of representation back into the setup. That may be. I’m just reporting what my sketches mean.

Because I like to be slightly confident about these things. I also drew the equivalent diagrams for a 4x4 square region. Well, I didn’t draw the hypergraph for a domino tiling, because I got bored. But I drew the graph for a domino tiling, and the hypergraph diagram for an I-tromino tiling.

Tiling dynamics

Then I tried it out a bit. This is a sequence of three steps of an (ill-fated) tiling of a 4x4 square with I-trominoes. On the left is a sequence of three steps of tromino placement. On the right of each step is a hypergraph diagram that shows one way I’ve been thinking about how tiles “claim” squares.

The first tile “claims” three squares, which is why I colored the matching three circles blue. But it also blocks some overlapping hyperedges from being used later. Because each square can only ever fall under one tile, I’ve deleted the hyperedges that “overlap” the claimed one.

In the second row, I place an orange tromino, and do the same sort of culling for all overlapping subsets.

Third row, same thing again.

Now you may notice that I’ve drawn these as blue-and-orange, but to be honest I haven’t started thinking about the ways the domino constraint of two colors on each domino comes into this. I’m just thinking about where dominoes get “claimed”, and how the hypergraph unravels as we move along. But it’s interesting, I have to say, that the rule “no two adjacent tiles can be the same color” can (I think) start to be captured by having the domino tiling on hand, and by simultaneously culling hyperedges from the tromino hypergraph and the domino hypergraph, with some rules about what’s feasible and what’s not.

I don’t know; just an idea.

For example, if I was tiling with arbitrary tetrominoes, I would have started with huge piles of hyperedges—one for every appropropriately-shaped and -sized region of the lattice—but very quickly after placing one tile, I’d have culled out a big chunk of the total possibilities. This process, in other words, feels wide. It feels like the tree of choices for the first position of the first tile will very broad at the beginning, but that it gets trimmed down to very few options quickly.

I mean, look what happens next time. There are three hyperedges left in the bottom step here. It won’t be long until I’ve run out of options.

sketchiness

A lot of programmers I know would probably think this is too much “design”. Some other ones I know would probably have found something on Stack Overflow that “did” what I was “looking for” already. But that’s not the point for me.

The point of the sketching here is to refine a sort of curiosity I’ve experienced about this problem, by poking and playing with the pieces until something with the ineffable “interesting” quality falls out. I don’t honestly want to know how many two-color domino patterns produce two-color tromino patterns, I want to find some kind of Goldilocks point where this moves from curiosity to exploration, exploration to question, and from a question to being a recreational undertaking that other people might find value in.

Drawings are fun, and they can help me muse.

Code is also fun, and it can be a kind of sketch as well. I think it’s time to make some code.