nLab
directed n-graph

Idea

A directed $n$-graph, or $n$-digraph, is a higher dimensional generalization of a directed graph with $r$-dimensional edges spanning $(r-1)$-dimensional vertices.

A directed $n$-graph is like an n-category with units and composition forgotten. Indeed, an $n$-category is a directed $n$-graph with extra structure. To formalize this idea, we say there is a forgetful functor

$$U:nCat\to nDiGraph$$U : n\Cat \to n\DiGraph

where $nDiGraph$ is the category of directed $n$-graphs and $nCat$ is the category of small $n$-categories. Moreover, this forgetful functor has a left adjoint

$$F:nDiGraph\to nCat$$F : n\DiGraph \to n\Cat

sending each directed $n$-graph to the free $n$-category on that $n$-graph. A free $n$-category on an $n$-graph is called an $n$-quiver.

Definition

An abstract directed $n$-graph $X$ is a category with

• objects $X_r$ of $r$-dimensional edges (or $r$-edges) for $0\le r\le n$;

• morphisms $s_r,t_r:X_{r+1}\to X_r$, called sources and targets for $0\le r<n$;

• together with identity morphisms ${\mathrm{Id}}_r:X_r\to X_r$ for $0\le r\le n$.

A directed $n$-graph is a functor $G:X\to$ Set.

A directed $n$-graph in a category $C$ is a functor $G:X\to C$.

An $r$-edge $e\in G_r$ is called an identity (or $r$-loop) if

$$s(e)=t(e).$$s(e) = t(e).

A morphism $i_r:X_r\to X_{r+1}$ sending an $r$-edge to its respective $(r+1)$-loop, when defined, is called an identity assigning map. Identity assigning maps satisfy

$$s_r\circ i_r={\mathrm{Id}}_r$$s_r\circ i_r = \mathrm{Id}_r

$$t_r\circ i_r={\mathrm{Id}}_r.$$t_r\circ i_r = \mathrm{Id}_r.

When identity assignment maps are defined for all $0\le r<n$, the directed $n$-graph is referred to as a directed $n$-graph with identities.

Remarks

• A directed $n$-graph is not required to contain identities.

Let $G_r=G(X_r)$, $s_r=G(s_r)$, $t_r=G(t_r)$.

• Any two consecutive objects $G_r,G_{r+1}$ together with morphism $s_r,t_r,{\mathrm{Id}}_r,{\mathrm{Id}}_{r+1}$ constitute a directed graph. In particular, a directed 1-graph is a directed graph.

• One can define a (globular) directed $\omega$-graph (or directed $\mathrm{\infty }$-graph) in a coalgebraic fashion as follows: A directed $\omega$-graph $G$ consists of a collection $G_0$ of vertices and, for each pair of vertices $x$ and $y$, a directed $\omega$-graph $Hom(x,y)$. (This is a definition by structural coinduction?.) Can this be continued to a corecursive definition of $\mathrm{\infty }$-category?

See also

---

• $\omega$-graph

Mike Shulman: I had not seen this page before it was linked from finite category, but I don’t really like ”$n$-graph” as a name for these. When I see ”$n$-graph” I automatically think ”$n$-globular set”, and I expect the same will be true for many category theorists; I’ve seen the phrase used that way in print as well.

Eric: I really like the generality of this definition. Globular sets seem too limited to me, e.g. I like to have square 2-cells, but that is probably due to a less than perfect understanding. You can see some discussion and references on Revision 8 of this page. If we really decide to limit $n$-graph to globular sets we can certainly change the name.

Mike Shulman: But you don’t have square 2-cells here either! A square 2-cell would have to have the composite of two 1-cells as its source and target, but here your 2-cells only have a single 1-cell as their source and target. It sounds like maybe what you really want is an $n$-computad.

Eric: Thanks Mike! Todd mentioned computads in the discussion at finite category, but I didn’t realize we had a nice page: computad. Maybe we can think about how to clean things up. Based on the opening paragraph at computad, they do seem to be what I was after. I need to do some homework now. Thanks again.