I'm a graduate student who has been spending a lot of time working with categories (model categories, derived categories, triangulated categories…) but I used to love graph theory and have always had a soft space in my heart for it. The semester I'm taking a graph theory course and for the first time seeing connections to category theory in the form of the underlying directed graph of a category (objects become vertices, and we put an edge $(A,B)$ if there's a morphism $A\rightarrow B$).
I'd like to learn more about places where graph theory has informed category theory.
One question that can be asked in this vein is whether a given graph could be the underlying graph of a category. This has been answered for finite graphs by Samer Allouch in his thesis. Sadly, the thesis is in French and I can't really understand it. Here is a nice n-Category Cafe post about this. In that post someone asked for an explanation of the results or ideas in English, but that was never given. I'd love to hear about this if anyone here knows about it, but my question is more general. Since most categories I come across and understand are not finite (nor even small), I'm wondering about the existence of work connecting large categories with graph theory.
Because this is very vague, I came up with a few specific questions. However, if all I get is reference requests which have nothing to do with these questions I'll still be happy. In particular, I'd love to hear about times questions similar to those below have been asked and answered, or to get a recommendation for a textbook on category theory which focuses on the underlying graph more than Maclane does.
1) Has anyone classified (sub)graphs which correspond to replete subcategories? For instance, is there a purely graph theoretic test for whether or not a subgraph $\mathcal{H}$ of $G$ underlies a replete subcategory $\mathcal{D}$ of $\mathcal{C}$?
Here's what I can tell so far about this problem: for each non-isomorphic object in $\mathcal{D}$ you will get a complete graph in $H$. Composition morphisms ensure that if there is any arrow from one vertex to another vertex in a different complete subgraph then there will be arrows from all vertices in the first complete subgraph to all in the second. So $H$ will need to look like a disjoint union of complete graphs, where complete here means for every two vertices there's an edge at least one way between them. One reason this is hard for me to wrap my brain around is that we're dealing with subgraphs of uncountable graphs in which vertices can have uncountable degree. I can solve this by restricting to isomorphism classes of objects, but I'm not sure this is a good idea. I'd love to hear from those more versed in category theory about the pros/cons of restricting to isomorphism classes. Note that the version of this question for full subcategories is answered by "induced subgraphs" and so it seems like you have no hope of classifying thick subcategories or other interesting full subcategories. I originally asked this question for dense subcategories and the helpful comment of David Roberts below shows you won't have success here because going to the underlying graph loses composition data.
Another sample question, about products of categories:
2) The underlying graph of $\mathcal{C}\times \mathcal{D}$ is the strong product $G\boxtimes H$ of the two underlying graphs. Is there a category corresponding to the cartesian product of two underlying graphs? The tensor (direct) product?
Best Answer
There is an interaction between category theory and graph theory in
F.~W.~Lawvere. Qualitative distinctions between some toposes of generalized graphs. In {\em Categories in computer science and logic (Boulder, CO, 1987)/}, volume~92 of {\em Contemp. Math./}, 261--299. Amer. Math. Soc., Providence, RI (1989).
which we have exploited in
R. Brown, I. Morris, J. Shrimpton and C.D. Wensley, `Graphs of Morphisms of Graphs', Electronic Journal of Combinatorics, A1 of Volume 15(1), 2008. 1-28.
But that is actually about possible categories of graphs, which may be the opposite of the question you ask.
If you look at groupoid theory, then "underlying graphs" are fundamental, for example in defining free groupoids. See for example
Higgins, P.~J. Notes on categories and groupoids, Mathematical Studies, Volume~32. Van Nostrand Reinhold Co. London (1971); Reprints in Theory and Applications of Categories, No. 7 (2005) pp 1-195.
Groupoids are kind of "group theory + graphs".