So this question’s been bugging me ever since I first thought it up, and I figured (in the spirit of MaBloWriMo, which by now is pretty much dead on this blog) that I’d ask about it here — I need to give Math Overflow a break.
The question concerns adjoint functors, which I don’t understand half as well as I’d like, but enjoy thinking about anyway. One of the (many!) motivating examples that adjoint functors generalize is the common “free/forgetful” dichotomy. For instance, there’s a functor from the category of groups (say) to the category of sets, which is defined by simply “forgetting” the group structure and giving back the underlying set. This functor doesn’t have an inverse, of course; that would make the two categories isomorphic, which is way too much to expect. Nor does it have an “inverse up to natural transformation.” That would make the categories equivalent, which is almost as good as isomorphism. But it does have the next-best thing after that: a functor in the opposite direction which comes with a natural isomorphism on some hom-sets. This is the free functor, that assigns to each set the free group on that set. These functors are called adjoint functors.
Okay, so if you click through to the Wikipedia article, you’ll see that the definition of adjoint functors isn’t totally symmetric. There’s a handedness to them, which we can see by noticing that free and forgetful functors don’t act the same way. In particular, we say that free functors are left adjoint to forgetful functors, or alternatively that forgetful functors are right adjoint to free functors.
So here’s the connection to graph theory. To every directed graph we can associate an underlying undirected graph, by just “forgetting” the directions. If you work out the details, this turns out to be a functor; we might suspect that it’s a forgetful functor. Then it’s natural to ask if there’s a free functor associated to it.
If you think about it some more, the following suggests itself: Given an undirected graph G, form a digraph by replacing every edge with a pair of directed edges, one in each direction. This seems to nicely preserve the properties of the original graph (at least up to isomorphism), and “feels” like an adjoint to the functor from digraphs to graphs.
If you work out all the details, you find out that these two functors do actually form an adjoint pair. But, twist! They don’t have the expected handedness! For more details, see this blog post. But if you don’t want to click through, the point is that the “forgetful” functor is actually left adjoint to the “free” one, not right adjoint as we’d expect in a truly free/forgetful pair.
The blog post to which I linked actually provides a pretty good justification as to how we can view this pair in the other direction. Specifically, we can think of undirected graphs as directed graphs with the extra structure of invertibility, or bidirectionalness. (Actually, this might remind you of the relationship between categories and groupoids — I suspect that there’s a lot to that analogy, and it’s one of the reasons I’d really like to learn more (n-)category theory.) But in particular this gives a way to think of the “forgetful” functor as “free.” My question is, is there a natural way to think of the “free” functor as “forgetful,” other than in abstract-nonsense terms?