Which Graphs Can be Given a Category Structure?

March 27, 2011

Which Graphs Can be Given a Category Structure?

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

I’ve just come back from the successful thesis defence of Samer Allouch, a student of Carlos Simpson in Nice. Among other things, Allouch’s thesis completely answers the question:

which finite directed graphs can be equipped with the structure of a category in at least one way?

The answer turns out to be rather satisfying: it’s neither simple enough that you’d guess it without prolonged thought, nor prohibitively complicated.

But here’s a curious thing: each of the conditions in Allouch’s theorem involves at most four vertices or objects. Let’s say that a directed graph is categorical if it can be given the structure of a category. Then for a finite directed graph $G$ ,

$G$ is categorical if and only if each full subgraph of $G$ with $\leq 4$ vertices is categorical.

(By a ‘full subgraph’ I mean a selection of the vertices and all of the edges between them.) I want to know:

Why?

In other words, can you prove this directly, without using Allouch’s theorem?

$MathML-enabled post (click for more details).$

Probably everyone’s first thought is that this could have something to do with the fact that associativity involves four objects. But on its own, this observation isn’t a proof. I talked about this with several people at Nice — Clemens Berger, André Hirschowitz, Carlos Simpson — and they observed that as long as the method of construction is uniform enough, one should be able to patch together the four-object categories to make a big category. Having read Allouch’s proof, I can sort of see that this might be how things work… but my mental picture’s fuzzy.

Maybe someone here has an idea.

You can read most of the material in Samer’s thesis in two arXiv papers (1, 2). I believe the thesis itself will eventually be available online.

He phrases everything in terms of matrices rather than graphs. Finite directed graphs are essentially the same thing as matrices of natural numbers, at least if you don’t mind putting the vertices of the graph in order: then the $(i, j)$ -entry of the matrix is the number of edges from the $i$ th vertex to the $j$ th.

The underlying graph of a finite category $A$ — say with objects $a_1, \ldots, a_n$ — corresponds to the matrix $Z_A$ whose $(i, j)$ -entry is $| Hom(a_i, a_j)|$ . Call a square matrix categorical if it is of the form $Z_A$ for some finite category $A$ (or equivalently, if the corresponding graph is categorical).

Life turns out to be easier when all of the entries of the matrix are strictly positive. Allouch’s first paper covers this case, giving necessary and sufficient conditions for a matrix of strictly positive integers to be categorical. (Non-francophones beware: $0$ counts as positif.) In this case, the conditions involve only three objects. So a matrix of strictly positive integers is categorical if and only if each $1 \times 1$ , $2 \times 2$ and $3 \times 3$ principal submatrix is categorical.

His second paper covers the general case: which finite directed graphs (or matrices of nonnegative integers) are categorical? I won’t give you the full answer: you can read his paper for that. But to get you in the mood — and to give you a sample of the arguments involved — here are three puzzles.

Puzzle 1 Suppose that in a finite category, we have objects and maps $a \stackrel{\longrightarrow}{\longleftarrow} b        \bar{a} \stackrel{\longrightarrow}{\longleftarrow} \bar{b}.$ Suppose also that $a$ and $\bar{a}$ have no non-identity endomorphisms. Prove that $|Hom(a, \bar{a})| + |Hom(b, \bar{b})| \geq |Hom(a, \bar{b})| + |Hom(\bar{a}, b)|.$

Puzzle 2 Let $Z = \left( \begin{matrix} 1 &k \\ \ell &m \end{matrix} \right)$ be a matrix of nonnegative integers. Prove that if $Z$ is categorical then either $k = \ell = m = 1$ or $\det Z \gt 0$ .

Puzzle 3 The converse of Puzzle 2. (That is, given a matrix $Z$ of the form shown, such that either $k = \ell = m = 1$ or $\det Z \gt 0$ , prove that $Z$ is categorical.)

Posted at March 27, 2011 9:10 PM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2377

19 Comments & 0 Trackbacks

Re: Which Graphs Can be Given a Category Structure?

Was there a good reason to define a new term “full subgraph” when the perfectly good term “induced subgraph” already means the same thing?

Posted by: D. Eppstein on March 27, 2011 10:08 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

The reason was that I didn’t know the term “induced subgraph”. But now I do. Thanks!

Posted by: Tom Leinster on March 27, 2011 10:09 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

I’ve just discovered that “full subgraph” is in fact established usage, at least in some circles (e.g. here and here). As anyone with a categorical background will have guessed, I chose the term because of full subcategory, but I didn’t realize until now that it was actually in use.

Posted by: Tom Leinster on July 17, 2013 6:45 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

Thanks for this post. I had often wondered about this. When I bump my head into this problem again I’ll go look up all those references…

Posted by: Bruce Bartlett on March 27, 2011 10:28 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

Curse my inadequate French. Are the conditions in Allouch’s theorem first-order, i.e. expressible only in terms of the edge-vertex relationships between the four elements involved? If so, he should be able to use the compactness theorem to extend the result to infinite directed graphs.

Posted by: Scott McKuen on March 27, 2011 11:15 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

I think so, though I’m not totally sure I understand the question.

Given the multiple uses of the word “graph”, I should perhaps have emphasized in the post that by a directed graph, I mean one in which there can be multiple edges. Formally, by a directed graph I mean a set $V$ , a set $E$ , and two functions $s, t: E \to V$ (assigning to an edge its source, or tail, and its target, or head).

Allouch states his theorem a bit indirectly, in the sense that there’s never a statement of the form “a matrix is categorical if and only if …”. There are reasons for that, but it does make this kind of question harder to answer. Anyway, as far as I can see, the conditions on a $4 \times 4$ matrix (corresponding to a 4-vertex graph) involve only very tame arithmetic statements. For example, a $2 \times 2$ matrix $\left( \begin{matrix} j &k \\ \ell&m \end{matrix} \right)$ of nonnegative integers is categorical if and only if ( $j \geq 2$ and $m \geq 2$ ) or $j = k = \ell = m = 1$ or $j m \gt k \ell$ . I don’t think the statement of the full theorem contains anything more logically sophisticated than that.

Posted by: Tom Leinster on March 28, 2011 12:05 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Ah…that initially looks less promising, since you’re multiplying cardinalities of Hom sets as part of your conditions. You’ve got variables (cardinalities) counting batches of other variables (morphisms), which generally means you aren’t in a first-order situation anymore. If that happens all over the place in a fairly arbitrary way, then it won’t work. On the other hand, you say everything can be done on four objects - is there a similar bound on the number of morphisms? Or is there any kind of definable bound on the size of the Hom sets? If so, then it might still work.

This specific $2 \times 2$ condition that you put down looks like it actually can be rewritten as a first-order statement in the “2-sorted” language of $V, E, s, t$ , though, because you’ve bounded the variables from above. E.g., $j \ge 2$ becomes

$\forall a,b \exists e_1, e_2 s(e_1) = a \wedge s(e_2) = a \wedge t(e_1) = a \wedge t(e_2) = a$

The condition $j m \ge k l$ has to be unpacked given the other conditions to something more elaborate like “for every pair of morphisms $x,y$ , where $x: a \rightarrow b$ and $y: b \rightarrow a$ , you have a $z: a \rightarrow a$ (that does not also play the same role for any other pair)”, along with symmetric conditions for the other object in the category.

Basically, if the conditions can be “unrolled” from nonnegative integer matrices into finite statements about bounded numbers of edges and vertices, then this is probably a first-order set of conditions. If the nature of the conditions is that you can’t escape from multiplicative statements about cardinalities of Hom sets, then you won’t even be able to sensibly state the conditions for the case infinite graphs, since in some cases the Hom sets may be infinite (and you would not be able to write down in a first-order way any condition specifying that the Hom sets are finite, either).

Posted by: Scott McKuen on March 28, 2011 1:40 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Come to think of it, I wonder whether Allouch’s theorem extends to infinite categories in a really simple way. I mean, maybe all that’s needed is to take the conditions on the entries of the matrix and interpret them as applying to cardinals rather than natural numbers. To do this, the inequalities should be written in terms of $\geq$ rather than $\gt$ , e.g. a condition such as “ $j m \gt k \ell$ ” should be expressed as “ $j m \geq k \ell + 1$ ”. (And when I say “matrix” here, I’m allowing matrices with infinitely many rows and columns.)

I think this would be possible as long as the pigeonhole principle isn’t used anywhere in the proof, and as far as I can remember, it isn’t.

Posted by: Tom Leinster on March 29, 2011 2:31 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

And by the way, I hope it is possible to apply the compactness theorem: that would be very nice.

Posted by: Tom Leinster on March 28, 2011 12:19 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

One obvious necessary condition is that the nerve of the directed graph is a quasi-category, and so the horn-filler conditions place numerical bounds on certain paths, which are represented by linear combinations of the elements of the matrix. In addition to being a quasi-category we need the nerve to be coskeletal at a certain level, which gives us some equations between linear combinations of the elements of the matrix. The required conditions only need to talk about a small number of edges and vertices so this gives a clue why only the sub-matrices need to be considered.

Obviously this is far from a sufficiency proof, but I hope it heads in the right direction.

Posted by: David Roberts on March 28, 2011 1:12 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

I can’t think of any way to define the “nerve” of a directed graph to be a simplicial set with any nontrivial 2-simplices. It seems like the question is whether we could add 2-simplices to it in some way to make it into a category.

Posted by: Mike Shulman on March 28, 2011 5:54 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

</foot in mouth> You’re right. But we could get some bounds on the size of the set of 2-simplices with given vertices.

Posted by: David Roberts on March 29, 2011 7:03 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

Does the fact that “a matrix of strictly positive integers is categorical if and only if each 1 X 1, 2 X 2, 3 X 3 prinicipal submatrix is categorical” have something to do with the role of quaternions in quantum field theory? Is there a finite directed graph below the Planck scale that can generate all of quantum field theory? What is the connection between finite directed graphs and string theory? Have string theorists unwisely ignored the work of J. P. Lestone on calculation of the fine structure constant?
Does the proton have a generalized Lestone model?
In Lestone’s model, an electron consists of 3 loops of one vibrating superstring confined on the 2-dimensional surface of a 3-sphere.
Consider the following:
HYPOTHESIS of the generalized Lestone model for the proton:
A proton consists of 9 loops of one vibrating superstring confined on the 3-dimensional 3-hypersurface of a 4-sphere.
What might the preceding hypothesis imply? The answer is unclear but note that
(9/2.980192) * ((proton mass)/(electron mass))**.25/(2 * pi**2) = 1.001, approximately, according to Wolfram Alpha.
3 * (1 + 1/(18 pi**2)) * ((proton mass)/(electron mass))**.25/(2 * pi**2) = 1, approximately.

Posted by: David Brown on March 31, 2011 11:03 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Does the fact that “a matrix of strictly positive integers is categorical if and only if each 1 X 1, 2 X 2, 3 X 3 prinicipal submatrix is categorical” have something to do with the role of quaternions in quantum field theory?

It’s impossible to answer such a question with a definite “no”, but I see no evidence for it.

Is there a finite directed graph below the Planck scale that can generate all of quantum field theory?

This doesn’t make sense, and I don’t see any connection between the rest of the comment and the topic at hand.

I don’t think this is worth pursuing.

Posted by: Tom Leinster on March 31, 2011 11:09 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

@Tom: You say, a graph is categorical if it can be given the structure of a category. What exactly does this mean? Does it simply mean that there is an associative composition of “matching” arrows? So that the question reads: How does the existence of an associative composition of matching arrows depend on the pattern of numbers of arrows between vertices?

Posted by: Hans Stricker on August 22, 2013 10:09 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

That’s right, except that one has to think about identities as well as composition.

Let me put it another way. Every finite category $C$ has an underlying finite directed graph $U(C)$ . The question is: for which finite directed graphs $G$ does there exist a finite category $C$ such that $U(C) \cong G$ ?

Of course, this isn’t a precise question, but I think the intent is fairly clear — we want an “explicit” description of this class of graphs, whatever “explicit” means.

Posted by: Tom Leinster on August 22, 2013 11:57 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Would it make things clearer to note that $U$ is a forgetful functor (with an interesting left adjoint)?

Posted by: Hans Stricker on August 24, 2013 8:07 AM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Tangentially related: enumeration of finite categories appears to be a rather young field of study. Cf. A125696 and A125696 in the OEIS, and https://mathoverflow.net/questions/159882/counting-categories-with-at-most-n-morphisms

and the recent work of G. Crutwell

Posted by: Peter Heinig on June 14, 2017 8:49 PM | Permalink | Reply to this

Re: Which Graphs Can be Given a Category Structure?

$MathML-enabled post (click for more details).$

Just happened upon this when thinking of neural nets and categories. I wonder if there is an obstruction via homology (derived from free forget) as a proof.

Posted by: Marc Nunes on July 15, 2018 7:44 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

March 27, 2011