Where do graphs live?

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.

Probably the above isn’t too controversial; sure, people work with representations of quivers, in which we attach to each edge a linear map, but this doesn’t come with the quiver to start with. Similarly, although we might attach to the edges of a graph or digraph a labeling or coloring, these (usually) are pretty much arbitrary, and the underlying graph has nothing to do with the extra information. But now I’m going to make a bigger claim.

Philosophical lesson, corollary. Quivers should not, in fact, even be considered as having “edge sets.”

And in fact we can replace “quivers” with “digraphs” or “graphs,” and the same holds true. This sounds like craziness! Of course graphs have edges; otherwise they’d just be sets! And there are actually a number of philosophical reasons to object to this:

  1. It’s evil. If we don’t want graphs to have edge sets, we still need some way to keep track of the “number of edges” between two vertices — but if we’re not doing this by assigning each one a set, or in some other equivalent way, we’re going to end up doing it evilly.
  2. It goes against years of tradition. Not that I’m against overturning the status quo, but most mathematical definitions are the way they are because that formulation has pulled its own weight over the years.
  3. It’s silly. Of course graphs have edges! We need something to color in an edge-coloring, and “forgetting the edge set” kind of interferes with that goal.

All of these are good points, and some of them arise (I think) from the fact that graphs are a rather basic class of mathematical objects, and that different people can intuit them in very different ways. But for now, let’s take the lesson at face value, and see if it has a chance of pulling its weight.

The problem is, most of the definitions of graphs and digraphs refer to an edge set in some way or another. But there’s a way to turn one definition into one that doesn’t, through application of some classical logic. Here we’ll be considering digraphs, possibly with loops but without multiple edges. (Directed pseudographs, if you want.) Now here’s one possible definition:

A directed pseudograph is composed of a vertex set V, an edge set E, and an injective function E \rightarrow V \times V.

But we can replace this by:

A directed pseudograph is composed of a vertex set V and an edge set E \subset V \times V.

And this we can replace by:

A directed pseudograph is composed of a vertex set V and a function E: V \times V \rightarrow \{0,1\}.

And finally we’ll curry, to get the following, rather nice-looking definition:

A directed pseudograph is a function G: V \rightarrow 2^V, where V is called the vertex set.

We’ll take this as our final definition of (directed pseudo)graphs. If you were reading carefully, you might have noticed that this definition of a graph corresponds exactly to the adjacency list structure — to each vertex we’re associating a list (or set) of vertices that it points to. And you can do other fun algorithmic stuff with it, too, but today we’re pretending to be category theorists, so we’d better figure out what a morphism of directed pseudographs is. Fortunately this isn’t too hard:

A morphism of directed pseudographs \pi: G\rightarrow H with vertex sets V, W is a function \pi: V \rightarrow W, with the induced function on power sets denoted \pi^*, such that

(\pi^* \circ G)(x) \subseteq (H \circ \pi)(x)

for all x \in V.

Now for the hard part: what’s an undirected graph? We want to be able to define a broader variety of mappings that are “morphisms of the underlying graph.” But I don’t know what these are! Fortunately some things are easier; for instance, if we want to allow multiple edges, we simply replace power sets by free abelian monoids.

But now I want to return to the title of the post: Where do graphs live? More correctly, where can graphs be represented as adjacency lists? That is, in what categories can we formalize the above construction, to get an abstract definition of graph entirely independent of the vertex set? Well, we need two things: First, we need to be able to replace the class of subobjects by the class of morphisms to a specific object. That means the category has a subobject classifier. Second, we need to be able to curry. That means the category is cartesian closed. These are two of the three requirements for a category to be a topos!

Question. Do adjacency lists determine an abstract graph iff the graph lives in a topos?

Okay, one last thing. The Rado graph is an infinite graph with a lot of strange properties. The best-known construction of the Rado graph is as “the” infinite random graph, but another interesting one is as follows: Take a countable model of ZF as your vertex set; put x and y adjacent if x \in y or y \in x. This seems remarkably similar to the process we use to get an undirected graph from a directed one! I don’t know if this is coincidental, but I hope and suspect it isn’t, entirely.


Tags: , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: