Since it’s not yet on Thomas’ blog, and I need to use the data, I thought I’d make it publicly available. All credit goes to Thomas Sauvaget for the sequence-to-HTML code, and to Polymath for the sequence itself. (Probably someone specific discovered it, but I don’t know who.) Tables below the fold.

## Archive for the ‘research’ Category

### Full HAP tables for the second 1124 sequence

January 12, 2010### Where do graphs live?

December 5, 2009This 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 on graphs and digraphs

November 16, 2009So 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.

### In which I am late to the MaBloWriMo party

November 4, 2009Hey, 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.) (more…)