nLab directed (n,r)-graph

Idea

The underlying higher directed graph of an $(n, r)$-category.

Definition

Directed (n,r)-pseudographs

For finite $r$, directed $(n,r)$-pseudographs are defined inductively as follows:

Definition

For $-2 \leq n \leq \infty$, a directed $(n,0)$-pseudograph is an ∞-groupoid that is n-truncated: an n-groupoid.

For $0 \leq r \lt \infty$, a directed $(n+1,r+1)$-pseudograph is an (n+1)-groupoid $G$ such that for every object $A$ and $B$, called a vertex, in $G$, there is a directed $(n,r)$-pseudograph of edges $Edge(A, B)$ between $A$ and $B$.

where $\infty + 1 = \infty$

For the case $r = \infty$, directed $(n, \infty)$-pseudographs are defined coinductively as follows:

Definition

For $-2 \leq n \leq \infty$, a directed $(n,\infty)$-pseudograph is an n-groupoid $G$ such that for every object $A$ and $B$, called a vertex, in $G$, there is a directed $(n,\infty)$-pseudograph of edges $Edge(A, B)$ between $A$ and $B$.

Directed (n,r)-multigraphs

For finite $r$, directed $(n,r)$-multigraphs are defined inductively as follows:

Definition

For $-2 \leq n \leq \infty$, a directed $(n,0)$-multigraph is an ∞-groupoid that is n-truncated: an n-groupoid.

For $0 \leq r \lt \infty$, a directed $(n+1,r+1)$-multigraph is an (n+1)-groupoid $G$ such that for every object $A$ and $B$, called a vertex, in $G$, there is a directed $(n,r)$-multigraph of edges $Edge(A, B)$ between $A$ and $B$ such that given any vertex $A$, $Edge(A, A)$ is equivalent to the empty $\infty$-groupoid.

where $\infty + 1 = \infty$

For the case $r = \infty$, directed $(n, \infty)$-multigraphs are defined coinductively as follows:

Definition

For $-2 \leq n \leq \infty$, a directed $(n,\infty)$-multigraph is an n-groupoid $G$ such that for every object $A$ and $B$, called a vertex, in $G$, there is a directed $(n,\infty)$-multigraph of edges $Edge(A, B)$ between $A$ and $B$ such that given any vertex $A$, $Edge(A, A)$ is equivalent to the empty $\infty$-groupoid.

Note on terminology

Some authors use “directed (n,r)-graph” to mean what we refer here as a “directed (n,r)-pseudograph”.

The periodic table

Directed $(n,r)$-pseudographs

There is a periodic table of directed $(n,r)$-pseudographs:

$r$↓\$n$→	$-2$	$-1$	$0$	$1$	$2$	…	$\infty$
$0$	trivial	truth value	set	groupoid	2-groupoid	...	infinity groupoid
$1$	"	"	directed loop graph?	directed pseudograph	directed (2,1)-pseudograph	...	directed (infinity,1)-pseudograph
$2$	"	"	"	directed loop 2-graph	directed (2,2)-pseudograph	...	directed (infinity,2)-pseudograph
$3$	"	"	"	"	directed loop 3-graph	...	directed (infinity,3)-pseudograph
⋮	⋮	⋮	⋮	⋮	⋮	⋱	⋮
$\infty$	trivial	truth value	directed loop graph	directed loop 2-graph	directed loop 3-graph	...	directed loop infinity-graph

Directed $(n,r)$-multigraphs

There is a periodic table of directed $(n,r)$-multigraphs:

$r$↓\$n$→	$-2$	$-1$	$0$	$1$	$2$	…	$\infty$
$0$	trivial	truth value	set	groupoid	2-groupoid	...	infinity groupoid
$1$	"	"	directed graph	directed multigraph?	directed (2,1)-multigraph	...	directed (infinity,1)-multigraph
$2$	"	"	"	directed 2-graph	directed 2-multigraph	...	directed (infinity,2)-multigraph
$3$	"	"	"	"	directed 3-graph	...	directed (infinity,3)-multigraph
⋮	⋮	⋮	⋮	⋮	⋮	⋱	⋮
$\infty$	trivial	truth value	directed graph	directed 2-graph	directed 3-graph	...	directed infinity-graph

See also

• directed pseudograph

• pseudograph

• n-graph

• (n,r)-category

• coinduction