Category theory and combinatorics

This post is about two very different areas of mathematics that I’m pretty interested in (although I know a lot more about one of them…) and the relationships between them. It’s well-known that category theory grew out of investigations in algebra and topology, and that its insights are today still most useful in those and closely related subjects. (Algebraic geometry, I’m looking at you.) In particular, the famous “slum of topology” epithet notwithstanding, combinatorics is pretty far-removed from both the above areas, and indeed, I don’t know of an introductory textbook in combinatorics that gives category theory a second (or first!) glance.

And why should it? Doubtless many have tried, but no one’s (as far as I know) managed to give combinatorics a Grothendieck- or MacLane-type makeover. On one level, this makes sense; combinatorics is a huge area that encompasses problems that look completely different. It can almost be described as the trash-heap of mathematics; combinatorics is the study of problems that don’t really fit in anywhere else. To abstract from such a huge generality would seem sort of… onanistic, “abstraction for abstraction’s sake.” But of course this doesn’t mean that category theory has no place in combinatorics!

In this post, I plan to discuss two (and a half) different applications of category theory to combinatorics. One is reasonably well-known; one is silly and (as far as I know) original, but hopefully gives some insight into something else that’s interested me ever since Qiaochu mentioned it.

Combinatorial species

The theory of combinatorial species is a far-reaching application of the language of category theory to enumerative combinatorics, and in particular generatingfunctionology. The starting point for the theory is the following: Let’s consider structures of some sort on a finite set S — say, labeled trees. Then, in most cases of interest, the number of these structures depends only on the size of S, and on nothing else at all. (In the example of labeled trees, it’s a classic theorem of Cayley that there are n^{n-2} labeled trees on n vertices.) Furthermore, given a labeled tree on S_1 with n vertices, and a bijection S_1 \rightarrow S_2, it is a simple matter to construct an isomorphic labeled tree on S_2. Since two sets are isomorphic iff they have the same number of elements, we have a description of the structure as a functor

F: FB \rightarrow FB

from the category FB of finite sets with bijections as morphisms to itself. This functor is called a species of structures.

The functor evaluated at a bijection \sigma between sets is called the transport of F-structures along \sigma. We can also define isomorphism of structures in the natural way; i.e., two structures on U, V respectively are isomorphic iff there is a morphism between them of the form F[\sigma] for some isomorphism \sigma: U \rightarrow V.

Much of the power of this approach lies in its great generality; any algorithm to construct the structures on a set can be considered as a species. Furthermore, it is possible to write functional (functorial?) equations for species in a succinct way. Let’s see how.

We want to define addition, multiplication, and composition of F-structures in a manner analogous to those operations on generating functions. Fortunately, it’s been known how to do this for a while! Addition of two species, F and G, corresponds to the set-theoretical disjoint union. The product of two species F, G is defined as an ordered pair s = (f, g) where

  • f is an F-structure on U_1 \subset U;
  • g is a G-structure on U_2 \subset U;
  • U_1, U_2 is a disjoint partition of U.

The reason that this is well-known is that this is exactly how multiplication and addition act on generating functions. With this in mind, we can also immediately see that addition and multiplication are associative, commutative, and multiplication distributes over addition — in other words, species can be given the structure of a commutative semiring. We can also consider the operations of substitution, F \circ G or F(G). and differentiation, F' — and these have natural definitions as well.

So now we can start writing functional equations for species. Let’s consider the species of rooted trees: we can describe it recursively, by choosing a single point as the root and describing the tree as that distinguished point plus a set of smaller rooted trees. Denoting the species of rooted trees by A (from the French arborescence), it turns out that we can write this recursion functionally. Let’s also denote by X the singleton species, which takes a singleton set S to \{S\} and any other set to the null set, and by E the species of sets, which takes any set to the singleton set \{S\}. Then we can write the above recursive definition of rooted trees in the form

A = X \cdot E(A).

So you probably have enough information on the theory to get through Todd and Vishal’s post dealing with species, in which the connection with generating functions is explained more clearly and some good references are given. This section of the post is already way longer than I intended, so let  me just briefly say a couple things about the notion of virtual species.

I mentioned earlier that the class of species can be given the structure of a commutative semiring. It turns out that, just as in the case of the most famous commutative semiring N, we can extend this to a commutative ring by way of virtual species. One of the most interesting things about virtual species is that they turn out to have all sorts of unexpected useful properties. For example, letting E be the species of sets as above, it turns out that in the ring of virtual species there is a unique \Gamma satisfying

F = E(\Gamma)

for any F with F(0) = 1.

Category theory and graph theory

Since graph theory is the area of mathematics that, despite my best efforts, I keep getting pulled back into, I thought I’d talk briefly about the few applications of category theory to it. First we need to define morphisms for graphs; fortunately, the notion of a graph homomorphism works just fine. So let Graph be the category of graphs with graph homomorphisms as morphisms. There are a couple of nice things about this category; first, any graph G is k-colorable if and only if there’s a morphism \phi: G \rightarrow K_k. Morphisms also preserve connectedness of graphs, and never increase odd girth. But probably the most interesting thing is the tensor product in this category.

A famous conjecture of Hedetniemi asserts that, letting \times be the tensor product of graphs,

\chi(G \times H) = min(\chi(G), \chi(H)).

This conjecture is still open when the chromatic numbers of G, H are at least 5, but half of it follows immediately from basic category theory; letting k be the RHS of the above equation and supposing WLOG that \chi(G) = k, we have

G \times H \rightarrow G \rightarrow K_k,

and \chi(G \times H) \leq min(\chi(G), \chi(H)). While this is not hard to prove directly, without resorting to category theory, it lacks the clarity that the categorical viewpoint provides.

Another application of category theory to graphs is even more interesting, albeit not nearly as rigorous. To correctly describe it, we need to slightly tweak the standard category of groups. Let gGrp be the category of groups along with generating sets for the group, where morphisms are the group homomorphisms that induce functions from the first generating set into the second.

Then there is a functor F: gGrp \rightarrow Graph, which is described by the Cayley graph construction. Essentially, this construction says that for any group G, there is a graph which the group acts on in the same way that the group acts on itself. Another way of looking at it, which gives a better idea of where the name comes from, is that the graph describes a quotient of S_{|G|}, the symmetric group on |G| vertices.

But the functorial properties of the Cayley graph construction are what interest us here, and they seem to have some interesting consequences. In particular, it seems that many important graph products actually correspond to group products. For instance, the Cayley graph of G \times H is the cartesian product of the Cayley graphs of G and H. Even more interesting: Alon-Lubotsky-Wigderson have shown that, for certain sets of generators, the celebrated zig-zag product of Cayley graphs is essentially equivalent to the semidirect product of the underlying groups. Are there other relations between graph products and group products?

Edit: Another application of category theory which I didn’t feel capable of discussing was the homological definition of the Jones polynomial — not strictly graph theory, of course, (or for that matter category theory) but closely related. Lo and behold, as I check the revised cross-listings in the combinatorics section of the Front, I come across this. There are some typos and (from a brief glance) the exposition could be better, but it might be worth checking out.

Pointed sets and the field with one element

There’s an interesting philosophy, arising initially from Lie theory and q-analogues, that many combinatorial structures can be viewed as algebraic structures over this nebulous “field with one element.” Developing (for instance) algebraic geometry over this non-existent field seems to be an exciting area of study, and one that’ll hopefully lead to many new insights. In this section, though, I’m going to talk about something more specific — namely, the philosophy that pointed sets are “really” vector spaces over F_{un}. I want to convince you to the best of my ability that, from a category-theoretic standpoint, this at least is a reasonable thing to be happening; that pSet, the category of pointed sets with basepoint-preserving functions as morphisms, “wants to be” KVect, the category of vector spaces over a field K, for some degenerate K.

So the first thing I’ll note to this effect is that pSet has lots of properties characteristic of “algebraic” categories like the category of abelian groups or the category of R-modules, but that aren’t shared by most other “combinatorial” categories like Set; for example, pSet has zero morphisms and therefore kernels and cokernels. The reason for this is essentially as follows: the categories with zero morphisms are exactly those enriched over pSet. An analogy to Ab can be drawn here, since KVect, Ab, and RMod are all enriched over Ab. Really, this analogy can be stretched even further by the simple observation that there is a forgetful functor from Ab \rightarrow pSet (that takes 0 to the basepoint).

So why is pSet like KVect and not Ab? Well, part of the reason intuitively might be that although both these categories are locally small, the first two have “more” morphisms. (Combinatorially, of course, we can count the sizes of the hom-classes, and get q-analogues over finite fields.) Another reason is that in both pSet and KVect, we have a notion of dimension (cardinality in the first case), and isomorphisms are exactly those morphisms that preserve dimension. In the end, though, I don’t know enough category theory to fully explain why pSet “should be” F_{un}Vect.

Nor can I explain via category theory exactly what it is stopping pSet from being actually equivalent to KVect for some field K. Of course, there are easy discrepancies; for instance, pSet is not even preadditive (unless I’m very hugely mistaken). But none of these seem to get to the heart of why pSet is different. So, readers, can we come up with a more compelling categorical justification, and have some F_{un} in the process?


Tags: , , , , ,

6 Responses to “Category theory and combinatorics”

  1. Qiaochu Yuan Says:

    The categorical ideas behind the field with one element were discussed in some detail at the n-category cafe.

    But cool, I’ve never seen that definition of a coloring before. Does the categorical perspective make it any easier to prove that the chromatic polynomial is a polynomial? Also, you forgot to mention that a graph is a category! Then the definition of a graph homomorphism can be read off from the definition of a functor, if I’m not mistaken.

    Anyway, another mysterious application of category theory to combinatorics is Mobius inversion in categories; this is an idea that generalizes Mobius inversion in posets, and it appears to have deep connections to topology via the Euler characteristic as well. Tom Leinster has a series of papers on the subject.

  2. Todd Trimble Says:

    The category of pointed sets is a somewhat interesting creature. It can be seen as the category of sets where the morphisms are partial functions (consider what basepoint-preserving functions look like when you remove the basepoints!).

    I think Segal’s famous category \Gamma, used in the study of infinite loop spaces, is the category opposite to finite pointed sets. But I digress.

    In what ways does pSet differ from K-Vect? You observed that pSet isn’t even pre-additive; an intrinsic way of capturing that is that the canonical morphism from a coproduct to a product,

    A + B \to A \times B,

    isn’t an isomorphism as it is in K-Vect. (By “canonical morphism”, I mean the one whose restriction to the summand A is defined by the pair of maps

    \langle id_A, 0\rangle: A \to A \times B

    and whose restriction to B is defined similarly; here ‘0’ is the zero morphism. In other words, we are taking crucial advantage here of the presence of a zero object.) It’s not too hard to see that if coproducts are canonically isomorphic to products in this way, then it’s possible to define an addition law on the hom-sets, in such a way that the hom-sets become commutative monoids, and the category becomes pre-additive in the sense of being enriched in the category of commutative monoids.

    To say it a bit more nicely: what does coproducts = products buy you? It means that morphisms

    A_1 + \ldots + A_m \to B_1 + \ldots + B_n

    can be described as matrices of morphisms, and composed as such.

    What’s another way in which pSet differs from K-Vect? First, as you point out, there’s a lot in common. I would add that in pSet,

    — Every morphism factors as an epi followed by a mono, in an essentially unique way.
    — Every mono in pSet is the kernel of its cokernel.
    — Every epi in pSet is the cokernel of its kernel.
    — The pullback of an epi along any morphism is an epi.
    — The pushout of a mono along any morphism is a mono.

    So pSet has some great exactness properties shared with any abelian category. But here’s a weird structural feature of pSet as a symmetric monoidal closed category (where the tensor product is smash product \wedge), and that’s that

    — There’s a natural transformation \delta: X \to X \wedge X which is coassociative and cocommutative, namely the usual diagonal map.

    This could be F_{un} to keep in mind.

    There is however no counit! That is, if the 2-element pointed set plays the role of a 1-dimensional space \mathbf{1} over \mathbb{F}_{un}, then there is no natural map X \to \mathbf{1} to play the role of a counit (of a hypothetical coalgebra structure).

    In fact, maps X \to \mathbf{1} are in bijective correspondence with subobjects of X in pSet. Thus \mathbf{1} is what category theorists call a “subobject classifier”. This would be another significant difference between pSet and K-Vect.

  3. Todd Trimble Says:

    Not meaning to hijack this, but there are maybe a couple things to add about “coalgebra” naturally appearing in pSet whereas it doesn’t in K-Vect.

    As I mentioned above, every object X in pSet (every pointed set) naturally carries a comultiplication \delta: X \to X \wedge X. The word “naturally” is meant in the technical sense of category category. It means that every morphism of pointed sets f: X \to Y preserves the multiplication.

    I also said there was no counit e: X \mathbf{1}, and then clarified there was no natural map to play the role of a counit, and that is again correct under the technical meaning of natural. But there is a counit e: X \to \mathbf{1} which is natural in a non-categorical sense, of having a uniform description for all X. It is just the map to the 2-element pointed set \mathbf{1} which takes every non-basepoint of X to the non-basepoint of \mathbf{1}. Thus every pointed set carries a comonoid (or coalgebra) structure, but not all maps of pointed sets preserve the comonoid structure on the nose; they do preserve comultiplication.

    But there’s an enriched point of view on pointed sets; namely, the set of maps \hom(X, Y) can be given a natural partial ordering. Namely, define f \leq g to mean that if f(x) is not the basepoint, then f(x) = g(x). (This may become more intuitive if you think of the category of pointed sets as equivalent to the category of sets and partial functions, where f \leq g just means that f(x) = g(x) whenever the left side is defined.) Hence the category of pointed sets is enriched in the category of partially ordered sets. Then, while a morphism of pointed sets f: X \to Y may not preserve the counit structure in the sense of an exact equation e_Y \circ f = e_X, we “come close” in the sense that e_Y \circ f \leq e_X.

    Another thing that could be observed is that the posets hom(X, Y) have binary meets (given f, g: X \to Y, f \wedge g sends x \in X to f(x) = g(x) wherever f, g agree, and otherwise maps x to the basepoint of Y).

    So there is in fact a kind of goofy commutative and associative addition structure on the hom-sets \hom(X, Y), given by f + g = f \wedge g. This brings pSet just a tad closer to K-Vect, doesn’t it? 🙂 The only thing stopping the hom-sets from being commutative monoids is the general lack of an identity element for this addition operation, at least if Y has more than two elements.

  4. Steven Sam Says:

    For more work exploiting the relationship between categories and graphs, there is the PCMI lecture notes by Kozlov:

    The idea that a k-coloring of G is just a morphism G \to K_k is nice, but at first glance doesn’t seem to yield much new information. One idea is to build structures which tell us whether such morphisms exist or not and which depend functorially on the graphs in question, and this is roughly what Kozlov and his collaborator Babson do.

  5. harrison Says:

    Todd: Don’t worry about “hijacking” the thread — if I’m giving you a lot to say and/or think about, it just means that I’m doing my job right :). (I’m still trying to process everything you said, which might mean that I’m doing my job too well!)

    Steven: Nice, I haven’t seen that paper. It is a pity that the coloring-homomorphism equivalence hasn’t been as useful as might be hoped, but there are a few nice things that come of it. For instance, it’s probably the quickest way to show that the graph homomorphism problem is NP-complete…

  6. Non-update « Portrait of the Mathematician Says:

    […] other news: my post on category theory and combinatorics has gotten a good deal of (what I consider to be) positive feedback, which of course I’m very […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: