More on graphs and digraphs

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?


Tags: , ,

4 Responses to “More on graphs and digraphs”

  1. Qiaochu Yuan Says:

    Think about what happens when there are multiple undirected edges between two vertices. If you split these up into directed edges going both ways, you forget which ones were paired up. In other words, the structure being forgotten is the inverse relationship.

  2. Gil Kalai Says:

    Dear Harrison, Interesting! Is thinking “cetegorically” has some graph-theoretic applications?

    • Harrison Says:

      It’s a good question, and the short answer is I don’t know — but I’m posting about it in the hopes that it’ll inspire someone to find out!

      A more concrete answer, though, would be to say that it doesn’t seem to — yet. I like to think that the “forgetfulness” of the functor from graphs to digraphs is related that linear-algebraic methods run into. The reasoning behind this is as follows: the standard proofs of things like the Matrix-Tree theorem start by arbitrarily orienting a graph, and then using linear algebra on the oriented digraph’s adjacency matrix to count spanning trees. If we’re forgetting some structure in the first part, then no matter how much linear algebra we do we’ll never be able to fully recover the graph. I’m not sure how to make this rigorous, but I’ve found it a fruitful line of thought.

      There’s another, bigger issue here, though, related to the digraph-category and graph-groupoid analogy. You can associate to each digraph sort of the “free category” on it, which is called a quiver, and you can associate to a graph a “free groupoid.” In the latter case, this turns out to be essentially the fundamental groupoid of the graph considered as a 1-complex. The problem is, up to isomorphism this fails to distinguish between connected graphs with the same number of vertices and edges! So you need to consider groupoids that are isomorphic to be different if you want to see nontrivial results, which means you need higher category theory, which I sadly don’t know nearly enough about.

      • colinwytan Says:

        I think a good question ask is what is the adjoint from Groupoids to Graphs to your “free groupoid” construction? If you take up to isomorphism, you don’t get much left. A skeletal groupoid forgets to a series of vertices.

        What this really means is that the “free groupoid” construction doesn’t preserve the combinatorial information you want from your graph. However, it does very well preserve the connectedness information of your graph. (Which is reflected in its adjoint).

        The other thing is that there is too low dimensions here. (in the sense of geometry or higher categories) There are only two kinds of 1-manifolds, circle of line. Graphs with at most 2 edges at each vertex, viewed as a 1-complex, realizes as a 1-manifold. That you speak of “number of vertices and edges” which determine the fundamental groupoid is your combinatorial way of putting this geometry.

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: