Hey, guys. Been a while, hasn’t it? Sorry for not blogging more; I blame having to “learn stuff” in “classes.” It’s very silly.

I didn’t find out about Charles Siegel’s MaBloWriMo until almost November 2 (and then there were more of the aforementioned “classes”), but it sounded cool, and gave me a reason to get back to blogging. So to make up for the late start, I’m going to try to write at least 30 total posts for the month of November, which should hopefully average in the range of 1000 words in length.

So, again because of school, I’m supposed to be spending November writing a final (expository) paper for introductory algebraic geometry. This means that I’ll probably be posting bits and pieces of drafts of said paper for MaBloWriMo, which means that there’ll be some unifying theme to some of the posts. The bad news is, I don’t actually know what it is yet, since I haven’t figured out my final paper topic, since I’ve been procrastinating horribly.

So instead I’ll talk about my usual craziness; over the next few days, I’ll ask the question: Is there a higher category theory for graphs? What is it?

So if you’re a combinatorialist, the easy way to think about categories (at least at first) is as special sorts of directed graphs with some extra structure (specifically, a way to glue together edges to make new edges.) To make this rigorous, we can think of every (small) category as having an “underlying digraph” where we just draw a directed edge from X to Y if there’s a morphism .

It turns out that this construction’s functorial: it gives us a forgetful functor from the category of small categories to the category of digraphs. (A morphism between digraphs, by the way, is exactly what it “should” be; it’s a function between the vertex sets that respects the adjacency structure.)Now the nice thing about forgetful functors is that they tend to be right adjoints to some free functor — although this isn’t always the case, as we’ll discuss later on. However, the underlying digraph is no exception to this rule of thumb, and indeed there’s a category — a free category — associated to every digraph.

Here’s how it’s built: given a digraph , the objects of our category are the elements of . The morphisms can’t just be the edges — there’s no composition rule! However, if we just choose the “freest possible” composition rule, then we might get what we’re looking for. So we’ll let a morphism just be a directed walk between two (not necessarily distinct) vertices. And, lo and behold, everything works out nicely, and we have our free category.

(Incidentally, this guy is usually called a quiver, and has connections to lots of cool stuff in physics and representation theory. But I don’t know how the quiver-stuff relates to what I want to talk about, so I won’t discuss it further, other than to point out that it’s a “quiver” because it’s a bunch of arrows.)

Okay, so this free category. By generalized abstract nonsense, it turns out that this free category doesn’t lose us information about our digraph. Specifically, functors between these free categories exactly correspond to digraph morphisms, and so we can think of digraphs as special kinds of small categories. And so graph theory is part of the big grand family of category theory, and everyone’s happy, and we can all go on our way.

Except… there’s a problem. Graph theorists who do graph theory for graph theory’s sake tend not to work with digraphs, but with undirected graphs. And you might think that this isn’t a problem — after all, an undirected graph is just a directed graph with some forgotten structure! — but if you try to make it go through, you start running into weird and kind of disturbing issues. And lots of graph theorists only worry about simple graphs, so we have to start thinking about endomorphisms, and we haven’t even touched on trees, dense graphs, sparse graphs, random graphs, planar graphs, perfect graphs, graph colorings, graph labellings…

So that is coming tomorrow.

Tags: graph theory, math.CO, math.CT, wild speculation

November 4, 2009 at 22:50 |

It seems to me that when some people say “graph” they are really referring to some degenerate case of one underlying concept, and when some other people say “graph” they are really referring to some degenerate case of a different underlying concept. Unfortunately I don’t have a good idea of what those notions might be. But I’ve had this feeling for some time now.