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.

Generalized LYM inequalities

I’ve been thinking about this problem ever since an old post of Qiaochu’s first raised the question, and I’ve been frustrated by my inability to solve it. I could post it on MO, but I sort of already have, and anyway it raises questions which are too ill-formed right now to be right for MO. So anyway, here we go:

A lot of problems in extremal combinatorics correspond to finding large antichains in partially ordered sets. (By the way, all posets in this post will be assumed to have a least element.) Classically speaking, Dilworth’s theorem completely characterizes the size of antichains in posets; however, this is often tricky to apply, since it’s not always clear whether a partition into chains is minimal. In addition, it’s sometimes the case (particularly with infinite posets) that there are infinitely long antichains, but a nontrivial bound should still be attainable. The way to get by both of these obstacles is to assign weights to the elements of the poset, and rather than looking for large antichains, we look for antichains with high total weight.

The classical example of this solves the problem of finding the largest antichain in the lattice of subsets of a given finite set — the content of Sperner’s theorem.

In which I am late to the MaBloWriMo party

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.)