### Which Graphs Can be Given a Category Structure?

#### Posted by Tom Leinster

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$,

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

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

Why?

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

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

## 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?