Is there a free digraph associated to a graph? - MathOverflow

Is there a free digraph associated to a graph?

2009-10-21T10:11:23Z

A little bit of background: A graph G is, of course, a set of vertices V(G) and a multiset of edges, which are unordered pairs of (not necessarily distinct) vertices. We say that two vertices v_1, v_2 are adjacent if {v_1, v_2} is an edge. A directed graph, or digraph is essentially the same thing, except that the edges are now ordered pairs. Digraphs have a rather nice categorical interpretation.

A graph homomorphism is exactly what it should be, categorically, if you think of graphs as "sets with an adjacency structure." It's a map f: V(G) \rightarrow V(H) is a homomorphism if v_1, v_2 \in V(G) adjacent implies f(v_1), f(v_2) adjacent. The notion of homomorphism for directed graphs is essentially the same; if there's an edge from v_1 to v_2, then there's an edge from f(v_1) to f(v_2). Taking these definitions as morphisms, we can define categories of graphs and of digraphs.

Oftentimes in graph theory (particularly when linear algebra methods come into play), it's easier to work with a digraph than a graph, and so we usually orient the edges arbitrarily. But this isn't really natural...

There's a forgetful functor from the category of digraphs to the category of graphs. Does this functor have an adjoint? (I forget which is left and which is right.) Now that I think about it, is the obvious thing (replace each edge by a pair of directed edges, one in each direction) an adjoint, and if so is there a way to fudge the categories so that simple graphs are taken to simple digraphs?

Answer by Greg Stevenson for Is there a free digraph associated to a graph?

2009-10-21T12:08:51Z

At least if one takes labeled graphs (LGrphs) and labeled digraphs the functor you suggest, say D, is right adjoint to the forgetful functor which I'll call U. There is a canonical natural transformation UD -> Id_{LGrphs} which just collapses the doubled edges to the ones they came from. For a labeled digraph Q and a labeled graph G the bijection on hom-sets then sends a map UQ -> G to the unique lift Q -> DG which sends each directed edge of Q to the corresponding edge of the appropriate direction which lifts the assignment coming from UQ -> G. I guess when you just define morphisms in terms of adjacency or directed adjacency and edges are indistinguishable then it is still fine.

And the comment to your question indicates that there can't be a left adjoint, so no free digraph just a cofree one.

Answer by Reid Barton for Is there a free digraph associated to a graph?

2009-10-21T18:35:05Z

I like to use the following definitions, which give a nonstandard definition of undirected graph but produce particularly nice categories.

A directed graph is a pair of sets V and E together with two maps s, t : E -> V. Call the category of these DirGraph.

An undirected graph is a pair of sets V and E together with two maps s, t : E -> V plus a map r : E -> E such that r^2 = 1, sr = t and tr = s. Call the category of these UndirGraph.

The interpretation of directed graphs should be obvious. For an undirected graph, an edge is an orbit under r of an element of E. Note that there are two kinds of loops--orbits of size 1 or 2.

We can represent the categories of directed graphs and undirected graphs as the categories of presheaves on two categories Dir and Undir respectively (each has two objects corresponding to V and E and a small number of morphisms). There's an inclusion functor i : Dir -> Undir which induces a restriction functor UndirGraph -> DirGraph; this is your doubling functor. It has adjoints on both sides (left and right Kan extension). The left adjoint is your "forgetful" functor DirGraph -> UndirGraph. The right adjoint is another functor DirGraph -> UndirGraph which roughly speaking sends a directed graph G to the undirected graph G' with the same vertices where an edge between v and w in G' is a pair of an edges in G, one from v to w and one from w to v.

So with these definitions, not only does the "forgetful" functor have a right adjoint, but its right adjoint also has a right adjoint.