nLab
digraph

Contents


This page is about the concept of directed graphs that is usual in combinatorics. For the notion of directed graph as commonly understood in category theory, see quiver. For some commentary on how the two formalizations relate to one another, see directed graph.


\,

Contents

Idea

In combinatorics, a digraph (a shortening of directed graph) consists of a set and a binary relation on that set that is irreflexive. The elements of the set are called nodes or vertices, and elements of the relation are called edges or arcs; the idea is that whenever an ordered pair (x,y)(x, y) belongs to the relation, then we depict it as an arrow or directed edge going from node xx to node yy. The irreflexivity condition means there is never an edge from a node to itself.

Definition and basic notions

In this section we collect some definitions that are fundamental to digraph theory, but presented largely from the point of view of category theory.

Definition

(digraph)

A digraph is a pair (V,A)(V,A) of sets, with A(V×V){(v,v):vV}A\subseteq (V\times V)\setminus\{ (v,v)\colon v\in V\}. Here, V×VV\times V denotes the product, and {}\setminus{} the relative complement in the category of sets. The elements of VV are called vertices, the elements of AA are called arcs. For a=(v,w)a = (v, w) an arc, we call vv the source of aa and ww the target of aa, also denoted s(a)s(a) and t(a)t(a) respectively.

A morphism from a digraph (V,A)(V, A) to a digraph (V,A)(V', A') is a function f:VVf: V \to V' such that (f(v),f(w))A(f(v), f(w)) \in A' whenever (v,w)A(v, w) \in A. Digraphs and their morphisms form a category denoted Dgr\mathsf{Dgr}.

A digraph (V,A)(V, A) may be regarded as a quiver in an evident way, with source and target functions s,t:AVs, t: A \rightrightarrows V. It is straightforward that Dgr\mathsf{Dgr} is (equivalent to) a full subcategory of the category of quivers Quiv. Of course most quivers are not digraphs since quivers can have parallel edges: distinct edges a,ba, b where s(a)=s(b)s(a) = s(b) and t(a)=t(b)t(a) = t(b).

Some useful examples of digraphs are based on ordinals:

Example

If α\alpha is an ordinal, we may form a digraph (V,A)(V, A) where VV is the underlying set of α\alpha and AA is the relation {(i,i+1):i,i+1α}\{(i, i+1): i, i+1 \in \alpha\}. We call this an ordinal digraph and denote it by the ordinal itself.

Definition

(walk in a digraph) Suppose D=(V,A)D=(V,A) is a digraph. A walk in DD is a digraph-morphism αD\alpha \to D where α\alpha is an ordinal digraph.

Notice that for α=1\alpha = 1, the hom-set Dgr(1,D)\mathsf{Dgr}(1, D) may be identified with the set of vertices of DD. The definition of graph morphism implies that the underlying set functor U=Dgr(1,):DgrSetU = \mathsf{Dgr}(1, -): \mathsf{Dgr} \to Set is faithful, and realizes Dgr\mathsf{Dgr} as a concrete category.

For α=2\alpha = 2, the hom-set Dgr(2,D)\mathsf{Dgr}(2, D) may be identified with the set of arcs of DD. However, the arc-set functor Dgr(2,):DgrSet\mathsf{Dgr}(2, -): \mathsf{Dgr} \to Set is very far from being faithful.

If we let CC denote the full subcategory of Dgr\mathsf{Dgr} consisting of the ordinal digraphs 1,21, 2, then the inclusion i:CDgri: C \hookrightarrow \mathsf{Dgr} induces a functor DgrSet C op=Quiv\mathsf{Dgr} \to Set^{C^{op}} = Quiv according to the usual “nerve” construction

DgrSet C op\mathsf{Dgr} \to Set^{C^{op}}
D(cDgr(ic,D))D \mapsto (c \mapsto \mathsf{Dgr}(i c, D))

and this nerve functor is exactly the full embedding DgrQuiv\mathsf{Dgr} \to Quiv. Since full embeddings reflect and preserve isomorphisms, a digraph morphism f:DDf: D \to D' is an isomorphism iff the vertex-function Dgr(1,f)\mathsf{Dgr}(1, f) and arc-function Dgr(2,f)\mathsf{Dgr}(2, f) are isomorphisms (which is in any case obvious from the definition of digraph morphism, but this underscores the general importance of walks).

Generally we will only be interested in walks αD\alpha \to D such that αω\alpha \leq \omega in the sense of ordinals; here ω\omega is of course the first infinite ordinal. Unwinding the definitions, here is an elementary description of such walks:

Definition

(walk in a digraph; elementary definition)

Suppose D=(V,A)D=(V,A) is a digraph. A walk in DD consists of

  • a sequence P:αVP\colon\alpha\rightarrow V, with αω\alpha\leq\omega,

such that

  • for all iαi\in\alpha, if i+1αi+1\in\alpha, then (P(i),P(i+1))A(P(i),P(i+1))\in A.

The phrase α\alpha-vertex path means any path whose domain is α\alpha.

Some special cases: If α=0\alpha=0, then PP is called the empty walk. We have already seen that a 11-walk is tantamount to a vertex, and that a 2-walk is tantamount to an edge. We call a walk ωD\omega \to D a ray in DD.

Example

Another useful example of a digraph is a finite cyclic order. For each n2n \geq 2, there is a digraph Z nZ_n whose vertex set is the underlying set of the finite cyclic group /n\mathbb{Z}/n, and whose arc relation is the set {(i,i+1):i/n}\{(i, i+1): i \in \mathbb{Z}/n\}.

Categorical properties of Dgr\mathsf{Dgr}

The category Dgr\mathsf{Dgr} is not especially well-behaved for a category theorist. For example, it doesn’t have a terminal object (no, the ordinal digraph 11 is not terminal), and it does not admit all coequalizers. In both cases the culprit is the irreflexivity condition.

It does however have products indexed over nonempty sets, and equalizers. These limits are computed as they are in Quiv, e.g., the quiver product of two digraphs is again a digraph and is their product in Dgr\mathsf{Dgr}. Such limits are easy to compute because QuivQuiv, being a presheaf topos Set C opSet^{C^{op}}, has limits (and colimits) that are computed pointwise/objectwise.

It follows from these observations that Dgr\mathsf{Dgr} has pullbacks which are simply QuivQuiv-pullbacks; they are computed objectwise at the objects c=1,2c = 1, 2, i.e., one simply takes pullbacks in SetSet at each of the vertex and edge levels.

In our development, it will be useful to characterize various classes of monomorphisms in Dgr\mathsf{Dgr}. We begin with plain monomorphisms.

Proposition

A morphism of digraphs f:DDf: D \to D' is monic iff its underlying function U(f)U(f) is monic (injective).

Proof

It is well-known that faithful functors UU reflect monomorphisms and epimorphisms. For suppose U(f)U(f) is monic. Given a diagram in Dgr\mathsf{Dgr} of the form

ChgDfDC \underoverset{h}{g}{\rightrightarrows} D \stackrel{f}{\to} D'

if we have fg=fhf \circ g = f \circ h then U(f)U(g)=U(f)U(h)U(f) \circ U(g) = U(f) \circ U(h), whence U(g)=U(h)U(g) = U(h) by monicity of U(f)U(f). Since UU is faithful, it follows that g=hg = h; therefore ff is monic. The argument for epimorphisms is dual.

For the other direction, use the fact that U=Dgr(1,)U = \mathsf{Dgr}(1, -) is representable. It follows immediately from the definition of monomorphism that representable functors preserve monomorphisms, so if ff is monic, then so is U(f)U(f).

(Still to come: characterization of regular monomorphisms.)

Paths, trails, and cycles

Definition

(path in a digraph)

Suppose D=(V,A)D=(V,A) is a digraph. A path in DD is a walk P:αDP: \alpha \to D whose underlying function is injective.

Or what is the same, that Dgr(1,P)\mathsf{Dgr}(1, P) is a monomorphism in SetSet. In view of Proposition , we may also define a path to be a monic walk. (Notice this digraph concept of path is at variance with the concept of path in topology which is simply a continuous map [0,1]X[0, 1] \to X into a topological space, where there is no assumption that its underlying function is injective.)

Definition

(trail in a digraph) Suppose D=(V,A)D=(V,A) is a digraph. A trail in DD is a walk αPV\alpha\overset{P}{\longrightarrow}V such that the partial function e P:αAe_P: \alpha\rightarrow A with e P(i)=(P(i),P(i+1))e_P(i)=(P(i),P(i+1)) is injective.

The domain of e Pe_P is canonically identified with the arc set of α\alpha, and the trail condition is equivalent to saying that Dgr(2,P)\mathsf{Dgr}(2, P) (which we again denote as e Pe_P), as a function between edge sets Dgr(2,α)Dgr(2,D)\mathsf{Dgr}(2, \alpha) \to \mathsf{Dgr}(2, D), is a monomorphism in SetSet.

We have the following easy result.

Proposition

In a digraph DD, every path is a trail.

Proof

Since we just observed that a path PP is the same as a monic walk, and since representable functors like Dgr(2,)\mathsf{Dgr}(2, -) preserve monomorphisms, it follows that e P=Dgr(2,P)e_P = \mathsf{Dgr}(2, P) is a monomorphism.

Continuing the theme of monic digraph morphisms, we introduce the notion of cycle:

Definition

An nn-cycle in a digraph DD is a monic morphism P:Z nDP: Z_n \to D (see Example ). A cycle in DD is just an nn-cycle in DD for some nn. A digraph DD is acyclic if it admits no cycles.

There is a natural bijection between digraph morphisms C:Z nDC: Z_n \to D and walks P:{0,,n}DP: \{0, \ldots, n\} \to D such that P(0)=P(n)P(0) = P(n). Indeed we have a digraph quotient map q:{0,,n}Z nq: \{0, \ldots, n\} \to Z_n defined as the mapping iimodni \mapsto i \mod n, and the walk associated with C:Z nDC: Z_n \to D is P=CqP = C \circ q. The map qq induces a bijection on arcs:

Dgr(2,q):Dgr(2,{0,,n})Dgr(2,Z n).\mathsf{Dgr}(2, q): \mathsf{Dgr}(2, \{0, \ldots, n\}) \stackrel{\sim}{\to} \mathsf{Dgr}(2, Z_n).

Thus if C:Z nDC: Z_n \to D is monic, we have a composite injective map in SetSet,

Dgr(2,{0,,n})Dgr(2,q)Dgr(2,Z n)Dgr(2,C)Dgr(2,D),\mathsf{Dgr}(2, \{0, \ldots, n\}) \underoverset{\mathsf{Dgr}(2, q)}{\sim}{\to} \mathsf{Dgr}(2, Z_n) \underset{\mathsf{Dgr}(2, C)}{\to} \mathsf{Dgr}(2, D),

which implies that the walk PP associated with a cycle C:Z nDC: Z_n \to D is a trail.

Symmetrizing and “weak” notions

For various digraph (directed graph) notions above, it can be useful to consider parallel notions for undirected graphs. A slick method for doing this is by invoking a “symmetrizing” functor construction.

Definition

For a digraph DD, we define Symm(D)Symm(D) to have the same vertices as DD, and the arc relation to be the symmetric closure of the arc relation of DD. In other words, (v,w)(v, w) is an arc of Symm(D)Symm(D) iff (v,w)(v, w) or (w,v)(w, v) is an arc of DD.

Clearly the symmetric closure of an irreflexive relation remains irreflexive, so Symm(D)Symm(D) is again a digraph, and the assignment DSymm(D)D \mapsto Symm(D) is the object part of an obvious functor Symm:DgrDgrSymm: \mathsf{Dgr} \to \mathsf{Dgr}. Also the monomorphism DSymm(D)D \to Symm(D) that is the identity on vertices is the component u Du_D of a natural transformation

u:1 DgrSymm.u: 1_\mathsf{Dgr} \to Symm.
Theorem

The functor SymmSymm carries an idempotent monad structure.

Proof

It is clear that u Symm(D):Symm(D)Symm 2(D)u_{Symm(D)}: Symm(D) \to Symm^2(D) is an isomorphism (and even an identity map) because the operation of taking the symmetric closure of a relation is itself idempotent. Similarly Symm(u D)Symm(u_D) is also an identity map: u Symm(D)=Symm(u D)u_{Symm(D)} = Symm(u_D). The multiplication m:Symm 2Symmm: Symm^2 \to Symm of the monad is defined by taking the inverse: m=u Symm 1m = u_{Symm}^{-1}. Then mm is natural and the unit law mu Symm=1m \circ u_{Symm} = 1 is automatic; the other unit law mSymm(u D)m \circ Symm(u_D) follows. The associativity of mm follows by inverting a naturality square for uu.

Morally we may consider the category of undirected graphs to be the category of algebras over the monad SymmSymm. In any case, this is a full subcategory of Dgr\mathsf{Dgr} consisting of digraphs of the form Symm(D)Symm(D).

We proceed to “weaken” various of the notions above to take into account the undirected graph context, simply by applying the functor SymmSymm. For example:

  • If α\alpha is an ordinal digraph, a weak walk αD\alpha \to D is defined to be a walk αSymm(D)\alpha \to Symm(D).

(Obviously, a weak walk αD\alpha \to D need not be literally a walk αD\alpha \to D; cf. red herring principle.)

Alternatively, we could define a weak walk to be a digraph morphism Symm(α)Symm(D)Symm(\alpha) \to Symm(D) where α\alpha is an ordinal digraph: the two ways of defining weak walks are (naturally) equivalent.

Similarly,

  • A weak trail αD\alpha \to D is defined to be a trail αSymm(D)\alpha \to Symm(D).

  • A weak cycle Z nDZ_n \to D is defined to be a cycle Z nSymm(D)Z_n \to Symm(D).

Miscellaneous notions

In contemporary mathematics, ordered pairs (x,y)(x,y), (y,x)(y,x) are called antiparallel arcs.

Definition

(in-neighborhood, out-neighbourhood)

Suppose D=(V,A)D=(V,A) is a digraph and vVv\in V. The in-neighborhood of vv in DD, denoted N D (v)N^{\rightarrow}_D(v), is the set {uV:(u,v)A}\{ u\in V\colon (u,v)\in A\}. The out-neighborhood of vv in DD, denoted N D (v)N^{\leftarrow}_D(v), is the set {uV:(v,u)A}\{ u\in V\colon (v,u)\in A\}.

We note that the rationale for the slightly non-standard notation N D (v)N^{\leftarrow}_D(v) is to have it be intuitively understandable: the arrow points away from the vertex and points to the letter which stands for the set which contains the out-neighbours.

Definition

(in-degree, out-degree)

Suppose D=(V,A)D=(V,A) is a digraph and vVv\in V. The in-degree of vv in DD, denoted d D (v)d^{\rightarrow}_D(v), is the cardinality of the in-neighborhood of vv in DD. The out-degree is defined analogously.

The axiom implies—digraphs being irreflexive— that always ¬(P(i)=P(i+1))\neg \, (P(i)=P(i+1)). Walks are only allowed to be non-injective every other step, so to speak.

Example

In a sense the least injective walk is obtained by considering any digraph containing a 2-cycle (see below) CC, taking α=ω\alpha=\omega and defining PP to alternate back and forth on CC forever. This walk has a two-element image.

Definition

(start vertex, AA-BB-walk in a digraph)

Suppose D=(V,A)D=(V,A) is a digraph. Suppose αPV\alpha\overset{P}{\rightarrow} V is a non-empty walk in DD. Then P(0)P(0) is called the start vertex of PP. Suppose that A,BA,B are subsets of VV, not necessarily disjoint. Then PP is an AABB-path if and only if α>0\alpha\gt 0 is a finite ordinal and P(0)AP(0)\in A, P(α1)BP(\alpha-1)\in B and 0<i<α10\lt i\lt \alpha-1 implies ¬(P(i)AB)\neg\, (P(i)\in A\cup B). If A={a}A=\{a\} and B={b}B=\{b\} are singletons, one also writes aabb-path for {a}\{a\}{b}\{b\}-path.

Discussion of weak trails from a previous revision mentioned Power’s proof of unique interpretability of pasting schemes.

The standard term in topology for a path which is free of self-intersections is arc (eg Kowalksky 1965, Definition 29b). As a saving grace, the standard way to rigorously define the arcs of plane digraphs uses precisely the topological arcs.

Allowing 2-cycles, yet neither loops nor parallel arcs, has become a standard meaning of digraph in combinatorics.

Definition

(acyclic digraph (DAG); classical definition)

Suppose D=(V,A)D=(V,A) is a digraph. Then DD is called acyclic if and only if there does not exist any cycle in DD.

A usual abbreviation in combinatorics for acyclic directed graph is DAG.

Here, “classical” refers to the negative definition.

The set of all weak cycles of a digraph DD is denoted WeCy(D)\mathrm{WeCy}(D).

The following non-standard definition is useful in when constructing proofs of Power’s pasting theorem:

Definition

(constructive acyclic digraph (cDAG))

A constructive acyclic digraph is a triple D=(V,A,z)D=(V,A,z) of data

  • a digraph (V,A)(V,A)
  • a function z:WeCy(D)Vz\colon\mathrm{WeCy}(D)\rightarrow V

subject to the axioms

  • for each PWeCy(D)P\in \mathrm{WeCy}(D), z(P)image(P)z(P) \in \mathrm{image}(P)

  • for each PWeCy(D)P\in \mathrm{WeCy}(D), if ( uimage(P)u\in \mathrm{image}(P) and ( (u,z(P))A(u,z(P))\in A or (z(P),u)A(z(P),u)\in A ) ) , then (u,z(P))A(u,z(P))\in A.

In words, the axioms mean that zz gives us one vertex on any given weak cycle PP whose out-degree on PP is two. Then z(P)z(P) witnesses PP‘s not being a cycle. Evidently, a (classical) DAG can usually be made a cDAG in many ways: there usually are many functions zz one can specify and that satisfy the axioms. We are here not interested in describing or counting these possibilities, rather in doing things with a given cDAG.

There is an apparently inescapable arbitrariness in whether to favor out-neighbors or in-neighbor when defining constructive DAG. The above definition would to all intents and purposes be equivalent the one obtained by replacing the conclusion in the axiom with “then (z(P),u)A(z(P),u)\in A”.

The following concept appears (under another name) in Power’s proof:

Definition

(king, coking, dd-king, dd-coking, ω\omega-king, ω\omega-coking)

Suppose D=(V,A)D=(V,A) is a digraph. A vertex vv of DD is a king (resp. coking) of DD if and only if (v,w)A(v,w)\in A (resp. (w,v)A(w,v)\in A) for all wV{v}w\in V\setminus\{v\}.

For any finite cardinal dd, a vertex vv of DD is a dd-king if and only if each vertex of DD can be reached along a path, starting with vv, the path having at most dd arcs.

For any finite cardinal dd, a vertex vv of DD is a dd-coking if and only if for each uVu\in V there exists at least one path starting with uu and ending with vv and having at most dd arcs.

A vertex vv of DD is an ω\omega-king if and only if each vertex of DD can be reached along a path of DD, starting with vv, and having any finite number of arcs.

A vertex vv of DD is an ω\omega-coking if and only if for each uVu\in V there is at least one path of DD, starting with uu, ending with vv, and having any finite number of arcs.

The term ω\omega-king is a natural variant of the usual term kk-king in digraph theory. By definition, for each kωk\in\omega, each kk-(co)king is an ω\omega-(co)king. Of course, a vertex can be a king and a coking simultaneously. (Which is why e.g. in Power’s proof, non-equality of the king and the coking must be made a separate axiom in the definition of what Power calls plane graph with source and sink).

Definition

(plane digraph)

A plane digraph consists of the data

  • a subset V 2V\subseteq\mathbb{R}^2 of the plane
  • a set AA of arcs (in the usual topological sense), each aAa\in A of the form [0,1]a 2[0,1]\overset{a}{\rightarrow}\mathbb{R}^2

and the axioms

(v.connect) for each aAa\in A, a(0)Va(0)\in V and a(1)Va(1)\in V,

(free.interior) if aAa\in A and 0<t<10\lt t\lt 1, then ¬(a(t)V)\neg\,(a(t)\in V),

(not.par) if a,aAa,a'\in A and if a(0)=a(0)a(0) = a'(0) and a(1)=a(1)a(1) = a'(1), then a=aa=a',

(disjoint.interiors) if a,aAa,a'\in A and ( t:[0,1]\exists t:[0,1], 0<t<10\lt t \lt 1 and t:[0,1]\exists t':[0,1], 0<t<10 \lt t' \lt 1 and a(t)=a(t)a(t)=a(t') ), then a=aa=a'.

Note that plane digraphs are often introduced into a context like (abstract) digraphs are, i.e. by writing D=(V,A)D=(V,A), although

  • the type of D=(V,A)D=(V,A) is invisible from this notation (it may be a digraph or a plane digraph)

  • for a plane digraph D=(V,A)D=(V,A) we do not in general have AV×VA\subseteq V\times V.

We make use of the treatment of undirected plane graphs given in (Diestel, Chapter 4), with some adaptations made for the present purposes:

  • here, arc means arc in the usual topological sense, without exception, while, since the author focuses on undirected graphs, in Diestel, “arc” is defined to be a subset of the plane, in particular is not parametrized, in particular does not carry directional information (compare def. where said information is used).

  • in (Diestel, Chapter 4), both VV and AA in the definition of plane graphs are required to be finite sets. Here we make no such restriction (cf. ).

  • for ease of reference, we calibrate the point-set topological terminology according to Introduction to Topology (example: we will say “component” instead of “region”) when defining faces, and also Munkres 2000.

Example

An example of a plane digraph with countably infinite vertex set, and whose satisfying the axioms of plane digraphs is evident, is given by T:={φ:0φ<2π,φ}T:=\{\varphi\in\mathbb{R}\colon 0\le \varphi\lt 2\pi,\quad \varphi\in\mathbb{Q} \}, D=(V,A)D=(V,A) with V:={(0,0)}{(cos(φ),sin(φ)):φM}V:=\{(0,0)\} \cup \{ ( \cos( \varphi ) , \sin( \varphi ) ) \colon \varphi\in M \} and a(φ):[0,1] 2a(\varphi)\colon [0,1]\rightarrow\mathbb{R}^2 with a(φ)(t)=(tcos(φ),tsin(φ))a(\varphi)(t) = ( t\cdot\cos(\varphi), t\cdot \sin(\varphi) ) and A:={a(φ):φM}A:= \{ a(\varphi)\colon \varphi\in M \}. Note that this example (0) is not a pasting scheme in the sense of Power (already for the strong reason that in it there does not exist any ω\omega-coking), and (1), while large, it would make for a rather dull and vacuously-uniquely-interpretable pasting diagram: there are no arrows that could possibly be composed, let alone is there any 2-cell.

In combinatorics, this is sometimes referred to as an infinite star.

Applications of the following standard concept are e.g. the study of maps on surfaces, and Power’s (proof) of unique interpretability of pasting schemes:

Definition

(face of a plane digraph)

Suppose D=(V,A)D=(V,A) is a plane digraph. The set of faces of DD, denoted Fa(D)\mathrm{Fa}(D), is the set of connected components, in the sense of Section 7, of the relative complement 2{im(a):aA}\mathbb{R}^2\setminus\bigcup\{ \mathrm{im}(a) \colon a\in A \}, where im(a)={a(t):0t1}\mathrm{im}(a)=\{ a(t)\colon 0\leq t\leq 1 \}.

A face of DD is a member of the set Fa(D)\mathrm{Fa}(D). Each face of DD is an open connected subspace of the plane.

Of course one needs a map from plane digraphs to (abstract) digraphs:

Definition

(the (abstract) digraph of a plane digraph)

Suppose D=(V,A)D=(V,A) is a plane digraph. Then Dig(D)=(V,A)\mathrm{Dig}(D)=(V',A') is the digraph defined as follows: it has vertex set V:=VV':=V and arc set A:={(a(0),a(1)):aA}A' := \{ ( a(0) , a(1) ) \colon a\in A \}.

Note that by axiom (v.connect), AA' is a subset of V×VV\times V, and because each aa is an topological arc, and, as such, injective, AA' is moreover disjoint from the diagonal {(v,v):vV}\{(v,v)\colon v\in V\}, so AA' has the type required by def. .

Definition

All digraph-theoretic technical terms like out-neighborhood, outdegree which are defined for digraphs are defined for plane digraphs DD by first applying the map Dig\mathrm{Dig} to DD, then applying the digraph-theoretic definition, then applying the inverse of Dig\mathrm{Dig}.

A central technical tool in Power’s proof are boundary walks: boundary walks validate a form of the red herring principle: each boundary walk is a weak walk, yet need not be a walk.

The boundary walks one works with when using A.J. Power’s application of plane digraphs to category theory are often weak trails, “often” in the sense that most pasting diagrams one encounters in practice do not have any arc-repetitions. Equivalently, the 1-cells of usual pasting diagrams have an underlying undirected graphs with is bridgeless. However, this is not generally true, and to have both walks and trails is not futile but necessary: a typical example of a pasting diagram occurring naturally in category theory are whiskering diagrams: the boundary trail of the exterior face of the typical whiskering diagram does have arc-repetions, hence is not a trail but only a walk.

Remarks on the definitions

The convention to have digraph imply that there be no loops and no parallel arcs, and resort to other terms such as directed pseudograph to signal loops or parallel arcs, is widespread in modern combinatorics. For example, see p. 2 of (Gutin and Bang-Jensen), and Section 1.2 of (Csaba et al).

Unsurprisingly, while the convention that digraph implies that there be no parallel arrows has been widely adopted nowadays, there is a generous disregard for whether a digraph may contain loops. In this set-theoretical definition given above, this corresponds to the decision whether to allow AA to contain elements of the form (v,v)(v,v).

The terms walk, trail and path are standard in modern combinatorics. They are in particular compatible with standard usage in the theory of undirected graphs, in that upon forgetting (so to speak) the directions in the various definitions, one obtains the standard notions of walk, trail and path in (undirected) graph theory (for example Figure 1.8 illustrates precisely this convention).

Many (e.g. p. 11 and Chapter 1) modern reference define walks to be sequences whose codomain conains both vertices and arcs. For simplicity we do not do so. Having paths consist of vertices only, and letting the structure of the target space determine the axioms seems cleaner. We can afford to make this simplification only because digraphs cannot have any parallel arcs: for digraphs, our definition and the vertex-arc-alternating definition of p. 11 are equivalent to all intents and purposes. There is, however a good reason why e.g. Bondy and Murty use the latter definition: for them, a directed graph is (cf. 10.1, though Bondy–Murty’s formalization is different from usual quivers and a rare hybrid between purely functional and purely relation-theoretic formalizations: they use maps with codomain set V×VV\times V) not a digraph but a quiver, and—evidently—if multiple parallel arcs are permitted, then a vertex-sequence does not contain enough information to define a “walk”. Upon stepping from one vertex to the next, a vertex sequence by itself cannot tell one which parallel arc to pick.

Needless to say (since given by the definitions), in a trail, arc-repetitions are forbidden, and in a path, any repetition is forbidden.

The perhaps oddly hybrid concept of trail has a crucial role in A. J. Power’s (proof) of unique interpretability of pasting schemes: any face of a plane digraph determines a boundary trail which always is a weak trail.

Generically, such a boundary trail has many vertex-repetitions, but it never has any arc-repetition.

The terminology “king” above is standard in modern digraph theory; the term “coking” is not, but in tune with category-theoretic usages. The term “ω\omega-king” appears not to be attested but is in tune with a standard notion of dd-king in digraph-theory, and also with some usages in mathematics which let ω\omega signal that some parameter is unconstrained (cf. omega-category omega-groupoid).

The choice of definitions documented here is biased towards (one of) the uses digraphs are put to in category theory, in particular in giving a rigorous justification of pasting diagrams. The most salient example of this is the emphasis given to plane digraphs in this article.

A reason for treating the concept of ω\omega-kings here is A. J. Power’s proof (Power 1990) of a pasting theorem, a rigorous justification of the notational practice of pasting diagrams: therein, both ω\omega-kings and ω\omega-cokings play an important role (Power calls ω\omega-kings “sources” and ω\omega-cokings “sinks”; both these terms clash with two standard technical terms in, respectively, contemporary digraph theory and flow theory, which is why the alternative terms were chosen).

Moreover, Power makes crucial use of a concept of addition of aabb-paths, which is one of the reasons why AABB-paths have been introduced.

Uses of digraphs in category theory

One example of why digraphs are relevant to category theory are pasting schemes, which are a rigorous justification of the (older) notational practice of pasting diagrams. Pasting diagrams are fundamental to higher category theory: already the axioms for various notions of higher categories are formalized in terms of pasting diagrams. The formal justification of pasting diagrams was achieved in the late 1980. Note that there are more than one definition of pasting scheme in the literature. E.g. there are M. Johnson’s pasting schemes ((Johnson 1987, Chapter 2), (Johnson 1989, Section 2)) and Power’s pasting schemes (Power 1990). The definition which is strictly relevant to the present article is Power’s. He defines defines pasting schemes as a special kind of digraph (Power 1990, Section 3), details will be found at pasting scheme.

References

  • A. Bondy, U.S.R. Murty: Graph Theory with Applications. Fifth Printing. North Holland 1982.
  • B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures. Memoirs of the American Mathematical Society, 244 (2016), monograph 1154, 170 pages
  • R. Diestel, Graph Theory, 4. ed., Springer 2010

  • Gregory Gutin?, Jørgen Bang-Jensen?: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Second Edition (2009)

  • Michael Johnson?: Pasting Diagrams in nn-Categories with Applications to Coherence Theorems and Categories of Paths, Doctoral Thesis, University of Sydney, 1987
  • Michael Johnson?: The Combinatorics of nn-Categorical Pasting, Journal of Pure and Applied Algebra 62 (1989)
  • Manfred Weis (https://mathoverflow.net/users/31310/manfred-weis), Calculating Cost-Optimal 1-Factors in Digraphs, URL (version: 2017-07-26): https://mathoverflow.net/q/277288
  • John Power: A 2-Categorical Pasting Theorem, Journal of Algebra 129 (1990)
  • H. J. Kowalksky: Topological Spaces. Academic Press. 1965.

Last revised on September 1, 2017 at 14:51:32. See the history of this page for a list of all contributions to it.