## Introduction

Consider this diagram

\[

\begin{array}{ccccc}

\bullet & \rightarrow & \bullet\\

\downarrow & & \downarrow\\

\bullet & \rightarrow & \bullet & \rightarrow & \bullet

\end{array}

\]

which consists of vertices (the dots) and arrows between the vertices. That is an example of a directed graph.

## Definitions

### Directed Graph

A **directed graph** is a set $V$ with a binary relation $\rightarrow$. By a binary relation we mean a subset of the Cartesian product $V\times V$. A **directed sub-graph** of $V$ is a subset $S$ of $V$ with a binary relation $\rightarrow_{S}$ such that for all $a,b$ in $S$, $a\rightarrow_{S}b$ if and only if $a\rightarrow b$ in $V$. An

**embedding** $f$ of a directed graph $\left(V_{1},\rightarrow_{1}\right)$ into a directed graph $\left(V_{2},\rightarrow_{2}\right)$ is a function from $V_{1}$ to $V_{2}$ such that, for all vertices $a,b$ in $V_{1}$, it follows $a\rightarrow_{1}b$ if and only if $f\left(a\right)\rightarrow_{2}f\left(b\right)$

### Infinite Chains

Here are two notions of an infinite chain in a directed graph. We will label one as “Def. 1” and the other as “Def. 2”.

**Def. 1**: An infinite chain in a directed graph $\left(V,\rightarrow\right)$ is a function $c$ from the natural numbers $\mathbb{N}$ to $V$ such that

- for all $i,j$ in $\mathbb{N}$, $i=j$ if and only if $c\left(i\right)=c\left(j\right)$;
- for all $i$ in $\mathbb{N}$, $c\left(i\right)\rightarrow c\left(i+1\right)$.

Condition (1) guarantees that there are no loops in the chain, that is, $v\rightarrow v$ for some vertex $v$ in the chain.

Before we introduce the other notion, we need to tell you what a **finite ****chain** of a directed graph $V$ is: it is a function $d$ from the collection $\left\{ 0,\ldots,n\right\} $, with $n$ a natural number, to $V$ such that (a) for all $i,j$ in the collection $\left\{ 0,\ldots,n\right\} $, $i=j$ if and only if $d\left(i\right)=d\left(j\right)$ and (b) for all $i$ in $\left\{ 0,\ldots,n-1\right\} $, $d\left(i\right)\rightarrow d\left(i+1\right)$.

**Def. 2**: An infinite chain in a directed graph $\left(V,\rightarrow\right)$ is a vertex, say $u$, along with a rule that stipulates for each finite chain $d\left(0\right)\rightarrow\cdots\rightarrow d\left(n\right)$, with $u=d\left(0\right)$, there is a vertex $v$ such that $d\left(0\right)\rightarrow\cdots\rightarrow d\left(n\right)\rightarrow v$ is a finite chain.

**Remark**: Note that any vertex in $\left(V,\rightarrow\right)$ is a trivial finite chain.

## When are Def. 1 and Def. 2 equivalent?

**Theorem 1**: An infinite chain as in Def. 1 is an infinite chain as in Def. 2.

**Proof**: Suppose we have an infinite chain $c\left(0\right)\rightarrow c\left(1\right)\rightarrow\cdots$ in $\left(V,\rightarrow\right)$ as in Def. 1. Let $u$ be $c\left(0\right)$. Now, for any finite chain $d\left(0\right)\rightarrow\cdots\rightarrow d\left(n\right)$ with $c\left(0\right)=d\left(0\right)$, let $f$ be the embedding from that finite chain to the infinite chain which sends $d\left(i\right)$ to $c\left(i\right)$ for each $i=0,\ldots,n$. Note that we consider both the finite chain and the infinite chain as subgraphs of $\left(V,\rightarrow\right)$. Therefore, the finite chain can be identified with the initial segment $c\left(0\right)\rightarrow\cdots\rightarrow c\left(n\right)$, so let $v$ be $c\left(n+1\right)$. $\blacksquare$

If $\left(V,\rightarrow\right)$ has an infinite chain as defined in Def. 2, it is not clear how to define a function from the natural numbers $\mathbb{N}$ to $V$ satisfying the conditions in Def. 1. For instance, take $V$ to be the set of the natural numbers $\mathbb{N}$ and the binary relation to be the strict order $<$. Moreover, take the rule to be as follow: (i) take an infinite binary sequence $b_{0},b_{1},\ldots$, and let $u$ be $0$; (ii) for each $k>0$, if $b_{k}=0$, let $v$ be the even natural number next to $d\left(k-1\right)$, and if $b_{k}=1$, let $v$ be the odd natural number next to $d\left(k-1\right)$. Note that the rule does not specify how to pick the binary sequence. Say the binary sequence has all its terms equal to $0$; then the infinite chain is, for each $0<2<4<\cdots<2j$ there is $v=2\left(j+1\right)$, and say the binary sequence has all its terms equal to $1$; then the infinite chain is, for each $0<1<3<\cdots<2j+1$ there is $v=2\left(j+1\right)+1$. Therefore, if there were a function $c$ from the natural numbers to the infinite chain under Def. 2, then $c\left(j+1\right)$ would be both odd and even for each $j$. But a natural number cannot be both odd and even.

### A fix with the axiom of countable choice

For any set $Y$, say an element of $Y$ is picked for each natural number. If the elements of $Y$ cannot be identified, there is no guarantee that a function can be defined from the natural numbers to $Y$ because the images of that function would not be well defined. To ensure that a function can be obtained, the axiom of countable choice can be used.

The **axiom of countable choice** is a special case of the axiom of choice, which is, for any sets $X,Y$, and relation $R$ between $X$ and $Y$, if, for any element $x$ in $X$, there is an element $y$ in $Y$ such that $R\left(x,y\right)$, then there is a function $f:X\rightarrow Y$ such that for each $x$ in $X$, $R\left(x,f\left(x\right)\right)$. In the case of the axiom of countable choice, the set $X$ is the set $\mathbb{N}$ of the natural numbers.

For each $n$ in $\mathbb{N}$, since the element $y$ that is picked in $Y$ depends on $n$, we will explicitly express this dependence by using $y^{\left(n\right)}$. In our case, $Y$ is the directed graph. Let $R\left(i,y^{\left(i\right)}\right)$ be a variant of the two conditions of Def. 1, that is,

- for all $i,j$ in $\mathbb{N}$, $i=j$ if and only of $y^{\left(i\right)}=y^{\left(j\right)}$;
- for all $i$ in $\mathbb{N}$, $y^{\left(i\right)}\rightarrow y^{\left(i+1\right)}$.

**Lemma 2**: Assume we have an infinite chain as in Def. 2. Then, for each natural number $n$, there is $y^{\left(n\right)}$ in $V$ such that $R\left(n,y^{\left(n\right)}\right)$.

**Proof**: We use induction on $n$. Since we assume we have an infinite chain in $\left(V,\rightarrow\right)$ as in Def. 2, let $u$ be the distinguished vertex, and the rule picks a vertex $v$ such that $u\rightarrow v$ is a finite chain. For $n=0$, let $y^{\left(0\right)}$ be $u$ and $y^{\left(1\right)}$ be $v$ . Hence, $R\left(0,y^{\left(0\right)}\right)$ since $u\rightarrow v$ is a finite chain.

Now assume the lemma is true for each $n>0$. Then there is a finite chain $u\rightarrow d\left(1\right)\rightarrow\cdots\rightarrow d\left(n+1\right)$ such that, for all $j$ in the collection $\left\{ 1,\ldots,n\right\} $, $y^{\left(j\right)}$ is $d\left(j\right)$ and $R\left(j,y^{\left(j\right)}\right)$. Since we have an infinite chain as in Def. 2, there is $v$ in $V$ such that $u\rightarrow d\left(1\right)\rightarrow\cdots\rightarrow d\left(n+1\right)\rightarrow v$ is a finite chain, so let $y^{\left(n+1\right)}$ be $d\left(n+1\right)$ and $y^{\left(n+2\right)}$ be $d\left(n+2\right)$. Hence, $R\left(n+1,y^{\left(n+1\right)}\right)$. $\blacksquare$

**Theorem 3**: Assume the axiom of countable choice holds. If there is an infinite chain in $\left(V,\rightarrow\right)$ as in Def. 2, then there is a function $c$ from the natural numbers $\mathbb{N}$ to $V$ such that

- for all $i,j$ in $\mathbb{N}$, $i=j$ if and only if $c\left(i\right)=c\left(j\right)$;
- for all $i$ in $\mathbb{N}$, $c\left(i\right)\rightarrow c\left(i+1\right)$.

**Proof**: Note that the conclusion of Lemma 2 is the hypothesis of the axiom of countable choice when $Y$ is the directed graph $V$, and the relation $R$ represents the two conditions in this theorem. Therefore, by the axiom of countable choice, there is a function $c$ from the natural numbers $\mathbb{N}$ to $V$ such that $R\left(n,c\left(n\right)\right)$ for each natural number $n$. $\blacksquare$

**Corollary 4**: Assume the axiom of countable choice. Then, Def. 1 and Def. 2 are equivalent.

**Proof**: An infinite chain as in Def. 1 is an infinite chain as in Def. 2, by Theorem 1, and an infinite chain as in Def. 2 is an infinite chain as in Def. 1, by Theorem 3. $\blacksquare$

## Directed Graphs in Applications

### Softwares

Graphviz is a software library that can be used to draw directed graphs. Another such software is Microsoft’s Force-Directed Graph.

### Graph Neural Networks

Graph Neural Networks are neural networks that can take directed graphs as inputs. For instance, see this paper (4.1).

### Quantum Information

Quantum networks can be modeled as directed graphs. For instance, see this paper on quantum walks on directed graphs.

———————————————————————————————————————————————————————–