# How is an $O$-graph different from a directed graph? - Category Theory

I'm reading Category Theory by Mac Lane and I'm trying to understand the paragraphs in the pictures included below.

What is the difference between a directed graph and an $O$-graph?
Why is the picture in the blue box considered an $O$-graph?

The blue box picture looks like two parallel morphisms between two digraphs both called $O$, and not an $O$-graph which is defined as a single digraph.

What does it mean by both functions domain and range the identity? What is the difference between a directed graph and an $O$−graph?

An $O$-graph is a directed graph where $O$ is the set of vertices (although the category of $O$-graphs differs substantially from the category of directed graphs—see Alex Kruckman's comment below). For example, this graph (public domain image from Wikimedia Commons, created by Wikimedia user Booyabazooka) is a $\{1, 2, 3, 4\}$-graph:

Why is the picture in the blue box considered an $O$−graph?

The way MacLane defines a graph is as four pieces of information:

• A set $A$ of arrows
• A set $O$ of verticies
• A function $\partial_0: A \rightarrow O$, which defines the tail of each arrow
• A function $\partial_1: A \rightarrow O$, which defines the head of each arrow

For example, for the graph in the image above:

• $A$ is a set with 6 elements, which could be $\{e_1, e_2, \dots, e_6\}$.
• $O = \{1, 2, 3, 4\}$
• If $e_1$ is the top horizontal arrow from $1$ to $2$, then $\partial_0(e_1) = 1$ and $\partial_1(e_1) = 2$.

MacLane uses the shorthand $A \rightrightarrows O$ for the two functions $\partial_0: A \rightarrow O$ and $\partial_1: A \rightarrow O$.

The graph $O \rightrightarrows O$ means a graph where each element of $O$ is regarded as both a vertex and an arrow. By saying that $\partial_0$ and $\partial_1$ are both identity functions, he's saying that each element of $x \in O$, when regarded as an arrow, is a loop from the vertex $x$ to itself.

• It's also worth noting that $O$-graphs differ from directed graphs in the definition of their morphisms: A morphism of directed graphs $(O,A,\delta_0,\delta_1)\to (O',A'\delta_0',\delta_1')$ might have any function $D_O\colon O\to O'$ as its map on objects, while a morphism of $O$-graphs $(O,A,\delta_0,\delta_1)\to (O,A'\delta_0',\delta_1')$ is required to have $\text{id}_O\colon O\to O$ as its map on objects. Part of the categorical philosophy is that a class of mathematical objects is determined not just by the definition of the object, but also the definition of the maps between objects. – Alex Kruckman Dec 11 '17 at 16:46
• I believe you recognize this, but for the benefit of the OP I comment that I'm fairly certain the occurrence of the word "range" in that paragraph in the picture is a typo, and what's intended is the "codomain" terminology used in his definition of a directed graph (i.e. $\partial_1$). – Malice Vidrine Dec 11 '17 at 16:46
• @OliverG, in Mac Lane's formulation of a directed graph $A \rightrightarrows O$, the set of arrows $A$ does not have to carry any information about what the head and tail of the arrows are. That is determined by the functions $\partial_0: A \rightarrow O$ and $\partial_1: A \rightarrow O$. In Mac Lane's "simplest" $O$-graph $O \rightrightarrows O$, the set $O$ is serving both as the set of arrows and set of vertices. So, that's what I mean by saying "each element of $O$ is regarded as both a vertex and an arrow". (Continued...) – PersonX Dec 12 '17 at 0:45
• Now, the statement that $\partial_0$ ("domain") and $\partial_1$ ("range", which Malice Vidrine points out should be "co-domain") are both identity is saying that each $x \in O$, as an arrow, has $O$ as both its domain (head) and co-domain (tail). That is saying that each $x \in O$ is a loop from $x$ to $x$. – PersonX Dec 12 '17 at 0:56
• Note that you could have a $O$-graph $O \rightrightarrows O$ without $\partial_0$ and $\partial_1$ both being the identity. For example, let $G$ be any finite group, and $g \in G$ a non-identity element. Then define $\partial_0: G \rightarrow G$ by $\partial_0(x) = x$ and $\partial_1: G \rightarrow G$ by $\partial_1(x) = gx$. This would give you a perfectly good $G$-graph. – PersonX Dec 12 '17 at 0:58

The directed graph has $A$ for arrows and $O$ for vertices. The $O$-graph has $O$ for its vertices. The $O$ just seems to be an explicit mention of the underlying set, whereas a graph can have any set of vertices.

I believe that they mean that the "simplest example" of an $O$-graph is the one where both of the arrows $O\to O$ are the identity.

• So you're saying: An $O-$graph is defined as a digraph where the objects AND arrows are both the set $O$? – Oliver G Dec 11 '17 at 16:21
• @OliverG Upon reading the definition I think that an $O$-graph is any graph that has the set $O$ as its vertices. These are clearly ordinary graphs, but not all graphs are $O$-graphs, since graphs can have other ses of vertices as well. – neptun Dec 11 '17 at 16:28