# Dowker Complexes and filtrations on self-relations

Dominic Desjardins Côté

###### Abstract

Given a relation on $X\times Y$, we can construct two abstract simplicial
complexes called Dowker complexes. The geometric realizations of these
simplicial complexes are homotopically equivalent. We show that if two
relations are conjugate, then they have homotopically equivalent Dowker
complexes. From a self-relation on $X$, this is a directed graph, and we use
the Dowker complexes to study their properties. We show that if two relations
are shift equivalent, then, at some power of the relation, their Dowker
complexes are homotopically equivalent. Finally, we define a new filtration
based on Dowker complexes with different powers of a relation.

Keywords :  Dowker complex, relation, filtration, graph theory, shift
equivalence

##  1 Introduction

We can use multivalued maps to study dynamical systems [17]. The idea is to
use Conley index [7] on upper semi-continuous multivalued maps. In
applications, it can be hard to study a dynamical system. We can use a model
that seems to fit data, but it can be a challenge to find it. Another way is
to discretize the continuous space and use to multivalued maps to approximate
the underlying dynamical system [8] [30]. Another approach is to use
combinatorial structures. To name a few, we can use combinatorial vector
fields from Forman [13] [18] [9]. Moreover, a generalization was proposed by
Mrozek called combinatorial multivector fields [23] [25]. Finally, others
proposed to use the distributive lattices to compute attractors on finite data
[19] [20] [21].

Multivalued maps can be restrictive. In [18], authors generalize them to
partial multivalued maps. But a partial multivalued map is equivalent to a
relation. Some advancements were done in [26] by using the Scymczak category
of finite sets where objects are sets and morphisms are relations. The
Szymczak category [29] captures the essence of index pairs and index maps [7]
which is the core of the theory of Conley index. So one motivation of this
paper is to continue to develop the theory of relations, and it can be used to
study dynamical system with finite data.

Our main object is a relation which is a subset of the cartesian product of
two sets $X$ and $Y$. We can define two different abstract simplicial
complexes on a relation. For the first simplicial complex, we fixed a value
$y\in Y$. For all elements in $X$, that they are related to $y$, they will
span a simplex together. For the second one, we reverse the role. We fixed a
value $x\in X$. For all elements in $Y$, that they are in relation with $x$,
they will span a simplex together. They are called Dowker complexes [10]. An
important result is the Dowker’s Theorem. It says that the geometric
realization of these Dowker complexes are homotopically equivalent. The
Dowker’s Theorem is quite useful in applications. To name a few examples, we
can use Dowker complexes to study signal coverage [14], to find errors in
relation of programs and files [1], to study the privacy of information [12]
and in social studies [3]. For the last one, this method is called Q-analysis
which is developed by Atkins [2]. The idea of Q-analysis is to study the
$q$-connectivity and the $q$-tunnel of the Dowker complexes. Our two main
inspirations for definitions come from these articles [24] and [26].

They are many contributions in this article. First, conjugate relations have
homotopically equivalent Dowker complex. If two relations are shift equivalent
with lag $l$, then at a certain power their Dowker complexes are homotopically
equivalent. We can define a filtration on relation based on the Dowker complex
at different powers of a finite self-relation. Moreover, this can be computed
in finite time. We can also compute the $0$th homology of a high enough power
with the connected components of the graph induced by the relation.

This article goes as follows. In section 2, we remind some concepts and
definitions on finite relation, graph, simplicial complex, Dowker complexes
and finally the famous Dowker’s Theorem. In section 3, we define right
morphism and left morphism. If there exists a right or left morphism between
two relations, then there is an inclusion from one of the Dowker complexes.
Moreover, we show that if there exists a conjugacy between two relations, then
their Dowker complexes are homotopically equivalent. In section 4, we
generalize the idea of right and left morphism for multivalued right and
multivalued left morphism. We show two important properties needed for the
definition of a filtration. The Dowker complex of a certain power of a
relation is include in the Dowker complex of the same relation with a higher
power. For some finite relations at certain a power $j$, every other Dowker
complexes of the same relation at power higher than $j$ are the same. We call
it the stabilization of the Dowker complex. We show that shift equivalence
between relations have homotopically equivalent Dowker complex at some power.
In section 5, we can define a filtration on the Dowker complexes of different
powers of a relation under some simple conditions by using the two properties
in section 4. We can use persistent homology on these filtration to extract
topological features of the Dowker complex. If a relation is acyclic, then we
have that the number of connected components of the graph associated to the
relation up to a certain power is equal to the dimension of the $0$th
homology. It can be generalized to the class of simple relations. We also have
a similar result for strongly connected relations.

##  2 Preliminaries

###  2.1 Finite Relations

Let $X$ and $Y$ be finite sets. We define a relation as a subset of $X\times
Y$. Let $(x,y)\in R\subset X\times Y$, we denote by $xRy$ or by $y\in R(x)$.
We define the composition of relations as follows. Let $R_{1}\subset X\times
Y$ and $R_{2}\subset Y\times Z$.

$R_{2}\circ R_{1}:=\\{(x,z)\in R_{2}\circ R_{1}\mid\exists y\text{ such that
}xR_{1}y\text{ and }yR_{2}z\\}.$ (1)

We define the inverse relation by swapping the sets of a relation.

$R^{-1}:=\\{(y,x)\in Y\times X\mid y\in R(x)\\}$ (2)

If a relation is a subset of $X\times X$, then we say it’s a self-relation on
$X$. We define the power of a self-relation as follows :

$R^{n}:=\begin{cases}R\circ R^{n-1}&n>0\\\ Id_{X}&n=0\\\ R^{-1}\circ
R^{n+1}&n<0\end{cases}$

The domain and the image for a relation $R\subset X\times Y$ are :

$\displaystyle\operatorname*{Dom\,}R:=\\{x\in X\mid\exists y\text{ such that
}(x,y)\in R\\}$ (3) $\displaystyle\operatorname*{Im\,}R:=\\{y\in Y\mid\exists
x\text{ such that }(x,y)\in R\\}.$ (4)

We can see relations as partial multivalued maps. If
$\operatorname*{Dom\,}R=X$, then we say that the relation is a multivalued
map. A relation is injective, if for all $x_{1},x_{2}\in X$,
$R(x_{1})=R(x_{2})$ implies that $x_{1}=x_{2}$. A relation is surjective if
$\operatorname*{Im\,}R=Y$. Moreover, a map $f:X\to Y$ induces a relation where
$(x,f(x))\in R$. Without ambiguity, we can compose maps and relations together
to obtain a new relation.

######  Definition 2.1.

Let $R$ be a self-relation on $X$. Let $j$ be the least positive integer such
that :

$R^{j}=R^{j+p}\text{ for some }p>0.$

We say that $j$ is the index and the least $p>0$ is the period. If $j=1$, then
$R$ is periodic. A pair $(j,p)$ is the eventual period of $R$ with index $j$
and period $p$.

In other words, the period $p$ will eventually be a period for $R$.

We sometimes use matrices with values in $\\{0,1\\}$ to represent relations.
Let $R\subset X\times Y$ be a relation with $card(X)=m$ and $card(Y)=n$. The
matrix $M_{m\times n}$ have a value $1$ at $M_{i,j}$ if $x_{i}Ry_{j}$
otherwise the value is $0$. It can be called relation matrix, Boolean relation
matrix, binary relation matrix, binary Boolean matrix, $(0,1)$-Boolean matrix
and $(0,1)$-matrix. For more information on Boolean matrix theory, we refer to
the book [22].

We say that a self-relation $R$ on $X$ has a cycle at $x$ if and only if there
exists an $n\in\mathbb{N}$ such that $xR^{n}x$. We say $R$ as a fixed point at
$x$, if $n=1$. If a relation has no cycle at $x$ for all $x$ with period
$n>1$, then the relation is acyclic. A cycle is a sequence
$x_{1},x_{2},\ldots,x_{n}$ such that $x_{1}=x_{n}$ and $x_{i}Rx_{i+1}$. A
self-relation $R$ on $X$ is simple if for any two cycles are either disjoints
or equals.

###  2.2 Graphs

In this subsection, we remind the definition of a graph and some notations.

######  Definition 2.2.

A directed graph $G$ is a pair $(E,V)$ where $V$ is the set of vertices $V$
and $E$ is the subset $V\times V$ the set of edges.

A relation can also be seen as a directed graph. If $R$ is a self-relation on
$X$, then $X$ is the set of vertices and the set of edges $E=R$. This graph
has at most one directed edge from the vertex $A$ to the vertex $B$, and we
also allow a self-loop on vertices. We note $G_{R}$ the graph induced by a
self-relation $R$.

Let $x,y\in V$. There is a $(x,y)$-path, if there exists a sequence of edges
$e_{1},e_{2},\ldots,e_{n}\in E$ that connect $x$ to $y$ without following the
direction of edges. We can define an equivalence relation on vertices of $G$.
If there is a path between two vertices $x$ and $y$, then $x$ and $y$ are in
the same class of equivalence. For a graph $G$, we say the number of connected
components is the number of class equivalences of the relation of paths. We
say $G$ is connected if there is only one connected component.

If the sequence of edges of a $(x,y)$-path follows the direction of edges of
the graph, then we say it’s a $(x,y)$-walk. We can also define an equivalence
relation with a walk between vertices. If there is a walk from $x$ to $y$ and
a walk from $y$ to $x$, then $x$ and $y$ are in the same equivalence class.
This is the class of strongly connected components. For a graph $G$, we say
the number of strongly connected components is the number of class equivalence
of the relation of walks. We say $G$ is strongly connected if there is only
one strongly connected component.

###  2.3 Simplicial Complexes and Dowker Complexes

In this subsection, we will discuss simplicial complex, Dowker complex and the
Dowker’s Theorem. For more information about simplicial complex, we suggest to
read [27]. We do not present filtration and persistent homology, but we refer
to [11].

An abstract simplicial complex is a set $K$ that contains finite non-empty
sets such as if $A\in K$, then for all subsets of $A$ are also in $K$. For
further examples, we use geometric simplex. A geometric $n$-simplex is the
convex hull of a geometrically independent sets of vertices
$\\{v_{0},v_{1},\ldots,v_{n}\\}\in\mathbb{R}^{N}$. This is the set of
$x\in\mathbb{R}^{N}$ such as $x=\sum_{i=0}^{n}t_{i}x_{i}$ and
$1=\sum_{i=0}^{n}t_{i}$ where $t_{i}\geq 0$ for all $i$. We denote an
$n$-simplex by $[v_{0},v_{1},\ldots,v_{n}]$ is the simplex spanned by the
vertices $v_{0},v_{1},\ldots,v_{n}$. Any simplex spanned by the subsets of
$\\{v_{0},v_{1},\ldots,v_{n}\\}$ are called faces and denote by the symbol
$\leq$. A simplicial complex is a collection of simplices for all $\sigma\in
K$, if $\tau\leq\sigma$ then $\tau\in K$ and if
$\sigma_{1}\cap\sigma_{2}=\tau$, then $\tau$ is either the empty set or $\tau$
is a face of $\sigma_{1}$ and $\sigma_{2}$. We say that $L\leq K$ if $L$ is a
sub-complex of $K$. A simplicial complex is contractible if its homology is
equivalent to a point. Given an abstract simplicial $K$, we can define a
geometric simplicial complex and $|K|$ call the geometric realization of $K$.
We call $0$-simplices vertices and $1$-simplices edges. The closure of a
simplex $\sigma$ is the set of all the faces of the simplex. We denote it by
$cl(\sigma)$. We need one more definition related to simplicial complexes. It
will be useful in some proofs.

######  Definition 2.3.

A simplicial complex $K$ is edge-connected, if for any two vertices $x$ and
$y$ there is a sequence of edges $e_{1},e_{2},\ldots,e_{n}$ such that $x\in
e_{1}$, $y\in e_{n}$ and $cl(e_{i})\cap cl(e_{i+1})\neq\emptyset$ for all
$i=1,2,\ldots,n-1$.

We have that the simplicial complex is connected if and only if it is edge-
connected if and only if $H_{0}$ is dimension $1$ [16].

Now we explain how to construct abstract simplicial complexes from a relation
which are called Dowker complexes. Let $R\subset X\times Y$ be a relation and
$X,Y$ be two finite sets. There are two ways to construct the Dowker complex
from a relation.

######  Definition 2.4.

Let $R\subset X\times Y$ be a finite relation and $K_{R}$ be the Dowker
complex. A simplex $[x_{1},x_{2},\ldots,x_{n}]\in K_{R}$ if and only if
$\exists y\in Y$ such as $x_{i}Ry$ for all $i=1,2,\ldots,n$.

We have an analogous construction.

######  Definition 2.5.

Let $R\subset X\times Y$ be a finite relation and $L_{R}$ be the Dowker
complex. A simplex $[y_{1},y_{2},\ldots,y_{m}]\in L_{R}$ if and only if
$\exists x\in X$ such as $xRy_{i}$ for all $i=1,2,\ldots,n$.

We denote $[x_{1},x_{2},\ldots x_{n}]=\sigma_{y}\in K_{R}$ if and only if
$x_{i}Ry$ for all $i=1,2,\ldots,n$. We use $y$ as an index for $\sigma_{y}$ to
note that all vertices of $\sigma_{y}$ are in $R^{-1}(y)$. We use the same
notation for $\sigma_{x}\in L_{R}$ but the vertices are in $R(x)$.

By using the matrix notation, we can use rows and columns to build the
simplices. The columns are for $K_{R}$ and the rows are for $L_{R}$.

######  Example 2.6.

Let $R\subset X\times Y$ be a finite relation.

$R:=\begin{bmatrix}1&0&0&0&1\\\ 0&0&1&1&0\\\ 1&0&0&0&1\\\
1&1&0&0&0\end{bmatrix}$ (5)

The first column gives the $2$-simplex $[x_{1},x_{3},x_{4}]$. The third and
the fourth column give the $0$-simplex $[x_{2}]$. The second and the fifth
column do not add new simplices. We obtain the simplicial complex
$K_{R}:=\\{[x_{1},x_{3},x_{4}],[x_{2}]\\}$.

The first row adds a $1$-simplex $[y_{1},y_{5}]$ to $L_{R}$. The second row
gives a $1$-simplex $[y_{3},y_{4}]$. The final row adds a $1$-simplex
$[y_{1},y_{5}]$. We obtain the simplicial complex
$L_{R}=\\{[y_{1},y_{5}],[y_{3},y_{4}],[y_{1},y_{2}]\\}$.

We obtain that $|K_{R}|$ and $|L_{R}|$ have two connected components and no
higher dimension cycle.

(a) Geometric realization of the Dowker complex $K_{R}$.

(b) Geometric realization of the Dowker complex $L_{R}$.

Figure 1: These are geometric realizations of the Dowker complexe in Example
2.6. They are homotopically equivalent.

The next theorem links to the homotopy between $|K_{R}|$ and $|L_{R}|$.

######  Theorem 2.7 (Dowker’s Theorem).

Let $R\subset X\times Y$ be a relation and let $K_{R}$ and $L_{R}$ be the
associated Dowker complexes. Then, the polyhedra $|K_{R}|$ and $|L_{R}|$ are
homotopy equivalent.

In 1952, Dowker [10] has shown that $K_{R}$ and $L_{R}$ have isomorphic
homology groups. In 1995, Björner [4] has shown that $|K_{R}|$ and $|L_{R}|$
are homotopically equivalent, which is the more commonly use in the
literature. In recent years, Dowker complexes were regained in popularity in
the community of topology data analysis. We can use them to do a filtration on
weighted networks [6]. In our cases, our filtration will be different and
based on different powers of a self-relation.

##  3 Left and Right Morphism

Let start with the definition of the graph homomorphism and next we define
left and right morphisms between relations.

######  Definition 3.1.

Let $R$ be a self-relation on $X$ and $R^{\prime}$ be a self-relation on $Y$.
A map $f:X\to Y$ is a graph homomorphism if the following condition is
satisfied :

$\text{For every }x_{1},x_{2}\in X\text{ such as }x_{1}Rx_{2}\implies
f(x_{1})R^{\prime}f(x_{2}).$

If $f$ is bijective and its inverse is also a graph homomorphism, then $f$ is
a graph isomorphism.

We obtain that graph homomorphism keeps some information of the Dowker complex
coming from the first relation.

######  Lemma 3.2.

Let $f:X\to Y$ be a graph homomorphism between $R$ and $R^{\prime}$. If $f$ is
injective, then there exist a map $p:K_{R}\hookrightarrow K_{R^{\prime}}$.

###### Proof.

Consider a $n$-simplex $[x_{0},x_{1},\ldots,x_{n}]\in K_{R}$. Then, there
exists $\alpha\in X$ such as $x_{i}R\alpha$ for all $i=0,1,2,\ldots n$. We
have that $f$ is a graph homomorphism. This implies that
$f(x_{i})R^{\prime}f(\alpha)$ for all $i=0,1,2,\ldots,n$. Indeed, $f$ is
injective implies that $[f(x_{0}),f(x_{1}),\ldots,f(x_{n})]$ is also a
$n$-simplex in $K_{R^{\prime}}$. So we can construct a map
$p:K_{R}\hookrightarrow K_{R^{\prime}}$ by sending a simplex
$[x_{0},x_{1},\ldots,x_{n}]$ to $[f(x_{0}),f(x_{1}),\ldots,f(x_{n})]$. By the
previous argument, $p$ is well defined and injective. ∎

If we have a graph isomorphism between two relations, then the Dowker
complexes remain unchanged. This holds because graph isomorphisms are
relabelling on the vertices of a graph.

######  Proposition 3.3.

Let $R_{1}$ be a self-relation on $X$ and $R_{2}$ be a self-relation on $Y$.
If there exists a graph isomorphism $f$ between $R_{1}$ and $R_{2}$, then they
have the same Dowker complexes up to the label of vertices.

###### Proof.

Graph homomorphisms $f$ and $f^{-1}$ are injective. By the Lemma 3.2, there
exist two injective maps $p:K_{R}\hookrightarrow K_{R^{\prime}}$ and
$p^{\prime}:K_{R^{\prime}}\hookrightarrow K_{R}$. So we have that $K_{R}$ and
$K_{R^{\prime}}$ are the same up to the label of vertices.

By similar arguments, we can show it for $L_{R}$ and $L_{R^{\prime}}$. ∎

Graph homomorphisms are nice, but they can drastically change the Dowker
complexes. So, we defined a left morphism which it changes the source of an
edge and a right morphism which it changes the target of an edge. In this way,
only one of the Dowker complexes will change from the right morphism or the
left morphism.

######  Definition 3.4.

A right morphism $f:(X,Y,R)\to(X,Z,R^{\prime})$ is a map $f:Y\to Z$ such that
for every $x\in X$ and $y\in Y$ :

$xRy\implies xR^{\prime}f(y).$

We obtain this simple Lemma which is very useful for later proofs.

######  Lemma 3.5.

If there exists a right morphism $f:(X,Y,R)\to(X,Z,R^{\prime})$, then
$K_{R}\leq K_{R^{\prime}}$. We obtain the equality if $f$ is a bijective map.

###### Proof.

Let $f:(X,Y,R)\to(X,Z,R^{\prime})$ be a right morphism and
$[x_{1},x_{2},\ldots,x_{n}]\in K_{R}$. This implies there exists a $y\in Y$
such as $x_{i}Ry$ for all $i=1,2,\ldots,n$. We obtain that
$x_{i}R^{\prime}f(y)$ for all $i$. Finally, we have
$[x_{1},x_{2},\ldots,x_{n}]\in K_{R^{\prime}}$.

Now, we suppose that $f$ is bijective. Let $[x_{1},x_{2},\ldots,x_{n}]\in
K_{R^{\prime}}$. Then, there exists a $z\in Z$ such that $x_{i}R^{\prime}z$
for all $i=1,2,\ldots,n$. We have $f^{-1}(z)\in Y$ and $f^{-1}$ is well
defined because $f$ is bijective. Then, $x_{i}Rf^{-1}(z)$ for all
$i=1,2,\ldots,n$. We obtain that $[x_{1},x_{2},\ldots,x_{n}]\in K_{R}$. ∎

The idea of right morphism comes from the article [24]. The author only
considered the right morphism. But, in our case, we are also interesting of
modifying the first set in the cartesian product of a relation.

######  Definition 3.6.

A left morphism $g:(X,Z,R)\to(Y,Z,R^{\prime})$ is a map $g:X\to Y$ such that
for every $x\in X$ and $z\in Z$ :

$xRz\implies g(x)R^{\prime}z.$

We have an analogous Lemma for left morphism as the Lemma 3.5 for right
morphism.

######  Lemma 3.7.

If there exists a left morphism $g:(X,Z,R)\to(Y,Z,R)$, then $L_{R}\leq
L_{R^{\prime}}$. We obtain the equality if $g$ is a bijective map.

With the definition of right and left morphism, we can easily show that if two
relations are conjugate, then there Dowker complexes are homotopically
equivalent. We remind the definition of conjugacy between relations before
showing the proof.

######  Definition 3.8.

Let $R_{1}$ be a self-relation on $X$ and $R_{2}$ be a self-relation on $Y$.
We say that $R_{1}$ and $R_{2}$ are conjugate if there exists a bijective map
$\varphi:X\to Y$ such as $\varphi\circ R_{1}=R_{2}\circ\varphi$.

######  Corollary 3.9.

Let $R$ be a self-relation on $X$ and $R^{\prime}$ be a self-relation on $Y$
which are conjugate by a bijective map $\varphi:X\to Y$. Then,
$|K_{R}|,|L_{R}|,|L_{R^{\prime}}|$ and $|K_{R^{\prime}}|$ are homotopy
equivalent.

###### Proof.

The map $\varphi$ is bijective. It implies that $K_{R}=K_{\varphi\circ R}$ by
Lemma 3.5 and $L_{R^{\prime}}=L_{R^{\prime}\circ\varphi}$ by Lemma 3.7.

By Dowker’s Theorem, we obtain that $|K_{R}|$ is homotopic equivalent to
$|L_{R^{\prime}}|$, because $K_{\varphi\circ R}=K_{R^{\prime}\circ\varphi}$. ∎

In [28], the author decides to combine the right and left morphism together.
Let $R\subset X\times Y$ and $R^{\prime}\subset X^{\prime}\times Y^{\prime}$
be relations and $f:X\to X^{\prime}$ and $g:Y\to Y^{\prime}$ be two maps. A
pair $(f,g)$ is a morphism between relation $R_{1}$ and $R_{2}$ if for all
$x\in X,y\in Y$ such that $xR_{1}y$ it implies that $f(x)R_{2}g(y)$. In [28],
it is shown that the Dowker complex and (co)sheaf representation have nice
functoriality properties. In our case, it won’t be useful because we only need
right or left morphism. But we can see them as a pair $(id_{X},f)$ where $f$
is a right morphism and $id_{X}$ is the identity function on $X$.

##  4 Multi-right morphism and multi-left morphism

We want to work with multivalued maps. We generalize left and right morphism
to multi-left and multi-right morphism.

######  Definition 4.1.

A multi-right morphism $F:(X,Y,R)\multimap(X,Z,R^{\prime})$ is a multivalued
map $F:Y\multimap Z$ such as for all $x\in X$, $y\in Y$ :

$xRy\implies xR^{\prime}a\text{ for all }a\in F(y).$

We also obtain the same Lemma as before.

######  Lemma 4.2.

Let $R\subset X\times Y$ and $R^{\prime}\subset X\times Z$ be relations. If
there exist a multi-right morphism $F:(X,Y,R)\multimap(X,Z,R^{\prime})$, then
$K_{R}\leq K_{R^{\prime}}$. We obtain the equality if $F$ is a bijective
multivalued map.

###### Proof.

The proof is the same as Lemma 3.5. ∎

######  Definition 4.3.

A multi-left morphism $G:(X,Z,R)\multimap(Y,Z,R^{\prime})$ is a multivalued
map $G:X\to Y$ such for all $x\in X,z\in Z$ :

$xRz\implies aR^{\prime}z\text{ for all }a\in G(x).$

######  Lemma 4.4.

Let $R\subset X\times Z$ and $R^{\prime}\subset Y\times Z$ be relations. If
there exist a multi-left morphism $G:(X,Z,R)\multimap(Y,Z,R^{\prime})$, then
$L_{R}\leq L_{R^{\prime}}$. We obtain the equality if $G$ is a bijective
multivalued map.

We denote a multi-right morphism by mr-morphism and a multi-left morphism by
ml-morphism.

######  Remarks 4.5.

We remind that if a relation $S\subset X\times Y$ satisfies
$\operatorname*{Dom\,}S=X$, then $S$ is a well-defined multivalued map.
Moreover, for any relation $R\subset Z\times X$, we have that
$S:(Z,X,R)\multimap(Z,Y,S\circ R)$ is a well-defined mr-morphism. It is also
true for ml-morphism.

The next corollary will be useful to define our filtrations.

######  Corollary 4.6.

Let $R$ be a self-relation on $X$. If $\operatorname*{Dom\,}R=X$, then
$K_{R^{n}}\leq K_{R^{n+1}}$. If $\operatorname*{Im\,}R=X$, then $L_{R^{n}}\leq
L_{R^{n+1}}$.

###### Proof.

$\operatorname*{Dom\,}R=X$ implies that $R$ is a multivalued map. Moreover,
$R:(X,X,R^{n})\multimap(X,X,R^{n+1})$ is well-defined mr-morphism. By Lemma
3.5, we have that $K_{R^{n}}\leq K_{R^{n+1}}$.

In the same way, $\operatorname*{Im\,}R=X$ implies that $R^{-1}$ is a
multivalued map. We have that $R^{-1}:(X,X,R^{n})\multimap(X,X,R^{n+1})$ is
well-defined ml-morphism. By Lemma 3.7, we have that $L_{R^{n}}\leq
L_{R^{n+1}}$. ∎

######  Remark 4.7.

The hypothesis $\operatorname*{Dom\,}R=X$ in the previous corollary is
important. Let us show that by an example. If $R$ is a self-relation on $X$,
define by this matrix such as :

$\begin{bmatrix}0&1&1\\\ 0&0&1\\\ 0&0&0\end{bmatrix}$ (6)

Then, we obtain $K_{R}=\\{[x_{2},x_{3}],[x_{2}],[x_{3}]\\}$,
$K_{R^{2}}=\\{[x_{3}]\\}$ and $K_{R^{n}}=\emptyset$ for $n>2$.

We don’t have $K_{R^{n}}\subset K_{R^{n+1}}$ for all $n\in\mathbb{N}_{>0}$. If
the matrix is nilpotent, then $K_{R^{n}}$ is an empty set for an
$n\in\mathbb{N}_{>0}$.

Using Corollary 4.6, we can show that the Dowker complexes of a relation
stabilize at some power $n$.

######  Corollary 4.8.

Let $R$ be a finite self-relation on $X$ with an eventual period $(j,p)$. If
$\operatorname*{Dom\,}R=X$, then, we have $K_{R^{j}}=K_{R^{j+i}}$ for
$i\in\mathbb{N}$. If $\operatorname*{Im\,}R=X$, then $L_{R^{j}}=L_{R^{j+i}}$
for $i\in\mathbb{N}$.

###### Proof.

By Corollary 4.6, we have the sequence :

$K_{R^{j}}\leq K_{R^{j+1}}\leq\ldots\leq K_{R^{j+p-1}}\leq K_{R^{j+p}}.$ (7)

But $p$ is the period of $R$, hence $R^{j}=R^{j+p}$ implies that
$K_{R^{j}}=K_{R^{j+p}}$. By (7), we obtain $K_{R^{j}}=K_{R^{j+i}}$ for
$i\in\mathbb{N}$. A similar proof can be done for $L_{R^{j}}=L_{R^{j+i}}$ for
$i\in\mathbb{N}$. ∎

We remind the definition of shift equivalence between two relations and we
show the assumption that relations are shift equivalences implies that theirs
Dowker complexes are homotopically equivalent at some power for each relation.

######  Definition 4.9.

Let $R_{1}$ be finite self-relation on $X$ and $R_{2}$ be finite self-relation
on $Y$. $R_{1}$ and $R_{2}$ are shift equivalent with a lag $l$, if there
exists two relations $S\subset X\times Y$ and $T\subset Y\times X$ such as :

$\displaystyle R_{1}\circ T=T\circ R_{2}\quad S\circ R_{1}=R_{2}\circ S$
$\displaystyle T\circ S=R_{1}^{l}\quad S\circ T=R_{2}^{l}$

We say it is a strong shift equivalence if $l=1$.

######  Corollary 4.10.

Let $R_{1}$ be finite self-relation on $X$ with
$\operatorname*{Dom\,}R_{1}=X=\operatorname*{Im\,}R_{1}$ and $R_{2}$ be finite
self-relation on $Y$ with
$\operatorname*{Dom\,}R_{2}=Y=\operatorname*{Im\,}R_{2}$. Let $(j_{p},p)$ be
an eventual period of $R_{1}$ and $(j_{q},q)$ be an eventual period of
$R_{2}$. Without loss of generality, we suppose that $j_{p}\geq j_{q}$. If
$R_{1}$ and $R_{2}$ are shift equivalent with lag $l$, then
$|K_{R_{1}^{j_{p}}}|$, $|K_{R_{2}^{j_{q}}}|$, $|L_{R_{1}^{j_{p}}}|$ and
$|L_{R_{2}^{j_{q}}}|$ are homotopy equivalent.

###### Proof.

If $R_{1}\circ T=T\circ R_{2}$ then $R_{1}^{n}\circ T=T\circ R_{2}^{n}$ is
also true for $n\in\mathbb{N}$. Moreover, we have $\operatorname*{Dom\,}S=X$
and $\operatorname*{Dom\,}T=Y$, because $\operatorname*{Dom\,}R_{1}=X$,
$\operatorname*{Dom\,}R_{2}=Y$, $T\circ S=R_{1}^{l}$ and $S\circ T=R_{2}^{l}$.
So we have that $S$ and $R$ are well defined multivalued maps.

We want to show that $K_{R_{1}^{j_{p}}}=K_{S\circ R_{1}^{j_{p}}}$ and
$L_{R_{2}^{j_{q}}}=L_{R_{2}^{j_{q}}\circ S}$. We are going to use $T$ and $S$
as mr-morphism with $R_{1}$ and ml-morphism with $R_{2}$.

We have that $S:(X,X,R_{1}^{j_{p}})\multimap(X,Y,S\circ R_{1}^{j_{p}})$ and
$T:(X,Y,S\circ R_{1}^{j_{p}})\multimap(X,X,T\circ S\circ R_{1}^{j_{p}})$ are
well-defined mr-morphisms. We have $T\circ S=R_{1}^{l}$. It implies that
$T\circ S\circ R_{1}^{j_{p}}=R_{1}^{l+j_{p}}$. We obtain
$K_{R_{1}^{j_{p}}}\leq K_{S\circ R_{1}^{j_{p}}}\leq K_{T\circ S\circ
R_{1}^{j_{p}}}=K_{R_{1}^{l+j_{p}}}$. The eventual period of $R_{1}$ is
$(j_{p},p)$. It implies that $K_{R_{1}^{j_{p}}}=K_{R_{1}^{j_{p}+l}}$. We
obtain that $K_{R_{1}^{j_{p}}}=K_{S\circ R_{1}^{j_{p}}}$.

We can see that $S:(Y,Y,R_{2}^{j_{p}})\multimap(X,Y,R_{2}^{j_{p}}\circ S)$ and
$T:(X,Y,R_{2}^{j_{p}}\circ S)\multimap(Y,Y,R_{2}^{j_{p}}\circ S\circ T)$ are
well-defined ml-morphisms. We have $S\circ T=R_{2}^{l}$. It implies that
$R_{2}^{j_{p}}\circ S\circ T=R_{2}^{j_{p}+l}$. We obtain
$L_{R_{2}^{j_{p}}}\leq L_{R_{2}^{j_{p}}\circ S}\leq L_{R_{2}^{j_{p}}\circ
S\circ T}=L_{R_{2}^{j_{p}+l}}$. We have
$L_{R_{2}^{j_{q}}}=L_{R_{2}^{j_{p}+l}}$ because $j_{p}\geq j_{q}$. We obtain
$L_{R_{2}^{j_{p}}}=L_{R_{2}^{j_{p}}\circ S}$.

Finally, we have $K_{R_{1}^{j_{p}}}=K_{S\circ
R_{1}^{j_{p}}}=K_{R_{2}^{j_{p}}\circ S}$ and
$L_{R_{2}^{j_{p}}}=L_{R_{2}^{j_{p}}\circ S}=L_{S\circ R_{1}^{j_{p}}}$. By
Dowker’s Theorem, we obtain that $|K_{R_{1}^{j_{p}}}|$, $|K_{R_{2}^{j_{q}}}|$,
$|L_{R_{1}^{j_{p}}}|$ and $|L_{R_{2}^{j_{q}}}|$ are homotopy equivalent.

∎

######  Example 4.11.

Let $X$ be a finite set with $8$ points and $Y$ be a finite set with $3$
points. Let $R_{1}$ be a self-relation on $X$ and $R_{2}$ be a self-relation
on $X$ defined by those graphs in Figure 2. $R_{1}$ has an eventual period
$(3,3)$ and $R_{2}$ has an eventual period $(1,3)$. We see in Figures 3(a),
(b) and (d) that the Dowker complexes are not homotopically equivalent. But,
in Figures 3 (c) and (d), the Dowker complexes with relations at power $3$ are
homotopically equivalent.

(a) The graph $G_{R_{1}}$.

(b) The graph $G_{R_{2}}$.

Figure 2: Theses are the graphs from Example 4.11.

(a) Dowker complex of $|K_{R_{1}}|$.

(b) Dowker complex of $|L_{R_{1}}|$.

(c) Dowker complexes of $|K_{R_{1}^{3}}|$ and $|L_{R_{1}^{3}}|$.

(d) Dowker complexes $|K_{R_{2}}|,|L_{R_{2}}|,|K_{R_{2}^{3}}|$ and
$|L_{R_{2}^{3}}|$.

Figure 3: Theses are the different Dowker complexes from Example 4.11.

There is an interesting proposition from [15] that we can use for strongly
connected relations. We remind that an indecomposable Boolean matrix is a
relation which is strongly connected and $J$ is a square matrix where all the
entries are equals to $1$.

######  Proposition 4.12 (Proposition 4.3 in [15] ).

Every indecomposable Boolean matrix with positive trace is strong shift
equivalent to $J$.

We can easily compute the Dowker complexes of $J$. It is a $(n-1)$-simplex
where $n$ is the number of rows of $J$ for both Dowker complexes. Finally, we
obtain that the Dowker complexes of a strongly connected self-relation at a
power high enough are contractible if the trace is strictly positive.

##  5 Filtrations of Dowker complexes

For this section, we suppose that a $R$ is a finite self-relation on $X$. From
Corollary 4.6, if $\operatorname*{Dom\,}R=X$, then we have $K_{R^{i}}\leq
K_{R^{i+1}}$ for all $i\geq 0$. We have an inclusion and we get this
filtration :

$K_{R}\hookrightarrow K_{R^{2}}\hookrightarrow\ldots\hookrightarrow
K_{R^{i}}\hookrightarrow K_{R^{i+1}}\hookrightarrow\ldots$ (8)

In the same way with $\operatorname*{Im\,}R=X$, we have $L_{R^{i}}\leq
L_{R^{i+1}}$. We obtain another filtration :

$L_{R}\hookrightarrow L_{R^{2}}\hookrightarrow\ldots\hookrightarrow
L_{R^{i}}\hookrightarrow L_{R^{i+1}}\hookrightarrow\ldots$ (9)

From Corollary 4.8, the Dowker complexes stabilize at a certain power. This
means we can compute the filtration (8) and (9) in finite time. For our
filtrations, we start at $i=1$, but we could also start with the $i=0$. We
have that $R^{0}=id_{X}$ and $R:(X,X,id_{X})\multimap(X,X,R)$ is a well-
defined mr-morphism, if $\operatorname*{Dom\,}R=X$. Then, the filtration (8)
becomes :

$K_{id_{X}}=K_{R^{0}}\hookrightarrow K_{R}\hookrightarrow
K_{R^{2}}\hookrightarrow\ldots\hookrightarrow K_{R^{i}}\hookrightarrow
K_{R^{i+1}}\hookrightarrow\ldots$ (10)

And for the filtration (9) by applying similar arguments, we obtain :

$L_{id_{X}}=L_{R^{0}}\hookrightarrow L_{R}\hookrightarrow
L_{R^{2}}\hookrightarrow\ldots\hookrightarrow L_{R^{i}}\hookrightarrow
L_{R^{i+1}}\hookrightarrow\ldots$ (11)

The homology of $K_{id_{X}}$ and $L_{id_{x}}$ is the homology of $n=card(X)$
points. In some cases, we might want to start the filtration at $i=0$ or
$i=1$.

We remind that, by Dowker’s Theorem, $|K_{R^{i}}|$ and $|L_{R^{i}}|$ are
homotopically equivalent for all $i\in\mathbb{N}$. We obtain the same bar code
representation for filtrations (8) and (9).

######  Example 5.1.

Let $R_{1}$ be a self-relation on $X$ given by the graph in the Figure 4(a).
$R_{1}$ has 9 nodes and is acyclic. The eventual period is $(3,1)$. We obtain
the bar code at Figure 4(b). It has one generator of $H_{1}$ with the interval
$[1,2]$ and we had $3$ generators of $H_{0}$ that die early and $1$ generator
of $H_{0}$ that survive to infinity.

######  Example 5.2.

Let $R_{2}$ be a self-relation on $X$ given by the graph in the Figure 4(c).
$R_{2}$ has 10 nodes and is simple. The eventual period is $(3,4)$. We obtain
the bar code at the Figure 4(d). It has $4$ generators of $H_{0}$ that die at
time $2$ and $2$ other generators that survive to infinity.

(a) The graph of the acyclic relation from Example 5.1.

(b) The associated bar code of the relation from Example 5.1. We use the
filtration with $K_{R_{1}^{i}}$. The first bar in orange is a generator in
$H_{1}$ and the others four bars in blue are generators in $H_{0}$.

(c) The graph of the relation with multiple cycles from Example 5.2.

(d) The associated bar code of the relation from Example 5.2. We use the
filtration with $K_{R_{2}^{i}}$. The six bars in blue are generators in
$H_{0}$.

Figure 4: In these figures, we have the graph on the left and the associated
bar code diagram on the right for Examples 5.1 and 5.2. Dashed lines in bar
code mean it goes to infinity.

For the next results, we compute the $0$th homology of the Dowker complexes
for different types of relation.

If $R$ is a finite acyclic self-relation, then it has an eventual period $p=1$
and $j\in\mathbb{N}_{>0}$ such as $R^{j}=R^{i}$ for all $i\geq j$. So we
denote this relation $R^{j}$ by $R^{\infty}$, because it converges to a
relation when $i\to\infty$.

######  Definition 5.3.

We say that $x\in X$ is a minimum for a self-relation $R$, if there exists no
$y\in X$ such as $x\neq y$ and $xR^{\infty}y$. We denote the set
$U_{x}:=\\{y\in X\mid yR^{\infty}x\\}$.

We say that $x\in X$ is a maximum for a self-relation $R$, if there exists no
$y\in X$ such as $x\neq y$ and $yR^{\infty}x$. We denote the set
$D_{x}:=\\{y\in X\mid xR^{\infty}y\\}$.

The maximums and minimums of an acyclic relation are important, because they
are responsible for the maximal simplices of $K_{R^{\infty}}$ and
$L_{R^{\infty}}$.

######  Lemma 5.4.

Let $R$ be a finite acyclic self-relation on $X$ with
$\operatorname*{Dom\,}R=X$. Then, the maximal simplices of $K_{R^{\infty}}$
are given by the minimums of $R^{\infty}$.

###### Proof.

We have that $\operatorname*{Dom\,}R=X$ it implies that
$\operatorname*{Dom\,}R^{\infty}=X$. Then, for all $x\in X$ there exists $z\in
X$ such that $xR^{\infty}z$ and $z$ is a minimum. Let
$\sigma_{y}=[x_{1},x_{2},\ldots,x_{n}]\in K_{R^{\infty}}$ be an arbitrary
simplex. We have an $y\in X$ such as $x_{i}R^{\infty}y$ for all
$i=1,2,\ldots,n$. By the first argument, there exists a minimum $z\in X$ such
as $yR^{\infty}z$. Therefore, we have $x_{i}R^{\infty}yR^{\infty}z$. Then,
$\sigma_{y}\subset\sigma_{z}$. ∎

We can do a similar result with $L_{R^{\infty}}$ by using the maximums of
$R^{\infty}$, if $\operatorname*{Im\,}R=X$.

######  Theorem 5.5.

Let $R$ an acyclic finite self-relation on $X$ with
$\operatorname*{Dom\,}R=X$.

$\text{ number of connected components of }G_{R}=\dim
H_{0}(K_{R^{\infty}})=\dim H_{0}(L_{R^{\infty}})$ (12)

###### Proof.

First, by Dowker’s Theorem, we have $\dim H_{0}(K_{R^{\infty}})=\dim
H_{0}(L_{R^{\infty}})$. We suppose that $G_{R}$ is connected and show that
$\dim H_{0}(K_{R^{\infty}})=1$. More precisely, we show that $K_{R^{\infty}}$
is edge-connected. We have that $\operatorname*{Dom\,}R=X$ implies that for
all $x\in X$,$[x]\in K_{R^{\infty}}$.

Let $x,x^{\prime}\in X$. There exists $y_{1}\in X$ a minimum such as
$xR^{\infty}y_{1}$ and $y_{1}R^{\infty}y_{1}$. This implies that
$e_{1}=[x,y_{1}]\in K_{R^{\infty}}$. We also have that there exists $y_{n}\in
X$ a minimum such as $x^{\prime}R^{\infty}y_{n}$ and $y_{n}R^{\infty}y_{n}$.
This implies that $e_{n}=[x^{\prime},y_{n}]\in K_{R^{\infty}}$.

Since $G_{R}$ is connected, there exists a $(y_{1},y_{n})$-path of finite
length. We denote this sequence by $y_{1},z_{1},z_{2},z_{3},$
$\ldots,z_{m},y_{n}$. Without loss of generality, we take the shortest path.
There exist a $i$ such as $z_{i}\in U_{y_{1}}$ and $z_{i+1}\notin U_{y_{1}}$.
First, we have $e_{2}=[y_{1},z_{i}]\in K_{R^{\infty}}$ and $z_{i}Rz_{i+1}$.
There exists $y_{2}\neq y_{1}$ a minimum such as $z_{i+1}R^{\infty}y_{2}$.
This implies that $z_{i}R^{\infty}y_{2}$ and we have the edge
$e_{3}=[z_{i},y_{2}]\in K_{R^{\infty}}$. We can repeat this process with the
$(y_{2},y_{n})$-path until we obtain a sequence of edges that connect the
vertex $[x]$ and $[x^{\prime}]$. We obtain that $K_{R^{\infty}}$ is edge-
connected.

Now suppose that $G_{R}$ is not connected. Let $H$ be a connected component of
$G_{R}$. Then, for all $x\in H$ and for all $y\notin H$, we have that $x\notin
R(y)$ and $y\notin R(x)$. It implies that for each connected component gives a
single generator for $H_{0}(K_{R^{\infty}})$.

We can construct a map $j:cc(G_{R})\to H_{0}(K_{R^{\infty}})$ that sends the
connected components of $G_{R}$ to the generators of $H_{0}(K_{R^{\infty}})$.
By the previous argument, we can make this map $j$ injective . For any
generator $g$ in $H_{0}(K_{R^{\infty}})$, there exists a $x\in X$ such as $g$
is homologous to $[x]$ because $\operatorname*{Dom\,}R=X$. This implies there
exists a $H\in cc(G_{R})$ such as $x\in H$. We obtain that the map $j$ is
bijective and the equality (12).

∎

We can show a similar proof for simple relations.

######  Theorem 5.6.

Let $R$ be a finite simple self-relation on $X$ with
$\operatorname*{Dom\,}R=X$ and $(j,p)$ be an eventual period. Assume that
$G_{R}$ is connected. There exists a $r\in\mathbb{N}$ such that :

$\dim H_{0}(K_{R^{j}})=\dim H_{0}(L_{R^{j}})=\text{ number of connected
components of }G_{R^{r}}.$ (13)

###### Proof.

We can find $q$ big enough so that $R^{q}$ is acyclic, because $R$ is a simple
relation. We choose a $i\in\mathbb{N}$ such as $iq>j$. We fix $r=iq$. We also
have that $R^{r}$ is also acyclic. By Corollary 4.8, we have that
$K_{R^{j}}=K_{R^{r}}$. By Theorem 5.5, we know that $\dim
H_{0}(K_{R^{j}})=\text{ number of connected components of }R^{r}$. ∎

If $G_{R}$ has more than one connected component, we apply this theorem for
each connected component of $G_{R}$ by using similar arguments as the proof of
Theorem 5.5. From preceding results, if $\operatorname*{Dom\,}R\neq X$ but
$\operatorname*{Im\,}R=X$, we can redo the proofs with $L_{R^{j}}$. Another
approach is to use $R^{-1}$, because $\operatorname*{Dom\,}R^{-1}=X$.

######  Remark 5.7.

In Example 5.2, it is a simple relation. We have $R_{2}^{4}$ is acyclic. The
graph of $R_{2}^{4}$ is shown in Figure 5. It has two connected components and
the bar code from Figure 4(b) has $2$ bars goes to infinity. It is expected
from Theorem 5.6.

Figure 5: The graph of $R_{2}^{4}$ from Example 5.2. $G_{R_{2}^{4}}$ has 2
connected components.

We have shown earlier in Corollary 4.10 and Proposition 4.12 that a strongly
connected self-relation $R$ is shift equivalent to a matrix $J$, if $tr(R)>0$.
But we will like to have a result for any strongly connected relations. But,
first we need some definition and other results from other papers. Let
$gcd(a,b)$ be the great common divisor of $a$ and $b$. We define :

$q=gcd(n_{1},n_{2},n_{3},\ldots)$ (14)

where $n_{i}$ is the length of a cycle and $i\in\mathbb{I}$ is the set of all
different cycles from $R$.

We obtain this proposition :

######  Proposition 5.8 (Proposition 6.12 in [26]).

Let $R$ be a strongly connected self-relation on $X$, $(j,p)$ be the eventual
period and $q$ defined by (14). We have $q|j$.

Let’s define a new equivalence relation $\sim_{q}$ for a strongly connected
self-relation $R$. We say that $x\sim_{q}y$, if for each $(x,y)$-walk has
length equal to $0$ modulo $q$. It is an equivalence relation.

######  Proposition 5.9 (Proposition 6.16 in [26]).

Let $R$ be a strongly connected self-relation on $X$. Let $q$ defined as (14).
Then, $\sim_{q}$ is an equivalence relation in $X$ with exactly $q$ distinct
equivalence classes.

We need one more Lemma before showing our final result.

######  Lemma 5.10 (Lemma 6.25 in [26]).

Let $R$ be a strongly connected self-relation on $X$ and $(j,p)$ an eventual
period. Then,

$x\sim_{q}x^{\prime}\implies R^{j}(x)=R^{j}(x^{\prime}).$ (15)

We are going to show that the number of class equivalence of $\sim_{q}$ is
equal to $\dim(H_{0}(K_{R^{j}}))$ for a strongly connected self-relation with
eventual period $(j,p)$.

######  Theorem 5.11.

Let $R$ be a finite self-relation on $X$ with an eventual period $(j,p)$, $R$
is strongly connected, $q$ defined by (14). Then, we have :

$\text{number of
}[x]_{\sim_{q}}=q=\dim(H_{0}(K_{R^{j}}))=\dim(H_{0}(L_{R^{j}})).$ (16)

###### Proof.

We show that for any $x,y\in X$, if $x\sim_{q}y$, then $x$ and $y$ are edge-
connected and if $x\not\sim_{q}y$, then $x$ and $y$ are not edge-connected.

First, we suppose that $x\sim_{q}y$. By Lemma 5.10, we have that
$R^{j}(x)=R^{j}(y)\neq\emptyset$. There exists a $z\in R^{j}(x)$. It implies
that $[x,z]$ and $[y,z]$ are in $K_{R^{j}}$. So, each vertex in the same
equivalence class is edge-connected.

Now, we suppose that, $x\not\sim_{q}y$. There exists a $(x,y)$-walk of length
$n$ modulo $q$ where $n\neq 0$. Let show that $R^{j}(x)\cap
R^{j}(y)=\emptyset$ . Let’s suppose there exists a $z\in R^{j}(x)\cap
R^{j}(y)$. This implies there exists a $(x,z)$-walk of length $j$ and a
$(y,z)$-walk of length $j$. But, from Proposition 5.8, $q|j$. This implies
$x\sim_{q}z$ and $y\sim_{q}z$. But $\sim_{q}$ is an equivalence relation. We
obtain that $x\sim_{q}y$ which is a contradiction. We obtain that
$x\not\sim_{q}y$ implies $R^{j}(x)\cap R^{j}(y)=\emptyset$. We obtain that if
$x\sim_{q}y$ then they are edge-connected. But, if $x\not\sim_{q}y$, then they
are not edge-connected. There is $q$ different equivalence classes. The proof
is complete. ∎

For the case of $R$ is an arbitrary relation, it is harder to find its
homology $H_{0}$. Also, for higher dimensions of the homology groups, it’s
hard to tell what happens. Further investigations are needed for both cases.

Now, we return to the filtrations defined earlier. There are two other types
of filtrations that we can use. If $R$ is a self-relation on $X$ with
$\operatorname*{Dom\,}R=X=\operatorname*{Im\,}R$, then we can use both
filtrations. But we obtain the same bar codes for both. That holds because,
for each $i\in\mathbb{N}$, $|K_{R^{i}}|$ is homotopically equivalent to
$|L_{R^{i}}|$ for any self-relation. We might need to come with other types of
filtration. We suggest two other types of filtration.

It will be interesting to use a zigzag filtration [5] with $K_{R^{i}}$ and
$L_{R^{i}}$ by alternating them. It will probably depend on the relation.
Further investigations are needed.

We will present an interesting bi-filtration with $K_{R^{m}}$ and $L_{R^{n}}$.
We have that, if $K_{R_{m}}\subset K_{R_{m+1}}$ and $L_{R^{n}}\subset
L_{R^{n+1}}$, then $K_{R^{m}}\cap L_{R^{n}}\subset K_{R^{m+1}}\cap L_{R^{n}}$
and $K_{R^{m}}\cap L_{R^{n}}\subset K_{R^{m}}\cap L_{R^{n+1}}$ for all
$m,n\in\mathbb{N}$. We obtain this bi-filtration :

${\vdots}$${\vdots}$${\ldots}$${K_{R^{m}}\cap L_{R^{n}}}$${K_{R^{m+1}}\cap
L_{R^{n}}}$${\ldots}$${\ldots}$${K_{R^{m}}\cap L_{R^{n+1}}}$${K_{R^{m+1}}\cap
L_{R^{n+1}}}$${\ldots}$${\vdots}$${\vdots}$

The computation of the bi-filtration is also finite. Because the relation $R$
is finite and $\operatorname*{Dom\,}R=X=\operatorname*{Im\,}R$. We obtain an
eventual period $(j,p)$. In the bi-filtration, there are, at maximum, $j^{2}$
different simplicial complexes to compute.

One may ask why the intersection is a good idea to consider. Let’s explain it
in more details. Let $R$ be a self-relation on $X$ with
$\operatorname*{Dom\,}R=X=\operatorname*{Im\,}R$ and $m,n\in\mathbb{N}$. Let
$\sigma\in K_{R^{m}}\cap L_{R^{n}}$ where $\sigma=[x_{1},x_{2},\ldots,x_{d}]$.
Then, there exists $x_{\omega}\in X$ such that $x_{i}R^{m}x_{\omega}$ and
there exists $x_{\alpha}\in X$ such that $x_{\alpha}R^{n}x_{i}$ for all $i$.
Another way to see this is, for each $x_{i}\in\sigma$, there exists a
$(x_{\omega},x_{\alpha})$-walk of length $m+n$ passing through $x_{i}$. We can
subdivide this $(x_{\omega},x_{\alpha})$-walk into a $(x_{\omega},x_{i})$-walk
of length $m$ and a $(x_{i},x_{\alpha})$-walk of length $n$. So, by only the
existence of a simplex $\sigma$ in $K_{R^{m}}\cap L_{R^{n}}$, each vertex of
$\sigma$, it has a walk with a common starting point and a common ending point
of same length going through the vertex. It will be interesting to study these
Dowker complexes when $m$ tends to infinity, $n$ tends to infinity or both.

##  6 Conclusion

In summary, we used the Dowker complexes to study some properties of self-
relation. First, we defined the right morphism and left morphism. We also
generalized it to the case of multivalued maps called multi-right morphism and
multi-left morphism. The existence of a right or multi-right morphism between
$R_{1}$ and $R_{2}$ implies that the $K_{R_{1}}$ is included in $K_{R_{2}}$.
Similarly, the existence of a left or a multi-left morphism between $R_{1}$
and $R_{2}$ implies that $L_{R_{1}}$ is included in $L_{R_{2}}$. We have shown
that two relations are conjugate implies that they have homotopically
equivalent Dowker complexes. We have also shown that if two relations are
shift equivalent, then their Dowker complexes are homotopically equivalent at
some power of the relations. We were interested in self-relation which is
equivalent of a type of directed graph. We have obtained two nice properties.
If $R$ is finite and $\operatorname*{Dom\,}R=X=\operatorname*{Im\,}R$, then we
have that $K_{R^{i}}\leq K_{R^{i+1}}$ and $L_{R^{i}}\leq L_{R^{i+1}}$ for all
$i\in\mathbb{N}$. Moreover, there exists a $j\in\mathbb{N}$ such as
$K_{R^{j}}=K_{R^{i+j}}$ and $L_{R^{j}}=L_{R^{i+j}}$ for all $i\in\mathbb{N}$.
With these two properties, we defined two filtrations with
$K_{R^{i}}\hookrightarrow K_{R^{i+1}}$ and $L_{R^{i}}\hookrightarrow
L_{R^{i+1}}$. Also, the filtration ends at some finite time. Finally, we
proved some results about the $0$th homology for some types of self-relation
at some power. We also proposed the intersection filtration and the zigzag
filtration.

We have put some foundations to study directed graph using Dowker complexes.
Moreover, we think it might be a useful tool to study the dynamics of finite
data define by a directed graph of Dowker complexes. Let $R$ be a self-
relation with an eventual period $(j,p)$. The positive or forward invariant is
given by the existence of a simplex in $K_{R^{j}}$ when $j$ converges to
infinity. The negative or backward invariant is given by the existence of a
simplex in $L_{R}^{j}$ when $j$ converges to infinity. But, by the
stabilization of Dowker complexes, we can compute it in finite time. Finally,
if we want to study the invariant of $R$, this is given by the existence of a
simplex in $K_{R^{j}}\cap L_{R^{j}}$ which is the intersection of the forward
and the backward invariant. But further investigations are needed. The idea is
to use the structure of the Dowker complexes to encode the dynamics of finite
data.

## References

  * [1] K. Ambrose, S. Huntsman, M. Robinson, and M. Yutin.  Topological differential testing.  CoRR, abs/2003.00976, 2020.
  * [2] R. Atkin.  Mathematical Structure in Human Affairs.  London, Heinemann, 1974.
  * [3] R. Atkin.  Q-analysis: A hard language for the soft sciences.  Futures, Heinemann, 10(6), 1978.
  * [4] A. Björner.  Topological methods.  Handb. Comb., 2:1819–1872, 1995.
  * [5] G. Carlsson and V. de Silva.  Zigzag persistence.  Found Comput Math, 10, 2010.
  * [6] S. Chowdhurry and F. Mémoli.  A functorial Dowker theorem and persistent homology of asymmetric networks.  Journal of Applied and Computational Topology, 2:115–175, 2018\.
  * [7] C. Conley.  Isolated Invariant Sets and the Morse Index.  American Mathematical Society, 1978.
  * [8] S. Day, O. Junge, and K. Mischaikow.  A rigorous numerical method for the global analysis of infinite-dimensional discrete dynamical systems.  SIAM J. Applied Dynamical Systems, 3(2):117–160, 2004.
  * [9] D. Desjardins Côté.  From finite vector field data to combinatorial dynamical systems in the sense of forman.  arXiv, 2021.
  * [10] C. Dowker.  Homology groups of relations.  Annals of Mathematics, pages 84–95, 1952.
  * [11] H. Edelsbrunner and J. L. Harer.  Computational Topology : An Introduction.  American Mathematical Society, 2010.
  * [12] M. Erdmann.  Topology of privacy: Lattice structures and information bubbles for inference and obfuscation.  arXiv, 2017.
  * [13] R. Forman.  Combinatorial vector fields and dynamical systems.  Mathematische Zeitschrift, 228:629–681, 1998.
  * [14] R. Ghrist, D. Lipsky, J. Derenick, and A. Speranzon.  Topological landmark-based navigation and mapping.  https://www2.math.upenn.edu/~ghrist/preprints/landmarkvisibility.pdf.  2012\.
  * [15] K. Hang Kim and F. W. Roush.  On strong shift equivalence over a boolean semiring.  Ergod. Th. and Dynam. Sys., 6:81–97, 1986.
  * [16] T. Kaczynski, K. Mischaikow, and M. Mrozek.  Computational Homology.  Springer, 2004.
  * [17] T. Kaczynski and M. Mrozek.  Conley index for discrete multivalued dynamical systems.  Topology and Its Appl., 65:83–96, 1995.
  * [18] T. Kaczynski, M. Mrozek, and T. Wanner.  Towards a formal tie between combinatorial and classical vector field dynamics.  Journal of Computational Dynamics, 3(1):17–50, 2016.
  * [19] W. D. Kalies, K. Mischaukow, and R. C.A.M Vandervorst.  Lattice structures for attractors i.  Journal of Computational Dynamics, 1(2):307–338, 2014.
  * [20] W. D. Kalies, K. Mischaukow, and R. C.A.M Vandervorst.  Lattice structures for attractors ii.  Foundations of Computational Mathematics, 16:1151–1191, 2016.
  * [21] W. D. Kalies, K. Mischaukow, and R. C.A.M Vandervorst.  Lattice structures for attractors iii.  Journal of Dynamics and Differential Equations, 34:1729–1768, 2022\.
  * [22] K. H. Kim.  Boolean Matrix Theory and Applications, volume (Monographs and textbooks in pure and applied mathematics, v. 70).  New York:Dekker, 1982.
  * [23] M. Lipiński, J. Kubica, M. Mrozek, and T. Wanner.  Conley-Morse-Forman theory for generalized combinatorial multivector fields on finite topological spaces.  arXiv:1911.12698 [math.DS], pages 1–44, 2020.
  * [24] G. Minian Elias.  The geometry of relations.  Order, 27:213–224, 2010.
  * [25] M. Mrozek, R. Srzednicki, Thorpe J., and Th. Wanner.  Combinatorial vs classical dynamics : Recurrence.  Commun. Nonlinear Sci. Numer. Simul., 108(106226):1–30, 2022.
  * [26] Marian Mrozek and Mateusz Przybylski.  The szymczak functor on the category of finite sets and finite relations.  arXiv, 2022.
  * [27] J. R. Munkres.  Elements of Algebraic Topology.  Addison-Weslay, Cambridge, 1984.
  * [28] M. Robinson.  Cosheaf representations of relations and Dowker complexes.  Journal of Applied and Computational Topology, 6:27–63, 2022.
  * [29] A. Szymczak.  The Conley index for disccrete dynamical system.  Topology Appl., 66:215–240, 1995.
  * [30] A. Szymczak.  Index Pairs : From Dynamics to Combinatorics and Back.  Ph.D. thesis, Georgia Inst. Tech., 1999.