17
$\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$ Feb 24, 2021 at 10:45
  • $\begingroup$ @ChrisHeunen Thanks for the reference, I'll check it out. $\endgroup$
    – Alec Rhea
    Feb 24, 2021 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, 2021 at 13:12
  • $\begingroup$ @ToddTrimble I'll check out those notes! $\endgroup$
    – Alec Rhea
    Feb 24, 2021 at 13:15
  • $\begingroup$ Also, there are some answers to my old question mathoverflow.net/questions/74615/… $\endgroup$ Feb 24, 2021 at 13:21

6 Answers 6

11
$\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, 2021 at 17:06
  • 4
    $\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, 2021 at 4:14
6
$\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$
2
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, 2021 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, 2021 at 13:12
2
$\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, 2021 at 0:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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