Graph theory from a category theory perspective

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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?

Answer 5

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.

Answer 6

You may be interested in my arXiv paper: Causal-net category, https://arxiv.org/abs/2201.08963.

I totally agree with Mirco A. Mannucci \bib{384818}{misc}{
title={Graph theory from a category theory perspective},
author={Mirco A. Mannucci (https://mathoverflow.net/users/15293/mirco-a-mannucci)},
note={URL: https://mathoverflow.net/q/384818 (version: 2021-02-24)},
eprint={https://mathoverflow.net/q/384818},
organization={MathOverflow}
}

The main idea to view graph theory from the category theory perspective is summarized by the slogan: Graph Theory= Kleisli Category.

In this paper, we introduce the category of causal-nets, called causal-net category and denoted by Cau, which takes causal-nets as objects and the functors between the path categories of causal-nets as morphisms. This category is actually the Kleisli category of the “free category on a causal-net” monad.

The introduction of this category is motivated by the study of causal-net condensation, which aims to give a categorical formulation of the Baez construction of spin networks for gauge theory. Causal-net category plays the role in causal-net condensation just as that of little n-disc operad in factorization homology. The construction of causal-net condensation turns out essentially to be a reformation of Joyal-Street’s graphical calculus for symmetric monoidal categories. Through detailed analysis, we found that there are six types of fundamental morphisms in Cau, which correspond exactly to six basic conventions of graphical calculi for monoidal categories. The correspondence between fundamental morphisms and basic conventions shows a fundamental connection between graph theory and monoidal categories.

In this paper, we study several composition-closed classes of morphisms, such as coarse-grainings, mergings, contractions, fusions, immersions, etc. We show that many common graph operations can be represented by morphisms of Cau in the same direction or in the opposite direction. We also introduce a purely categorical framework for general minors, which is meaningful for general small categories. We categorify the usual minor posets to gauged minor categories, which turns out to be acyclic categories. Based on this results, we conclude that causal-net category is a natural framework for the study of causal-nets and the theory provides a new understand of categorical graph theory.

In this paper, we only discuss acyclic directed graphs, but the way of discussion is effectively suitable for general directed graphs and undirected graphs.