You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Alex Kreitzberg (Aug 27 2025 at 18:57):There is a game with "a notion of composition" that I've been trying to understand with category theory for awhile called "Black's Path Game"
In this game you have three tiles with paths:Square_(02)_12-34.svg.png
Players alternate placing tiles on the board, connecting them to tiles that have already been placed down. The first person to place a tile that connects a path between two edges of the board loses.
There are a ton of variations on this basic idea, a simple one mentioned by the Wikipedia article, generates art by randomly tiling with two of the tiles:
Screenshot_20250827_113740_Chrome.jpg
I'm part of the way through trying to understand operads for modeling circuit diagrams and open dynamical systems. I once considered trying to use operads for modeling these tiles, but after playing with them for a bit decided they were too flexible. Recently while trying to understand "compositionality" I found Baez suggest here this should bring to mind functorial semantics, monoidal functors, and operad algebras.
So I figured maybe I discounted operads to soon. If they capture "n-ary" multiplication maybe they're the right tool for the job. But I'm not sure how to proceed with them if they are the right tool.
What do folks think? As a first impression do operads seem like a good way to model the board state for "Black's Path Game"? Or are there other categorical gadgets that could be more appropriate?
Alex Kreitzberg (Aug 27 2025 at 19:13):The one dimensional version doesn't seem too bad to me, you have the freely generated monoid on two generators (imagine two horizontal paths that either do or don't flip). Then the last person to move, filling the board, loses. So the game is just Nim. So it didn't seem too out of reach to come up with a "two dimensional" multiplication, but I'm not sure.
Alex Kreitzberg (Aug 27 2025 at 21:28):Another idea I've been playing with that I see as connected to this, is I'll imagine a "2D free monoid generated over {x, y, z}"
So one element might be:
y
x y y z x
z x z
And then a homomorphism would replace the generators with elements that can also be composed in this grid aware way. So if I choose which of the above tiles correspond to each generator, the output of the map would be the tile board state. Or I could map to a different tiling game, like Tsuro
Morgan Rogers (he/him) (Aug 28 2025 at 03:44):It seems like "compose" means "place side by side" (along some axis) here. If so, how do you decide where exactly to place the 2D monoid elements you described above? As a simple example, if I take xx and y, even if I decide that the grids have to be connected I have 6 ways to compose these (assuming only relative positions in the grid matter).
An operad would be more obviously applicable if the composition was instead a kind of "substitution", where a tile is replaced with a grid. While it might be possible to argue that such structure is applicable here with some clever grid transformations, it doesn't feel to me like it corresponds to actually playing the games you describe.
Alex Kreitzberg (Aug 28 2025 at 04:07):That reminds me of a nested tic tac toe game concept I've seen people play occasionally (you have to win tic tac toe in a square to win that square.
Anyways thank you, that answer actually really helps me understand operads a lot better, which was a motivating goal for sharing this.
Now that I actually wrote out what I'm trying to play with here maybe it'll help me get more ideas.
I want gluing tiles to be a sort of push out, if their edges match you simply glue them and the paths together. But you can't always "multiply" along one edge - sometimes you need to do two or three, which makes it weirder.
If I let myself place the tiles in a grid, then it's a lot easier, it's just an array of the tiles and null spots, and each tile added, except the first, has at least one neighbor. But I dunno, it seems to me like "2D adjoining" could be a really fun primitive to figure out.
Alex Kreitzberg (Aug 28 2025 at 06:33):Wait, so does my "free monoid" example not make sense then, or is suggesting a borked interpretation?
It being a "free monoid" suggests it should be legal to replace an x with some sub expression right? Because if I'm thinking of this as an algebra, shouldn't that be legal?
Maybe I'm confusing myself by trying to think of it as an algebra, because algebras/languages want to be arbitrarily recursive, but I'm trying to understand tiling paths, which maybe aren't?
John Baez (Aug 28 2025 at 08:34):I don't see how an operad or a 2-category or a double category are fully able to formalize your game - basically, there's too much geometry involved in your game, because you're interested in gluing together squares to form regions in the plane.
If you were only interested in gluing together squares to form larger rectangles, then double category theory would be perfect for your question! You'd then be discussing the free strict double category on one object, one vertical arrow, one horizontal arrow, and three 2-morphisms. (Or maybe more 2-morphisms if we're allowed to rotate your squares.)
If I were you, you would be willing to adjust your focus slightly to make it fit into the subject of double category theory. There's already been work on double categories and tilings, by Robert Dawson.
Alex Kreitzberg (Aug 28 2025 at 16:59):Thank you for mentioning Dawson, his papers look extremely relevant. Especially for the Truchet tilings, the procedurally generated art.
I guess now I know why most painting's canvases are rectangles! /Joke
It's satisfying knowing that stuff like the following "pinwheel" from Dawson's paper, are a nuisance in this abstract setting:
Screenshot_20250828_085920_Chrome.jpg
Another example in the back of my mind are Kolam tiles. I think the rectangle requirement is modest enough, we don't have to rule them out:
They even allow closed tiles, as circles, in the official rules so I can always fill in gaps. That's funny that works.
I guess I'll say one last thing about the game as I change focus.
We imagine starting with one tile, which has four edges for a new tile.
*
* T *
*
Adding a new tile lays down an asterisk on each side without a T or an asterisk, so if we added a tile on the right we'd get
* *
* T T *
* *
I think this can be made into an efficient algorithm for representing a sparse tile "composition". But the algorithms coming to my mind don't seem "categorical". Most of the algorithmic work I can come up with involves juggling properties of elements.
When Bartosz taught me category theory he played up how it was about "composition". This seems like an okay slogan, but not a bullet proof intuition. It gets my head close to the right ideas, but I'm not getting anything for free.
Morgan Rogers (he/him) (Aug 29 2025 at 14:09):If you like, you could see a tile configuration as having four composition surfaces (this is a different, less rectangular way to turn them into a double category). The downside is that this only keeps track of the outer edges, so you can't meaningfully keep track of any operation for plugging holes without some higher-dimensional data.
Alex Kreitzberg (Aug 29 2025 at 15:36):The way you're thinking about that, are you imagining the "left edge" of some configuration is a sort of path, and we can glue this to a "right edge" of a different tile configuration if one path is a sub-path of the other, or do the paths have to be the same? (Or am I missing what you're trying to do? What's a "composition surface"?)
John Baez (Aug 29 2025 at 16:25):If you're going for a double category those paths have to be equal: 2-morphisms compose when the target of one equals the source of the other. So you can't just have one path be merely sub-path of another, unless you're willing to use an extra trick, which this screen is too narrow to contain. It's probably best to start by going along with what's mathematically easy, instead of fighting against it.
By 'composition surface' Morgan surely doesn't mean a 2-dimensional surface. He's saying you can take a tiled region without holes in it and subdivide its boundary into four paths, which (going counterclockwise) you call the 'top', 'left', 'bottom' and 'right' even though they can snake around in quite complicated ways.
At least that's my reading of his remark.
Alex Kreitzberg (Aug 29 2025 at 16:57):Okay, that makes sense. That was my read as well. That is an interesting generalization, but it still doesn't permit adding one tile to a larger configuration, so I was making sure I didn't misunderstand. It's very similar to the rectangle example (though it breaks my rectangular canvas joke!)
Which is fine, I'm just trying to get a feeling for what is and isn't natural. I had a feeling "adding one tile" was a forced fit at the 2-category level, but I wasn't sure. It's cool combining rectangles (and jagged regions) works and is natural, that's news to me.
Category theory seems to "want" to be topological and I'm curious how much I can push back against that. I'll see Lego blocks brought up as a metaphor or analogy occasionally for example, but the metaphor feels forced. The rectangle composition double category makes this analogy seem much less forced.
I guess another angle on this I've thought about some, is the topos of graphs is often explained as the free cocompletions of edges and verticies. In this tiling vein I considered adding squares to that and wondered if I could restrict how the completion process worked by specifying a more restricted category than Set or something.
But that felt like working against the subject, like "degenerate" graphs actually help you do useful stuff.
John Baez (Aug 29 2025 at 17:00):That is an interesting generalization, but it still doesn't permit adding one tile to a larger configuration.
It does if one of the four paths in the larger configuration has just a single edge.
John Baez (Aug 29 2025 at 17:01):I had a feeling "adding one tile" was a forced fit at the 2-category level, but I wasn't sure.
We're talking about double categories now, not 2-categories. At least I didn't notice anyone mentioning 2-categories until you did right now.
Alex Kreitzberg (Aug 29 2025 at 17:21):Sorry, 2-categories and double categories are both in my head as "two dimensional" is this a conflation? That's why I misspoke in any case.
Once you decide the boundary types of your four edges for a given configuration you're stuck with that right? So there is one jagged "visual" arrangement with multiple ways to equip it with four distinct paths? So if your configuration doesn't have any one edge length path, then you can't add a single tile?
Alex Kreitzberg (Aug 29 2025 at 17:50):(I don't want to get in the weeds in these examples, ya'll have given plenty of examples of double categories to think about now, I'll play with them more so I can be more definite and careful with what I say)
John Baez (Aug 29 2025 at 18:06):Sorry, 2-categories and double categories are both in my head as "two dimensional" is this a conflation?
They're both 2-dimensional, but they're different. Double categories are fundamentally about squares, while 2-categories are about bigons.
Once you decide the boundary types of your four edges for a given configuration you're stuck with that right?
Well, you are unless you decide to introduce some math that lets you change your mind about how much of the boundary of your tiling is included in each of the four edges! You may want to work with double categories that have features that let you change your mind.
For example you might want to work with 'symmetric' strict double categories, meaning those where the category of vertical arrows is fundamentally the same as the category of horizontal arrows. At that point maybe you want to use a 2-category, or maybe a 2-category where the 1-morphisms are invertible.
This could become a research project, and as long as you have some good examples and do a good job in formalizing them, you might come up with some nice new math.
Or maybe someone has already done all this. A one-minute search turns up
which probably doesn't solve your problems for you, but does describes some of the extra bells and whistles people have considered for double categories. Some of these are relevant to what we're talking about.
Alex Kreitzberg (Aug 29 2025 at 18:10):That is encouraging, thanks for sharing that context
John Baez (Aug 29 2025 at 18:12):Sure! Brown and Dawson have written a lot of stuff that comes to mind, vaguely, when I think about the issues you're raising. But I forget most of the details.
Morgan Rogers (he/him) (Aug 30 2025 at 09:53):@Alex Kreitzberg have you thought about monoidal categories before? If I have an arrow and an arrow , these aren't composable but I can compose the latter with a similar kind of padding could allow you to add a single tile to a larger configuration in two dimensions, although there are lots of details you would need to figure out.
Alex Kreitzberg (Aug 30 2025 at 10:09):I have but I clearly need to think about them more! In a very vague sense I interpreted Baez's comment as implying I needed to add the analogs of "unitors", "associators", etc to a double category.
I definitely don't have an intuition for what's convenient or possible in this respect. Which in retrospect is why I had the impression one couldn't always add individual tiles.
John Baez (Aug 30 2025 at 13:34):No, that's not what I meant. I meant adding some features to a double category that would help solve your problem: for example, a feature that could change a square with top equal to fg and right side equal to h to a square with top equal to f and right side equal to gh... in a reversible way.
This sort of thing makes the four points where you chop up the boundary of your patch of tiles movable, solving your problem of not being able to add individual tiles.
You were correct that in the double category framework you can't in general add individual tiles to a large patch of tiles without some extra trick like this.
Alex Kreitzberg (Aug 30 2025 at 17:05):Oh! Is that something "connections", from the paper you linked, would make easier or possible?
John Baez (Aug 31 2025 at 09:23):Mainly connections let you turn vertical arrows into horizontal ones and vice versa, which is just part of what you're demanding. Connections may help you a bit, but it may be faster for you to just make up the desired structure from scratch. I mainly recommended connections to you so you can see how people introduce extra structures of this general sort on double categories.
I believe the structure you want is the ability to change a square with top equal to fg and right side equal to h to a square with top equal to f and right side equal to gh... in a reversible way... and similarly with the words "bottom" and "left", "left" and "top", or "right" and "bottom" replacing "top" and "right".
If I were you (or technically: if you were me) I'd start by:
1) clearly specifying some examples of what I'm trying to axiomatize,
2) writing down the axioms that capture what's going on in these examples.
The resulting axioms may look a bit clunky, but in consultation with practicing category theorists, double category theorists, and 2-category theorists you may be able to make them look nicer.
In fact, come to think of it, I might start by writing down axioms that don't mention double categories at all, because the insistence that your region have a boundary subdivided into four parts (arbitrarily called top, right, botttom and left), fundamental to double category theory, is not so important to you.
Alex Kreitzberg (Aug 31 2025 at 14:03):Okay thank you, you've provided plenty of stuff to get me started, I'll try and axiomatize some of these examples.
I think the main motivation for framing everything in category theory, is these tiles have paths on them. So I'm hoping after everything is in its proper place I'll have functors, or some structure preserving map, taking the tile configurations to path configurations.