Mathematics

Two Notions of an Infinite Chain in a Directed Graph

  1. Introduction
  2. Definitions
    1. Directed Graphs
    2. Infinite Chains (Def. 1 & Def. 2)
  3. When are Def. 1 and Def. 2 equivalent?
    1. A fix with the axiom of countable choice
  4. Directed Graphs in Applications
    1. Softwares
    2. Graph Neural Networks
    3. Quantum Information

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

  1. for all $i,j$ in $\mathbb{N}$, $i=j$ if and only if $c\left(i\right)=c\left(j\right)$;
  2. 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,

  1. for all $i,j$ in $\mathbb{N}$, $i=j$ if and only of $y^{\left(i\right)}=y^{\left(j\right)}$;
  2. 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

  1. for all $i,j$ in $\mathbb{N}$, $i=j$ if and only if $c\left(i\right)=c\left(j\right)$;
  2. 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.

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



Leave a Reply

Your email address will not be published. Required fields are marked *