# Which directed graphs correspond to “algebraic” diagrams?

Any diagram for which the question of commutativity make sence is a directed graph, but not any directed graph make the question meaningful. $\require{AMScd}$ \begin{CD} A @>>> B @. A @>>> B\\ @AAA @VVV @VVV @AAA\\ C @<<< D @. C @<<< D \end{CD} The squares above make no sence according to commutativity, but below are some qriteria listed that seems to be necessary for an "algebraic graph".

1. Any vertex must be associated to at least two edges.
2. If two different edges leads from (to) the same vertex, they are parts of two different ways that leads to (from) a common vertex.
3. There must be at least one vertex with two different edges pointing to it.
4. No loops.

Is this a complete list? Is it correct? Is there a name for this kind of graphs?

• Doesn't your second graph satisfy all three points? – A.P. Jul 28 '15 at 17:31
• @A.P. No, not point 2, which is a double qriteria: the main case and the bracket case. – Lehs Jul 28 '15 at 17:34
• A directed graph is a commutative diagram if and only if every undirected cycle consists of two directed paths with the same initial vertex and the same final vertex. – Batominovski Jul 28 '15 at 18:38
• I would suggest that my reply above be put as a definition of "combinatorial commutative diagrams." Then, an "algebraic commutative diagram" in a category $C$ would be a combinatorial commutative diagram whose vertices are labelled by objects in $C$ and whose arc starting from a vertex with label $a\in C$ and ending in a vertex with label $b\in C$ is labelled by a morphism in $\text{Hom}_C(a,b)$ such that the commutativity of morphisms in every undirected cycle is satisfied. (The reason I say "labels" is that two distinct vertices may actually represent the same object.) – Batominovski Jul 28 '15 at 19:15
• @Batominovski: I think there should be a supplement to your straight forward definition, that every vertex should be a part of a cycle. – Lehs Jul 28 '15 at 20:56

First of all, a diagram in $\mathcal{C}$ is not the same thing as a directed graph. A $\Gamma$-shaped diagram in $\mathcal{C}$ is a morphism of graphs $\Gamma\longrightarrow U(\mathcal{C})$, where $U(\mathcal{C})$ denotes the underlying directed graph of $\mathcal{C}$ ${}^{1)}$.

Secondly, it makes sense to talk about commutativity for all kinds of graphs. It is just the usual notion: A diagram is commutative, if for all sequences $$A=V_1\xrightarrow{f_1}V_2\longrightarrow\dots\longrightarrow V_{n}\xrightarrow{f_{n}}V_{n+1}=B$$ and $$A=W_1\xrightarrow{g_1}W_2\longrightarrow\dots\longrightarrow W_{m}\xrightarrow{g_{m}}W_{m+1}=B$$ we have $g_{m}\circ\dots\circ g_1=f_{n}\circ\dots\circ f_1$.

Note as one subtility here: The case $n=0$ is allowed${}^{2)}$! What does that mean? It means that we have an empty composition, i.e. the identity. This implies, that whenever a sequence ends at the point it started at, composition is the identity. In particular, all loops are the identity.

For example, your first diagram is commutative, if and only if whenever walking round the diagram, one ends up with the identity. The diagramm $A\leftrightarrows B$ is commutative if and only if the arrows are inverse isomorphisms. Your second diagram is always commutative.

${}^{1)}$ Via the free-forgetful adjunction between graphs and categories, this is the same thing as a functor $F(\Gamma)\longrightarrow\mathcal{C}$. One can show that limits and colimits of a diagram as morphism of graphs are the same thing as limits and colimits of the associated functors, which justifies the common practice of considering limits of functors. Note however, that one defines the limit of a functor $\mathcal{J}\longrightarrow\mathcal{C}$ as the limit of the underlying morphism $U(\mathcal{J})\longrightarrow U(\mathcal{C})$, so I think it's more natural to think of diagrams as morphisms of graphs.

${}^{2)}$ This is a more monadic point of view. It says that it is more natural to consider $n$-fold composition as a basic concept, not as a derived one, inductively defined using $2$-fold composition, associativity and treating $n=0$ as a special case.

• That is a problem with category theory: it steals definitions... :) – Lehs Jul 29 '15 at 10:38
• @Jakob Werner, I was aware of the case $n=0$ as you stated when I typed down my comment. However, I discussed with somebody in the past and they stated that this type of diagrams shouldn't be included, whence when I replied, I declared that there must be "two direct paths" to avoid the dispute. I do agree with you though. If we want to include the $n=0$ case, we would have to modify my definition to say: "every undirected cycle consists of at most two directed, possibly closed, paths." – Batominovski Jul 29 '15 at 10:55
• I remember now why some people want to ignore directed closed paths in a commutative diagram. Let's take this example: $f:A\to B$, $g:B\to C$, and $h:C\to A$. It is possible to have $h\circ g\circ f=\text{id}_A$, but $f\circ h\circ g \neq \text{id}_B$ or $g\circ f\circ h \neq \text{id}_C$. Hence, it is unclear where the starting point should be. – Batominovski Jul 29 '15 at 12:07
• An example is in the category of abelian groups with $A=\mathbb{Z}$ and $B=C=\mathbb{Z}\oplus\mathbb{Z}$. We define $f$ to be the injection $a\mapsto (a,0)$, $g$ the identity, and $h$ the projection $(a,b)\mapsto a$. Hence, $h\circ g\circ f=\text{id}_A$, $f\circ h\circ g\neq\text{id}_B$, and $g\circ f\circ h\neq \text{id}_C$. Hence, we have this pathology with ambiguity of directed closed paths. – Batominovski Jul 29 '15 at 12:07
• @Batominovski but of course you just require all starting points to satisfy the condition. – Kevin Carlson Jul 29 '15 at 22:43