12
$\begingroup$

Are there any textbooks on graph theory written for a category theorist?

It would probably have to be on directed graph theory, but if there's some trick we can use to talk about undirected graphs as well that would be interesting.

A little more specifically, I'm looking for a text that begins by defining directed graphs and paths, then defines the obvious category out of a given directed graph with paths as arrows, then proceeds to derive results about directed graphs using these categories.

Most connections I see made between category theory and graph theory are in the other direction, taking the underlying graph of a category and saying something about it to derive a result about the category, but as someone comfortable with categories and not comfortable with graphs this approach isn't particularly illuminating.

Further, unless I'm mistaken, these constructions amount to an equivalence (maybe even an isomorphism?) between the category of directed graphs and the category of categories, so it feels like we should be able to say something about directed graphs from this perspective.

Any references are appreciated.

$\endgroup$
7
  • 3
    $\begingroup$ Not quite what you're looking for, but Godsil and Royle's "Algebraic Graph Theory" explicitly talk about homomorphisms between graphs and automorphism groups of graphs, and defines things like chromatic number in terms of morphisms. $\endgroup$ – Chris Heunen Feb 24 at 10:45
  • $\begingroup$ @ChrisHeunen Thanks for the reference, I'll check it out. $\endgroup$ – Alec Rhea Feb 24 at 13:10
  • 2
    $\begingroup$ I don't think I know of any books that would qualify (I myself would like to know if there are!), but you might be interested in some of Tom Leinster's posts at the Cafe, like this: golem.ph.utexas.edu/category/2014/12/… $\endgroup$ – Todd Trimble Feb 24 at 13:12
  • $\begingroup$ @ToddTrimble I'll check out those notes! $\endgroup$ – Alec Rhea Feb 24 at 13:15
  • $\begingroup$ Also, there are some answers to my old question mathoverflow.net/questions/74615/… $\endgroup$ – David White Feb 24 at 13:21
7
$\begingroup$

A few points:

  1. The category of graphs is certainly not equivalent to the category of categories. But they are related (for more on that see (3)).

  2. As you allude to, there are multiple categories of graphs to be interested in. I've had a go at naming some of them here, including directed/undirected, multi/simple, and various conditions on loops, trying to view them from a common framework as being certain categories of presheaves.

  3. Let $Gph$ be the category of directed multigraphs (as usual for category theorists), and let $U: Cat \to Gph$ be the forgetful functor. As you point out, $U$ has a left adjoint $F: Gph \to Cat$, which sends a graph $\Gamma$ to the category of "paths" in $\Gamma$. This adjunction is even monadic, exhibiting $Cat$ as a category of algebras over $Gph$. In this way, it's reasonable to regard a category as a graph with extra structure. I'd hazard a guess that dually the functor $F: Gph \to Cat$ is maybe comonadic? (EDIT: Yes, I'm pretty sure that $F$ preserves all equalizers. It is clearly a conservative left adjoint between complete categories, so it's comonadic by the dual of the crude monadicity theorem.) In this way, it should be reasonable to regard a graph as a category with extra structure associated to being a free category. This would give some more justification for your approach of viewing a graph as a category with extra structure.

$\endgroup$
2
  • $\begingroup$ This is all very cool, thank you! $\endgroup$ – Alec Rhea Feb 24 at 17:06
  • 2
    $\begingroup$ The fact that this path functor $F$ is comonadic is explained in detail in the "Prologue" to Dawson–Paré–Pronk's Paths in double categories. In fact the "extra structure" making a category (free on) a graph is a property, which comes from the fact that the $2$-comonad induced by the extension of $F$ to a $2$-functor from (op)virtual double categories to double categories is oplax-idempotent (Theorem 1.21 op.cit.) $\endgroup$ – David Kern Mar 14 at 4:14
5
$\begingroup$

You may be interested with my work with Bisson, we have defined various closed models on category of graphs. In particular in the category of directed graphs. Consider the category $C$ which has two objects $0,1$ and two morphisms: $s,t:0\rightarrow 1$. A directed graph $G$ is a presheaf defined on $C$, that is two sets $G_0$ and $G_1$ where $G_0$ is the set of vertices here and $G_1$ the set of arrows $G(s):G_1\rightarrow G_0$ is the source map and $G(t)$ the target maps.

The category of undirected graphs can also be viewed as a topos, by adding in $C$ an involution $i:1\rightarrow 1$ such that $i\circ s=t$.

Bisson, Terrence, and Aristide Tsemo. "A homotopical algebra of graphs related to zeta series." Homology, Homotopy and Applications 11.1 (2009): 171-184.

Bisson, T., & Tsemo, A. (2011). Symbolic dynamics and the category of graphs. arXiv preprint arXiv:1104.1805.

$\endgroup$
3
  • $\begingroup$ This sounds very cool, thank you. $\endgroup$ – Alec Rhea Feb 24 at 17:24
  • $\begingroup$ Why was the 2011 paper never published? It seems like a great paper! Maybe you could submit it? Or submit it again if you already tried once? $\endgroup$ – David White Feb 24 at 22:32
  • $\begingroup$ tac.mta.ca/tac//volumes/25/22/25-22.pdf $\endgroup$ – Tsemo Aristide Feb 25 at 0:55
4
$\begingroup$

Not quite what you're looking for, but the Handbook of Product Graphs does discuss the category of graphs, and which of the four products of graphs are appropriate from the point of view of category theory (hint: it's the categorical product, not the lexicographic product or the cartesian product). If you search this pdf for "category" you will find various little nuggets you might enjoy.

$\endgroup$
1
  • $\begingroup$ Thank you David, I'll take a look through it. $\endgroup$ – Alec Rhea Feb 24 at 13:12
3
$\begingroup$

What you are describing is here. A (directed) graph is essentially a free category, ie the path category generated by the graph.

This construction is the left adjoint to the forgetful functor from Cats to the category of directed graphs.

This amount to an equivalence between the category of directed graphs and the category of free categories, not the entire Cat (which makes sense, a category can be presented from a free cat by imposing relations, ie commuting diagrams, aside the trivial ones. That side is invisible from the point of view of the underlying graph).

Now, on to the book: as far as I know, there isn't (though there are a few refs to the above, again look it up in the hyperlink). Such a book should investigate basic results of directed graph theory from the point of view of the theory of free categories. Not too sure it would help finding new facts in graph theory, but it is nevertheless an intriguing idea. After all, there is an entire industry on free groups, why not on free cats?

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the link and vocab update, I'll take a look through the references. $\endgroup$ – Alec Rhea Feb 24 at 13:12
1
$\begingroup$

You may be interested in "Functorial Approach to Graph and Hypergraph Theory" by M. Schmidt. It contains plenty of adjunctions and gives examples of concrete constructions. It contains more than your average paper on categorical constructions on graphs. It is a generalization of the ideas contained in the paper "Categorical Constructions in Graph Theory" by Bumby and Latch. Even if it doesn't have exactly what you are looking for, it is an interesting look.

$\endgroup$
1
  • $\begingroup$ Thank you for the reference, I’ll check it out. $\endgroup$ – Alec Rhea Apr 13 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.