# Intersection between category theory and graph theory

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$).

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?

-
Perhaps one problem about thinking of dense subcategories via graphs is that to express the universal property of a colimit one needs to use the composition in the category, or at the very least commuting diagrams. Why do you want to use this approach? –  David Roberts Sep 6 '11 at 0:03
@David Roberts: You're absolutely right, the question about dense subcategories was a silly one. I asked because I'm curious about the intersection between category theory and graph theory (e.g. for future research or to give a talk on the subject) and I thought that would be a good toy problem to think about. Anyway, I edited the question a lot to make what I wanted clearer. Hopefully people don't think it's too vague. –  David White Sep 6 '11 at 14:24
Are you familiar with nerves? I think your question is more or less equivalent to asking about what properties of simplicial sets (that satisfy the unique inner horn-filling condition) can be reconstructed from the 1-skeletons. –  S. Carnahan Sep 6 '11 at 17:10
@S. Carnahan: I've heard of nerves and probably read the definition once or twice, but never got deeply into them. I've never heard of inner horns. I'll read up this afternoon and see how much this hits on what I was thinking about. I don't believe Allouch's thesis mentions nerves or 1-skeletons, but that's probably because everything in sight is finite. If you have the time and inclination, I'd certainly love to hear about known results where you can reconstruct properties from the 1-skeletons. It seems we lose a lot of data (perhaps too much?) by moving to the 1-skeleton –  David White Sep 6 '11 at 18:38
Possibly related, if this goes down the skeleton path: mathoverflow.net/questions/11674/… –  David White Sep 6 '11 at 18:38

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".

-