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".
- Any vertex must be associated to at least two edges.
- If two different edges leads from (to) the same vertex, they are parts of two different ways that leads to (from) a common vertex.
- There must be at least one vertex with two different edges pointing to it.
- No loops.
Is this a complete list? Is it correct? Is there a name for this kind of graphs?
$\endgroup$ 71 Answer
$\begingroup$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.
$\endgroup$ 6
