\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{digraph} \vspace{.5em} \hrule \vspace{.5em} 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]]. \vspace{.5em} \hrule \vspace{.5em} $\,$ \hypertarget{graph_theory}{}\paragraph*{{Graph Theory}}\label{graph_theory} [[!include graph theory - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definition_and_basic_notions}{Definition and basic notions}\dotfill \pageref*{definition_and_basic_notions} \linebreak \noindent\hyperlink{categorical_properties_of_}{Categorical properties of $\mathsf{Dgr}$}\dotfill \pageref*{categorical_properties_of_} \linebreak \noindent\hyperlink{paths_trails_and_cycles}{Paths, trails, and cycles}\dotfill \pageref*{paths_trails_and_cycles} \linebreak \noindent\hyperlink{symmetrizing_and_weak_notions}{Symmetrizing and ``weak'' notions}\dotfill \pageref*{symmetrizing_and_weak_notions} \linebreak \noindent\hyperlink{miscellaneous_notions}{Miscellaneous notions}\dotfill \pageref*{miscellaneous_notions} \linebreak \noindent\hyperlink{remarks_on_the_definitions}{Remarks on the definitions}\dotfill \pageref*{remarks_on_the_definitions} \linebreak \noindent\hyperlink{uses_of_digraphs_in_category_theory}{Uses of digraphs in category theory}\dotfill \pageref*{uses_of_digraphs_in_category_theory} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} In combinatorics, a \textbf{digraph} (a shortening of \emph{[[directed graph]]}) consists of a [[set]] and a [[binary relation]] on that set that is [[irreflexive relation|irreflexive]]. The elements of the set are called \emph{nodes} or \emph{vertices}, and elements of the relation are called \emph{edges} or \emph{arcs}; the idea is that whenever an ordered pair $(x, y)$ belongs to the relation, then we depict it as an arrow or directed edge going from node $x$ to node $y$. The irreflexivity condition means there is never an edge from a node to itself. \hypertarget{definition_and_basic_notions}{}\subsection*{{Definition and basic notions}}\label{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. \begin{defn} \label{Digraph}\hypertarget{Digraph}{} \textbf{(digraph)} A \emph{digraph} is a [[pair]] $(V,A)$ of [[sets]], with $A\subseteq (V\times V)\setminus\{ (v,v)\colon v\in V\}$. Here, $V\times V$ denotes the [[product]], and ${}\setminus{}$ the [[relative complement]] in the [[category of sets]]. The elements of $V$ are called [[vertices]], the elements of $A$ are called [[arcs]]. For $a = (v, w)$ an arc, we call $v$ the \emph{source} of $a$ and $w$ the \emph{target} of $a$, also denoted $s(a)$ and $t(a)$ respectively. A \emph{morphism} from a digraph $(V, A)$ to a digraph $(V', A')$ is a function $f: V \to V'$ such that $(f(v), f(w)) \in A'$ whenever $(v, w) \in A$. Digraphs and their morphisms form a [[category]] denoted $\mathsf{Dgr}$. \end{defn} A digraph $(V, A)$ may be regarded as a [[quiver]] in an evident way, with source and target functions $s, t: A \rightrightarrows V$. It is straightforward that $\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, b$ where $s(a) = s(b)$ and $t(a) = t(b)$. Some useful examples of digraphs are based on [[ordinals]]: \begin{example} \label{ExampleDigraph}\hypertarget{ExampleDigraph}{} If $\alpha$ is an ordinal, we may form a digraph $(V, A)$ where $V$ is the underlying set of $\alpha$ and $A$ is the relation $\{(i, i+1): i, i+1 \in \alpha\}$. We call this an \emph{ordinal digraph} and denote it by the ordinal itself. \end{example} \begin{defn} \label{Walk}\hypertarget{Walk}{} \textbf{(walk in a digraph)} Suppose $D=(V,A)$ is a digraph. A \emph{walk in $D$} is a digraph-morphism $\alpha \to D$ where $\alpha$ is an ordinal digraph. \end{defn} Notice that for $\alpha = 1$, the hom-set $\mathsf{Dgr}(1, D)$ may be identified with the set of vertices of $D$. The definition of graph morphism implies that the underlying set functor $U = \mathsf{Dgr}(1, -): \mathsf{Dgr} \to Set$ is [[faithful functor|faithful]], and realizes $\mathsf{Dgr}$ as a [[concrete category]]. For $\alpha = 2$, the hom-set $\mathsf{Dgr}(2, D)$ may be identified with the set of arcs of $D$. However, the arc-set functor $\mathsf{Dgr}(2, -): \mathsf{Dgr} \to Set$ is very far from being faithful. If we let $C$ denote the full subcategory of $\mathsf{Dgr}$ consisting of the ordinal digraphs $1, 2$, then the inclusion $i: C \hookrightarrow \mathsf{Dgr}$ induces a functor $\mathsf{Dgr} \to Set^{C^{op}} = Quiv$ according to the usual ``[[nerve]]'' construction \begin{displaymath} \mathsf{Dgr} \to Set^{C^{op}} \end{displaymath} \begin{displaymath} D \mapsto (c \mapsto \mathsf{Dgr}(i c, D)) \end{displaymath} and this nerve functor is exactly the full embedding $\mathsf{Dgr} \to Quiv$. Since full embeddings reflect and preserve isomorphisms, a digraph morphism $f: D \to D'$ is an isomorphism iff the vertex-function $\mathsf{Dgr}(1, f)$ and arc-function $\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 $\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: \begin{defn} \label{WalkElementary}\hypertarget{WalkElementary}{} \textbf{(walk in a digraph; elementary definition)} Suppose $D=(V,A)$ is a digraph. A \emph{walk} in $D$ consists of \begin{itemize}% \item a [[sequence]] $P\colon\alpha\rightarrow V$, with $\alpha\leq\omega$, \end{itemize} such that \begin{itemize}% \item for all $i\in\alpha$, if $i+1\in\alpha$, then $(P(i),P(i+1))\in A$. \end{itemize} The phrase \emph{$\alpha$-vertex path} means any \emph{path whose domain is $\alpha$}. \end{defn} Some special cases: If $\alpha=0$, then $P$ is called \emph{the empty walk}. We have already seen that a $1$-walk is tantamount to a vertex, and that a 2-walk is tantamount to an edge. We call a walk $\omega \to D$ a \emph{ray} in $D$. \begin{example} \label{cycle}\hypertarget{cycle}{} Another useful example of a digraph is a finite [[cyclic order]]. For each $n \geq 2$, there is a digraph $Z_n$ whose vertex set is the underlying set of the finite cyclic group $\mathbb{Z}/n$, and whose arc relation is the set $\{(i, i+1): i \in \mathbb{Z}/n\}$. \end{example} \hypertarget{categorical_properties_of_}{}\subsection*{{Categorical properties of $\mathsf{Dgr}$}}\label{categorical_properties_of_} The category $\mathsf{Dgr}$ is not especially well-behaved for a category theorist. For example, it doesn't have a terminal object (no, the ordinal digraph $1$ 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 $\mathsf{Dgr}$. Such limits are easy to compute because $Quiv$, being a presheaf topos $Set^{C^{op}}$, has limits (and colimits) that are computed pointwise/objectwise. It follows from these observations that $\mathsf{Dgr}$ has pullbacks which are simply $Quiv$-pullbacks; they are computed objectwise at the objects $c = 1, 2$, i.e., one simply takes pullbacks in $Set$ at each of the vertex and edge levels. In our development, it will be useful to characterize various classes of [[monomorphisms]] in $\mathsf{Dgr}$. We begin with plain monomorphisms. \begin{prop} \label{Mono}\hypertarget{Mono}{} A morphism of digraphs $f: D \to D'$ is monic iff its underlying function $U(f)$ is monic ([[injective function|injective]]). \end{prop} \begin{proof} It is well-known that faithful functors $U$ reflect monomorphisms and epimorphisms. For suppose $U(f)$ is monic. Given a diagram in $\mathsf{Dgr}$ of the form \begin{displaymath} C \underoverset{h}{g}{\rightrightarrows} D \stackrel{f}{\to} D' \end{displaymath} if we have $f \circ g = f \circ h$ then $U(f) \circ U(g) = U(f) \circ U(h)$, whence $U(g) = U(h)$ by monicity of $U(f)$. Since $U$ is faithful, it follows that $g = h$; therefore $f$ is monic. The argument for epimorphisms is dual. For the other direction, use the fact that $U = \mathsf{Dgr}(1, -)$ is representable. It follows immediately from the definition of monomorphism that representable functors preserve monomorphisms, so if $f$ is monic, then so is $U(f)$. \end{proof} (Still to come: characterization of regular monomorphisms.) \hypertarget{paths_trails_and_cycles}{}\subsection*{{Paths, trails, and cycles}}\label{paths_trails_and_cycles} \begin{defn} \label{Path}\hypertarget{Path}{} \textbf{(path in a digraph)} Suppose $D=(V,A)$ is a digraph. A \emph{path} in $D$ is a walk $P: \alpha \to D$ whose underlying function is [[injection|injective]]. \end{defn} Or what is the same, that $\mathsf{Dgr}(1, P)$ is a [[monomorphism]] in $Set$. In view of Proposition \ref{Mono}, 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] \to X$ into a [[topological space]], where there is no assumption that its underlying function is injective.) \begin{defn} \label{Trail}\hypertarget{Trail}{} \textbf{(trail in a digraph)} Suppose $D=(V,A)$ is a digraph. A \emph{trail} in $D$ is a walk $\alpha\overset{P}{\longrightarrow}V$ such that the [[partial function]] $e_P: \alpha\rightarrow A$ with $e_P(i)=(P(i),P(i+1))$ is injective. \end{defn} The domain of $e_P$ is canonically identified with the arc set of $\alpha$, and the trail condition is equivalent to saying that $\mathsf{Dgr}(2, P)$ (which we again denote as $e_P$), as a function between edge sets $\mathsf{Dgr}(2, \alpha) \to \mathsf{Dgr}(2, D)$, is a monomorphism in $Set$. We have the following easy result. \begin{prop} \label{PathsAreTrails}\hypertarget{PathsAreTrails}{} In a digraph $D$, every path is a trail. \end{prop} \begin{proof} Since we just observed that a path $P$ is the same as a monic walk, and since representable functors like $\mathsf{Dgr}(2, -)$ preserve monomorphisms, it follows that $e_P = \mathsf{Dgr}(2, P)$ is a monomorphism. \end{proof} Continuing the theme of monic digraph morphisms, we introduce the notion of cycle: \begin{defn} \label{}\hypertarget{}{} An $n$-\emph{cycle} in a digraph $D$ is a monic morphism $P: Z_n \to D$ (see Example \ref{cycle}). A \emph{cycle} in $D$ is just an $n$-cycle in $D$ for some $n$. A digraph $D$ is \emph{acyclic} if it admits no cycles. \end{defn} There is a natural bijection between digraph morphisms $C: Z_n \to D$ and walks $P: \{0, \ldots, n\} \to D$ such that $P(0) = P(n)$. Indeed we have a digraph quotient map $q: \{0, \ldots, n\} \to Z_n$ defined as the mapping $i \mapsto i \mod n$, and the walk associated with $C: Z_n \to D$ is $P = C \circ q$. The map $q$ induces a bijection on arcs: \begin{displaymath} \mathsf{Dgr}(2, q): \mathsf{Dgr}(2, \{0, \ldots, n\}) \stackrel{\sim}{\to} \mathsf{Dgr}(2, Z_n). \end{displaymath} Thus if $C: Z_n \to D$ is \emph{monic}, we have a composite injective map in $Set$, \begin{displaymath} \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), \end{displaymath} which implies that the walk $P$ associated with a cycle $C: Z_n \to D$ is a trail. \hypertarget{symmetrizing_and_weak_notions}{}\subsection*{{Symmetrizing and ``weak'' notions}}\label{symmetrizing_and_weak_notions} For various digraph (directed graph) notions above, it can be useful to consider parallel notions for \emph{undirected} graphs. A slick method for doing this is by invoking a ``symmetrizing'' [[functor]] construction. \begin{defn} \label{}\hypertarget{}{} For a digraph $D$, we define $Symm(D)$ to have the same vertices as $D$, and the arc relation to be the symmetric closure of the arc relation of $D$. In other words, $(v, w)$ is an arc of $Symm(D)$ iff $(v, w)$ or $(w, v)$ is an arc of $D$. \end{defn} Clearly the symmetric closure of an irreflexive relation remains irreflexive, so $Symm(D)$ is again a digraph, and the assignment $D \mapsto Symm(D)$ is the object part of an obvious functor $Symm: \mathsf{Dgr} \to \mathsf{Dgr}$. Also the monomorphism $D \to Symm(D)$ that is the identity on vertices is the component $u_D$ of a [[natural transformation]] \begin{displaymath} u: 1_\mathsf{Dgr} \to Symm. \end{displaymath} \begin{theorem} \label{}\hypertarget{}{} The functor $Symm$ carries an [[idempotent monad]] structure. \end{theorem} \begin{proof} It is clear that $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)$ is also an identity map: $u_{Symm(D)} = Symm(u_D)$. The multiplication $m: Symm^2 \to Symm$ of the monad is defined by taking the inverse: $m = u_{Symm}^{-1}$. Then $m$ is natural and the unit law $m \circ u_{Symm} = 1$ is automatic; the other unit law $m \circ Symm(u_D)$ follows. The associativity of $m$ follows by inverting a naturality square for $u$. \end{proof} Morally we may consider the category of undirected graphs to be the category of algebras over the monad $Symm$. In any case, this is a full subcategory of $\mathsf{Dgr}$ consisting of digraphs of the form $Symm(D)$. We proceed to ``weaken'' various of the notions above to take into account the undirected graph context, simply by applying the functor $Symm$. For example: \begin{itemize}% \item If $\alpha$ is an ordinal digraph, a \emph{weak walk} $\alpha \to D$ is defined to be a walk $\alpha \to Symm(D)$. \end{itemize} (Obviously, a weak walk $\alpha \to D$ need not be literally a walk $\alpha \to D$; cf. [[red herring principle]].) Alternatively, we could define a weak walk to be a digraph morphism $Symm(\alpha) \to Symm(D)$ where $\alpha$ is an ordinal digraph: the two ways of defining weak walks are (naturally) equivalent. Similarly, \begin{itemize}% \item A \emph{weak trail} $\alpha \to D$ is defined to be a trail $\alpha \to Symm(D)$. \item A \emph{weak cycle} $Z_n \to D$ is defined to be a cycle $Z_n \to Symm(D)$. \end{itemize} \hypertarget{miscellaneous_notions}{}\subsection*{{Miscellaneous notions}}\label{miscellaneous_notions} In \hyperlink{MO277288}{contemporary} mathematics, ordered pairs $(x,y)$, $(y,x)$ are called \emph{antiparallel arcs}. \begin{defn} \label{Neighbourhoods}\hypertarget{Neighbourhoods}{} \textbf{(in-neighborhood, out-neighbourhood)} Suppose $D=(V,A)$ is a digraph and $v\in V$. The \emph{in-neighborhood} of $v$ in $D$, denoted $N^{\rightarrow}_D(v)$, is the set $\{ u\in V\colon (u,v)\in A\}$. The \emph{out-neighborhood} of $v$ in $D$, denoted $N^{\leftarrow}_D(v)$, is the set $\{ u\in V\colon (v,u)\in A\}$. \end{defn} We note that the rationale for the slightly non-standard notation $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. \begin{defn} \label{Degrees}\hypertarget{Degrees}{} \textbf{(in-degree, out-degree)} Suppose $D=(V,A)$ is a digraph and $v\in V$. The \emph{in-degree} of $v$ in $D$, denoted $d^{\rightarrow}_D(v)$, is the [[cardinality]] of the in-neighborhood of $v$ in $D$. The \emph{out-degree} is defined analogously. \end{defn} The axiom implies---digraphs being \emph{irreflexive}--- that always $\neg \, (P(i)=P(i+1))$. Walks are only allowed to be non-injective \emph{every other step}, so to speak. \begin{example} \label{TheLeastInjectiveWalk}\hypertarget{TheLeastInjectiveWalk}{} In a sense the \emph{least injective} walk is obtained by considering any digraph containing a \emph{2-cycle} (see below) $C$, taking $\alpha=\omega$ and defining $P$ to alternate back and forth on $C$ forever. This walk has a two-element image. \end{example} \begin{defn} \label{StartAndEndVertices}\hypertarget{StartAndEndVertices}{} \textbf{(start vertex, $A$-$B$-walk in a digraph)} Suppose $D=(V,A)$ is a digraph. Suppose $\alpha\overset{P}{\rightarrow} V$ is a non-empty walk in $D$. Then $P(0)$ is called the \emph{start vertex} of $P$. Suppose that $A,B$ are [[subsets]] of $V$, not necessarily disjoint. Then $P$ is an $A$--$B$-path if and only if $\alpha\gt 0$ is a finite ordinal and $P(0)\in A$, $P(\alpha-1)\in B$ and $0\lt i\lt \alpha-1$ implies $\neg\, (P(i)\in A\cup B)$. If $A=\{a\}$ and $B=\{b\}$ are singletons, one also writes $a$--$b$-path for \emph{$\{a\}$--$\{b\}$-path}. \end{defn} Discussion of weak trails from a previous revision mentioned Power's \hyperlink{Power1990}{proof} of unique interpretability of [[pasting schemes]]. The standard term in topology for a path which is \emph{free of self-intersections} is [[arc]] (eg \hyperlink{Kowalksky65}{Kowalksky 1965}, Definition 29b). As a saving grace, the standard way to rigorously define the arcs of \emph{plane} digraphs uses precisely the topological [[arcs]]. Allowing 2-cycles, yet neither loops nor parallel arcs, has become a standard meaning of \emph{digraph} in combinatorics. \begin{defn} \label{Acyclic}\hypertarget{Acyclic}{} \textbf{(acyclic digraph (DAG); classical definition)} Suppose $D=(V,A)$ is a digraph. Then $D$ is called \emph{acyclic} if and only if there does not exist any cycle in $D$. A usual abbreviation in combinatorics for \emph{acyclic directed graph} is \emph{DAG}. \end{defn} Here, ``classical'' refers to the negative definition. The set of all weak cycles of a digraph $D$ is denoted $\mathrm{WeCy}(D)$. The following non-standard definition is useful in when constructing proofs of Power's pasting theorem: \begin{defn} \label{ConstructiveAcyclic}\hypertarget{ConstructiveAcyclic}{} \textbf{(constructive acyclic digraph (cDAG))} A \emph{constructive acyclic digraph} is a triple $D=(V,A,z)$ of data \begin{itemize}% \item a digraph $(V,A)$ \item a function $z\colon\mathrm{WeCy}(D)\rightarrow V$ \end{itemize} subject to the axioms \begin{itemize}% \item for each $P\in \mathrm{WeCy}(D)$, $z(P) \in \mathrm{image}(P)$ \item for each $P\in \mathrm{WeCy}(D)$, if ( $u\in \mathrm{image}(P)$ [[and]] ( $(u,z(P))\in A$ [[or]] $(z(P),u)\in A$ ) ) , then $(u,z(P))\in A$. \end{itemize} \end{defn} In words, the axioms mean that $z$ gives us one vertex on any given weak cycle $P$ whose out-degree \emph{on $P$} is two. Then $z(P)$ witnesses $P$`s not being a cycle. Evidently, a (classical) DAG can usually be \emph{made} a cDAG in many ways: there usually are many functions $z$ 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 \emph{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)\in A$''. The following concept appears (under another name) in \hyperlink{Power1990}{Power's proof}: \begin{defn} \label{King}\hypertarget{King}{} \textbf{(king, coking, $d$-king, $d$-coking, $\omega$-king, $\omega$-coking)} Suppose $D=(V,A)$ is a digraph. A vertex $v$ of $D$ is a \emph{king} (resp. \emph{coking}) of $D$ if and only if $(v,w)\in A$ (resp. $(w,v)\in A$) for all $w\in V\setminus\{v\}$. For any finite [[cardinal number|cardinal]] $d$, a vertex $v$ of $D$ is a \emph{$d$-king} if and only if each vertex of $D$ can be reached along a \emph{path}, starting with $v$, the path having at most $d$ arcs. For any finite [[cardinal number|cardinal]] $d$, a vertex $v$ of $D$ is a \emph{$d$-coking} if and only if for each $u\in V$ there exists at least one \emph{path} starting with $u$ and ending with $v$ and having at most $d$ arcs. A vertex $v$ of $D$ is an \emph{$\omega$-king} if and only if each vertex of $D$ can be reached along a path of $D$, starting with $v$, and having \emph{any finite} number of arcs. A vertex $v$ of $D$ is an \emph{$\omega$-coking} if and only if for each $u\in V$ there is at least one path of $D$, starting with $u$, ending with $v$, and having \emph{any finite} number of arcs. \end{defn} The term \emph{$\omega$-king} is a natural variant of the usual term \emph{$k$-king} in digraph theory. By definition, for each $k\in\omega$, each $k$-(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 \hyperlink{Power1990}{Power's proof}, non-equality of the king and the coking \emph{must be made a separate axiom} in the definition of what Power calls \emph{plane graph with source and sink}). \begin{defn} \label{PlaneDigraph}\hypertarget{PlaneDigraph}{} \textbf{(plane digraph)} A \emph{plane digraph} consists of the data \begin{itemize}% \item a subset $V\subseteq\mathbb{R}^2$ of the [[plane]] \item a [[set]] $A$ of [[arcs]] (in the usual topological sense), each $a\in A$ of the form $[0,1]\overset{a}{\rightarrow}\mathbb{R}^2$ \end{itemize} and the axioms (v.connect) for each $a\in A$, $a(0)\in V$ and $a(1)\in V$, (free.interior) if $a\in A$ and $0\lt t\lt 1$, then $\neg\,(a(t)\in V)$, (not.par) if $a,a'\in A$ and if $a(0) = a'(0)$ and $a(1) = a'(1)$, then $a=a'$, (disjoint.interiors) if $a,a'\in A$ and ( $\exists t:[0,1]$, $0\lt t \lt 1$ and $\exists t':[0,1]$, $0 \lt t' \lt 1$ and $a(t)=a(t')$ ), then $a=a'$. \end{defn} Note that plane digraphs are often introduced into a context like (abstract) digraphs are, i.e. by writing $D=(V,A)$, although \begin{itemize}% \item the type of $D=(V,A)$ is invisible from this notation (it may be a \emph{digraph} or a \emph{plane digraph}) \item for a plane digraph $D=(V,A)$ we do not in general have $A\subseteq V\times V$. \end{itemize} We make use of the treatment of \emph{undirected} plane graphs given in (\hyperlink{DiestelGraphTheoryFourthEd}{Diestel}, Chapter 4), with some adaptations made for the present purposes: \begin{itemize}% \item here, \emph{arc} means arc in the usual topological sense, without exception, while, since the author focuses on undirected graphs, in \hyperlink{DiestelGraphTheoryFourthEd}{Diestel}, ``arc'' is defined to be a [[subset]] of the [[plane]], in particular is not parametrized, in particular does not carry \emph{directional information} (compare def. \ref{AbstractDigraphOfAPlaneDigraph} where said information is used). \item in (\hyperlink{DiestelGraphTheoryFourthEd}{Diestel}, Chapter 4), both $V$ and $A$ in the definition of plane graphs are required to be [[finite sets]]. Here we make no such restriction (cf. \ref{ExamplePlaneDigraph}). \item 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 \emph{faces}, and also \hyperlink{Munkres2000}{Munkres 2000}. \end{itemize} \begin{example} \label{ExamplePlaneDigraph}\hypertarget{ExamplePlaneDigraph}{} 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:=\{\varphi\in\mathbb{R}\colon 0\le \varphi\lt 2\pi,\quad \varphi\in\mathbb{Q} \}$, $D=(V,A)$ with $V:=\{(0,0)\} \cup \{ ( \cos( \varphi ) , \sin( \varphi ) ) \colon \varphi\in M \}$ and $a(\varphi)\colon [0,1]\rightarrow\mathbb{R}^2$ with $a(\varphi)(t) = ( t\cdot\cos(\varphi), t\cdot \sin(\varphi) )$ and $A:= \{ a(\varphi)\colon \varphi\in M \}$. Note that this example (0) is not a [[pasting scheme|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 \emph{infinite star}. \end{example} Applications of the following standard concept are e.g. the study of [[maps]] on [[surfaces]], and Power's (\hyperlink{Power1990}{proof}) of unique interpretability of [[pasting schemes]]: \begin{defn} \label{Face}\hypertarget{Face}{} \textbf{(face of a plane digraph)} Suppose $D=(V,A)$ is a plane digraph. The \emph{set of faces of $D$}, denoted $\mathrm{Fa}(D)$, is the set of [[connected components]], in the sense of \href{Introduction+to+Topology+--+1#subspaces}{Section 7}, of the [[relative complement]] $\mathbb{R}^2\setminus\bigcup\{ \mathrm{im}(a) \colon a\in A \}$, where $\mathrm{im}(a)=\{ a(t)\colon 0\leq t\leq 1 \}$. A \emph{face of $D$} is a \emph{member of the set $\mathrm{Fa}(D)$}. Each face of $D$ is an open connected subspace of the plane. \end{defn} Of course one needs a map from \emph{plane digraphs} to (abstract) \emph{digraphs}: \begin{defn} \label{AbstractDigraphOfAPlaneDigraph}\hypertarget{AbstractDigraphOfAPlaneDigraph}{} \textbf{(the (abstract) digraph of a plane digraph)} Suppose $D=(V,A)$ is a plane digraph. Then $\mathrm{Dig}(D)=(V',A')$ is the digraph defined as follows: it has vertex set $V':=V$ and arc set $A' := \{ ( a(0) , a(1) ) \colon a\in A \}$. \end{defn} Note that by axiom (v.connect), $A'$ is a subset of $V\times V$, and because each $a$ is an topological arc, and, as such, injective, $A'$ is moreover disjoint from the diagonal $\{(v,v)\colon v\in V\}$, so $A'$ has the type required by def. \ref{Digraph}. \begin{defn} \label{DigraphTheoreticTermsForPlaneDigraph}\hypertarget{DigraphTheoreticTermsForPlaneDigraph}{} All digraph-theoretic technical terms like \emph{out-neighborhood}, \emph{outdegree} which are defined for \emph{digraphs} are defined for \emph{plane digraphs} $D$ by first applying the map $\mathrm{Dig}$ to $D$, then applying the digraph-theoretic definition, then applying the inverse of $\mathrm{Dig}$. \end{defn} A central technical tool in \hyperlink{Power1990}{Power's proof} are \emph{boundary walks}: boundary walks validate a form of the [[red herring principle]]: each boundary walk is a \emph{weak walk}, yet need not be a walk. The boundary walks one works with when using A.J. Power's \hyperlink{Power1990}{application} of plane digraphs to category theory are often weak \emph{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 \emph{bridgeless}. However, this is not generally true, and to have both \emph{walks} and \emph{trails} is not futile but necessary: a typical example of a pasting diagram occurring naturally in category theory are [[whiskering]] diagrams: the \emph{boundary trail} of the \emph{exterior} face of the typical whiskering diagram \emph{does} have arc-repetions, hence is not a trail but only a walk. \hypertarget{remarks_on_the_definitions}{}\subsection*{{Remarks on the definitions}}\label{remarks_on_the_definitions} The \emph{convention} to have digraph imply that there be no loops and no parallel arcs, and resort to other terms such as \emph{directed pseudograph} to signal loops or parallel arcs, is widespread in modern combinatorics. For example, see p. 2 of (\hyperlink{DG2nd}{Gutin and Bang-Jensen}), and Section 1.2 of (\hyperlink{DecompositionProof}{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 $A$ to contain elements of the form $(v,v)$. The terms \emph{walk}, \emph{trail} and \emph{path} are standard in modern combinatorics. They are in particular compatible with standard usage in the theory of \emph{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 \hyperlink{BondyMurtyFirstEdition}{Figure 1.8} illustrates precisely this convention). Many (e.g. \hyperlink{DG2nd}{p. 11} and \hyperlink{BondyMurtyFirstEdition}{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 \emph{only} because digraphs cannot have any parallel arcs: for digraphs, our definition and the vertex-arc-alternating definition of \hyperlink{DG2nd}{p. 11} are equivalent to all intents and purposes. There is, however a good reason why e.g. \hyperlink{BondyMurtyFirstEdition}{Bondy and Murty} use the latter definition: for them, a \emph{directed graph} is (cf. \hyperlink{BondyMurtyFirstEdition}{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\times V$) not a \emph{digraph} but a [[quiver]], and---evidently---if multiple parallel arcs are permitted, \emph{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), \emph{in a trail, arc-repetitions are forbidden}, and in a path, any repetition is forbidden. The perhaps oddly hybrid concept of \emph{trail} has a crucial role in A. J. Power's (\hyperlink{Power1990}{proof}) of unique interpretability of [[pasting schemes]]: any \emph{face} of a \emph{plane digraph} determines a \emph{boundary trail} which always is a \emph{weak trail}. Generically, such a \emph{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 $d$-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 \emph{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 \emph{plane digraphs} in this article. A reason for treating the concept of $\omega$-kings here is A. J. Power's proof (\hyperlink{Power1990}{Power 1990}) of a \emph{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 \emph{addition of $a$--$b$-paths}, which is one of the reasons why $A$--$B$-paths have been introduced. \hypertarget{uses_of_digraphs_in_category_theory}{}\subsection*{{Uses of digraphs in category theory}}\label{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 ((\hyperlink{Johnson1987}{Johnson 1987}, Chapter 2), (\hyperlink{Johnson1989}{Johnson 1989}, Section 2)) and Power's pasting schemes (\hyperlink{Power1990}{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 (\hyperlink{Power1990}{Power 1990}, Section 3), details will be found at [[pasting scheme]]. \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[geometric shape for higher structures]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item A. Bondy, U.S.R. Murty: Graph Theory with Applications. Fifth Printing. North Holland 1982. \end{itemize} \begin{itemize}% \item B. Csaba, D. K\"u{}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 \end{itemize} \begin{itemize}% \item R. Diestel, Graph Theory, 4. ed., Springer 2010 \item [[Gregory Gutin]], [[Jørgen Bang-Jensen]]: \emph{Digraphs: Theory, Algorithms and Applications}. Springer Monographs in Mathematics. Second Edition (2009) \end{itemize} \begin{itemize}% \item [[Michael Johnson]]: \emph{Pasting Diagrams in $n$-Categories with Applications to Coherence Theorems and Categories of Paths}, Doctoral Thesis, University of Sydney, 1987 \end{itemize} \begin{itemize}% \item [[Michael Johnson]]: \emph{The Combinatorics of $n$-Categorical Pasting}, Journal of Pure and Applied Algebra 62 (1989) \end{itemize} \begin{itemize}% \item 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 \end{itemize} \begin{itemize}% \item [[James Munkres]]: \emph{Topology}, Prentice Hall. Second Edition (2000) \end{itemize} \begin{itemize}% \item [[John Power]]: \emph{A 2-Categorical Pasting Theorem}, Journal of Algebra 129 (1990) \end{itemize} \begin{itemize}% \item H. J. Kowalksky: Topological Spaces. Academic Press. 1965. \end{itemize} [[!redirects digraphs]] \end{document}