Posts Tagged ‘research’

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

Elementary properties of the Tutte polynomial at (1, 0)

June 25, 2009

The Tutte polynomial of a graph G is a widely-studied and very useful graph invariant. It’s a polynomial in two variables x, y that extends, among other things, the chromatic and flow polynomials of a graph. In a certain (well-defined) sense, it’s actually the most general object that obeys what’s called the deletion-contraction recurrence, which I’ll talk about in a bit.  One particular specialization of the Tutte polynomial of interest is its value at x = 1, y = 0. This has at least two useful combinatorial interpretations; it counts the number of acyclic orientations of the edges of G with a fixed unique source, or, equivalently, it counts what are called the “maximal parking functions” of G. As it happens, this second interpretation is the one I’m most interested in, but the first is more useful for this discussion, so we’ll only consider it here. Throughout this post, we’ll let M(G) = T_G(1,0) be the Tutte polynomial evaluated at (1, 0). (more…)