Posts Tagged ‘math.CT’

Where do graphs live?

December 5, 2009

This post came out of some thoughts I posted (anonymously, but mostly because I didn’t feel like registering) over at nLab. I don’t think it’s a secret that I’m heavily interested in the relationships between category theory and combinatorics, and more generally the ways in which we can use “structured” algebraic objects and “continuous” topological objects to gain information about the unstructured discrete objects in combinatorics. That said, the folks over at the nLab work on some crazy abstract stuff, which seems about as far away as possible from the day-to-day realities of graph theory or set systems. And maybe it is — but I hope it’s not, and as far as I’m concerned, this is a windmill that deserves to be tilted at. (After all, it might be a giant.)

So as my jumping-off point, I’ll take my observation from last time that the relationship between graphs and digraphs is analogous to the one between groupoids and categories. I briefly mentioned something called a quiver, which can be thought of as any of the following:

  • Another name for a digraph, which categorical people use when they don’t want us combinatorialists stomping in and getting the floor all muddy;
  • A “free category,” i.e., one in which there are no nontrivial relations between composition of morphisms;
  • An algebraic object whose representations we want to consider; it’s worth thinking of this way mostly because of the “freeness,” although if you try to define it more formally you’ll probably end up with the previous definition;
  • What you get when you take (part of) a category and forget all the rules for how morphisms compose.

This last point is the most interesting one for our purposes, since it’s clearly an algebraic object but isn’t as restrictive as “free category,” and thus has a chance of capturing the unstructured behavior of the combinatorial zoo. But it’s tricky to turn this into a rigorous definition that actually includes everything we want to be a quiver… so we’ll just use “quiver” as a fancy name for “digraph.” However, there’s an important philosophical lesson to be learned from the final point, so I’ll set it off:

Philosophical lesson. The edges of a quiver shouldn’t carry any information except for the vertices they are incident to; more generally, paths in a quiver shouldn’t carry any information except for their sequence of vertices.

(more…)

Advertisements

More on graphs and digraphs

November 16, 2009

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.

(more…)

In which I am late to the MaBloWriMo party

November 4, 2009

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 X \rightarrow Y.

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.) (more…)

Category theory and combinatorics

June 30, 2009

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. (more…)