# Sequents, barcodes, and homology

Saugata Basu, Negin Karisani, Laxmi Parida

###### Abstract.

We consider the problem of generating hypothesis from data based on ideas from
logic. We introduce a notion of barcodes, which we call sequent barcodes, that
mirrors the barcodes in persistent homology theory in topological data
analysis. We prove a theoretical result on the stability of these barcodes in
analogy with similar results in persistent homology theory. Additionally we
show that our new notion of barcodes can be interpreted in terms of a
persistent homology of a particular filtration of topological spaces induced
by the data. Finally, we discuss a concrete application of the sequent
barcodes in a discovery problem arising from the area of cancer genomics.

##  1\. Introduction

We introduce a new method for generating causal hypotheses from data. Our
method draws inspiration from classical logic (sequent calculus) on one hand
and the relatively new discipline of topological data analysis (or more
precisely the theory of persistent homology) on the other. Our data consists
of a finite number of labeled sets of two types:

  1. (a)

the causal ones which we label by $A,B,C,\ldots$ using letters from the
beginning of the alphabet (these could for example represent genotypes of cell
lines);

  2. (b)

the effect ones which we label by $X,Y,Z,\ldots$ using letters from the end of
the alphabet (these could for example represent phenotypes of cell lines).

The data sets (both causal and effect) are all assumed to be subsets of some
universal set (for example the set of available cell lines).

The goal is to identify certain set hypotheses of the form

$A\wedge B\wedge C\cdots\Longrightarrow X\vee Y\vee Z\cdots$

which are strongly suggested by the data. In the paper we will refer to these
hypotheses as “sequents” in keeping with the terminology of Gentzen’s sequent
calculus (see for example [17]).

One basic problem that needs to be addressed when using mathematical
techniques on data coming from applications is the issue of noise. There are
many techniques that are being used to filter noise from signal in data.
However, one technique that is closest in spirit (and indeed a motivates our
method) is the technique of persistent homology which is the bedrock of the
field of topological data analysis.

Persistent homology has emerged as an important tool in data analysis for
separating noise from signal in topologically minded applications [10]. We
will define precisely persistent homology later in the paper (see Section A).
For the purposes of this introduction – persistent homology theory associates
to point cloud data coming from some metric space a “barcode” (a finite set of
intervals parameterized by a parameter often identified with time). The bars
which are long (or “persistent” in time) correspond to signals while those
which are short correspond to noise.

In the theory we develop in this paper using sequents we associate a similar
barcode to the given data (though defined in a somewhat different way from
barcodes in persistent homology theory). Each bar in the barcode will
represent a sequent and we postulate that the long bars correspond to sequents
which are more significant – based on the philosophy that these sequents are
the _strongest conclusions lasting the longest_ amongst all possible sequents
according to the data. We interpret these sequents (strongest last longer)
corresponding to long bars as the signal in the data (in analogy with
persistent homology applications).

A key property satisfied by the barcodes coming from persistent homology is
that of stability. Stability theorems [6, 8, 7] state that the persistent
homology or its associated barcode is stable under perturbations of the input
data. This makes persistent homology useful in applications, where the data
often comes from physical measurements with their attendant sources of error.
There are many variations of stability results in the literature. We refer the
reader to [12, Chapter VIII] and [3, §5.6] for a survey of these results. We
prove an analogous stability result (Theorem 5) for sequence barcodes (under
certain restrictions on the data) that mirror the corresponding results for
persistent homology barcodes.

The sequent barcodes that we define in this paper originate in a filtration of
the poset of all possible sequents induced by the data. Posets and simplicial
complexes are very closely related. Every simplicial complex has an associated
poset (namely the face poset), and every poset has an associated simplicial
complex (whose simplices correspond to the chains of the poset). Filtrations
of a poset induce in an obvious manner a filtration of the associated
simplicial complex. Thus it is natural to speculate whether the sequent
barcode can be interpreted as the persistent homology barcode of the
associated simplicial filtration. We show that this is not the case (at least
in the straight-forward way as described above). However, we are able to
establish a mathematical connection between the two notions of barcodes. We
prove (see Theorem 7 below) that the sequent barcodes that we introduce in
this paper are _embedded_ in the persistent barcodes of a certain filtration
of a topological spaces that is naturally associated to the data. In this way
we reconnect our sequent barcodes to the persistent barcodes of topological
data analysis completing the circle.

Finally, we apply the method of sequent barcodes to certain datasets coming
from an application in cancer genomics and show that the hypotheses predicted
by the long bars in the sequent barcodes matches to a great extent those that
are produced by more standard methods.

The rest of the paper is organized as follows. In Section 2 we define sequent
barcodes, discuss some basic examples and state and prove a stability result
giving theoretical justification for their use in generating hypotheses. In
Section 3, we give the necessary background on persistent homology and
establish the connection between our sequent barcodes and the barcodes of
persistent homology theory. Finally in Section 4 we discuss an application of
the ideas introduced in this paper to a problem in cancer genomics. In the
Appendix we give precise definitions of persistent homology and barcodes in
order to make the paper self-contained.

##  2\. Sequents and partial order on them

We assume two finite sets of propositional variables

$V_{A}=\\{a,b,c,\ldots\\},$

and

$V_{S}=\\{x,y,z,\ldots\\}.$

A _sequent_ $\Gamma\vdash\Delta$ is specified by a pair $(\Gamma,\Delta)$
where $\Gamma\subset V_{A}$, $\Delta\subset V_{S}$. We denote the set of all
sequents by $\mathcal{S}=\mathcal{S}(V_{A},V_{S})$.

######  Definition 2.1 (Partial order on $\mathcal{S}$).

If $s=(\Gamma\vdash\Delta),s^{\prime}=(\Gamma^{\prime}\vdash\Delta^{\prime})$
are two sequents we will denote $s\preceq s^{\prime}$ if
$\Gamma\subset\Gamma^{\prime}$ and $\Delta\subset\Delta^{\prime}$.

######  Remark 1.

We identify a sequent $s=(\Gamma\vdash\Delta)$ with the element

$\bigvee_{a\in\Gamma}\neg a\vee\bigvee_{x\in\Delta}x$

in the free Boolean algebra $\mathcal{B}(V)$ generated by $V=V_{A}\cup V_{S}$.

######  Remark 2.

We should think of the partial order as saying that $s\preceq s^{\prime}$, if
from the sequent $s$ alone it is possible to deduce $s^{\prime}$ (in sequent
calculus terminology this means being able to deduce $s^{\prime}$ from $s$ by
successive applications of the (left and right) weakening and interchange
rules).

We will define (depending on the data maps to be introduced below) two kinds
of _filtrations_ of the sequent poset $\mathcal{S}$ introduced above. To each
such filtration we will associate a barcode. In order to define these barcodes
we need a few preliminary definitions.

######  Definition 2.2 (Minimal elements of a poset).

Given any poset $(P,\preceq)$ we denote by $\mathrm{Min}(P)$ the set of
minimal elements of $P$.

######  Definition 2.3 (Filtrations of posets).

We call an indexed family

$\mathcal{F}=(P_{t})_{t\in[0,1]}$

of posets to be a filtration of posets if for each $t,t^{\prime},0\leq t\leq
t^{\prime}\leq 1$, $P_{t}\subset P_{t^{\prime}}$.

######  Definition 2.4 (Barcodes of filtrations of posets).

Let $\mathcal{F}=(P_{t})_{t\in[0,1]}$ be a filtration of posets. For $p\in
P=P_{1}$, we denote by

$I_{p}(\mathcal{F})=\\{t\in[0,1]\mid p\in\mathrm{Min}(P_{t})\\}.$

We denote

$\mathrm{barcode}(\mathcal{F})=\\{(p,I_{p}(\mathcal{F}))\mid p\in
P,I_{p}\neq\emptyset\\},$

and call it the _barcode of the filtration $\mathcal{F}$_.

######  Remark 3.

Note that in Definition 2.4, for $p\in P$, if $I_{p}$ is non-empty then it is
equal to a half-closed interval $[s,t)$. In this case we will refer to $s$ as
the “birth-time” and $t$ as the “death time” of $p$ in the filtration.

###  2.1. Data maps

Till now the discussion of the sequent poset above had nothing to do with
data. We now introduce certain maps which we call data maps, which connects
the sequent posets with the data. This will also allow us to define certain
filtrations on the sequent poset (depending on the data maps). For this
purpose, we first fix a measure space $(X,m)$, with $m(X)=1$, and let
$\mathfrak{M}$ denote the set of measurable subsets of $X$. For instance $X$
could be a finite set with the counting measure normalized so that $m(X)=1$.
In this case $\mathfrak{M}=2^{X}$.

######  Definition 2.5 (Data maps).

We will call a map

$\halign{\hbox to\displaywidth{$\hfil\displaystyle#\hfil$}\cr
0.0pt{\hfil$\displaystyle[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M},\crcr}}$

that maps each element of $V_{A},V_{S}$ to a measurable subset of
$\mathfrak{M}$ a _data map_.

A data map allows to define filtrations of the sequent poset and thus
associate barcodes.

###  2.2. Filtration of the poset of sequents and their barcodes

######  Definition 2.6 (Filtration in sequent space).

A filtration of the poset of sequents is a filtration of posets
$\mathcal{F}=(\mathcal{S}_{t})_{t\in[0,1]}$ where each $\mathcal{S}_{t}$ is a
subposet of the poset $\mathcal{S}$.

We introduce two different filtrations on the poset of sequents. Depending on
the application it might be preferable to choose one over the other – however,
in this paper we do not discuss such choices.

######  Definition 2.7 (Fuzzy inclusions).

Let $S,T\in\mathfrak{M}$. For $0\leq t\leq 1$. We define the predicate
$S\subset_{t}T$ by

$S\subset_{t}T\Longleftrightarrow\frac{m(S\cap T)}{m(S)}\geq t.$

Note that $\subset_{t}$ is not necessarily transitive.

######  Remark 4.

Note that fuzzy set theory is a well-established field of research. In set
theory there are two basic predicates – membership and equality. In fuzzy set
theory the membership relation is allowed to be fuzzy. In Definition 2.7 on
the other hand we let the inclusion relationship (which generalizes equality)
to be fuzzy. It is interesting to note that in [1, Section 15.6] the authors
make the remark – "In topos theory, both (membership and equality) may be
fuzzy, but in fuzzy set theory, only membership is allowed to be". Our notion
of fuzziness as defined above thus straddles the two worlds of fuzzy set
theory and topos theory.

######  Definition 2.8 (Filtration I).

For $0\leq t\leq 1$, and a data map $[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M}$, we define

$\mathcal{S}^{\prime}_{t}([[\cdot]])=\left\\{(\Gamma\vdash\Delta)\in\mathcal{S}\mid\bigcap_{a\in\Gamma}[[a]]\subset_{1-t}\bigcup_{x\in\Delta}[[x]]\right\\}.$

Note that

$\mathcal{S}^{\prime}_{1}([[\cdot]])=\mathcal{S},$

and for $0\leq t\leq t^{\prime}\leq 1$

$\mathcal{S}^{\prime}_{t}([[\cdot]])\subset\mathcal{S}^{\prime}_{t^{\prime}}([[\cdot]]).$

We denote the filtration $(\mathcal{S}^{\prime}_{t}([[\cdot]]))_{t\in[0,1]}$
by $\mathcal{F}^{\prime}([[\cdot]])$.

######  Definition 2.9 (Filtration II).

For $0\leq t\leq 1$, and a data map $[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M}$, we define

$\mathcal{S}^{\prime\prime}_{t}([[\cdot]])=\left\\{(\Gamma\vdash\Delta)\in\mathcal{S}\mid
m\left(\bigcup_{a\in\Gamma}[[a]]^{c}\cup\bigcup_{x\in\Delta}[[x]]\right)\leq
1-t\right\\},$

where for any $Y\in\mathfrak{M}$, $Y^{c}=X-Y\in\mathfrak{M}$.

Note again that

$\mathcal{S}^{\prime\prime}_{1}([[\cdot]])=\mathcal{S},$

and for $0\leq t\leq t^{\prime}\leq 1$

$\mathcal{S}^{\prime\prime}_{t}([[\cdot]])\subset\mathcal{S}^{\prime\prime}_{t^{\prime}}([[\cdot]]).$

We denote the filtration $(\mathcal{S}^{\prime\prime}_{t})_{t\in[0,1]}$ by
$\mathcal{F}^{\prime\prime}([[\cdot]])$.

The barcodes $\mathrm{barcode}(\mathcal{F}^{\prime}([[\cdot]]))$,
$\mathrm{barcode}(\mathcal{F}^{\prime\prime}([[\cdot]]))$, give important
information about the implicational information contained in the data (i.e. in
the data map $[[\cdot]]$).

###  2.3. Example

We discuss an example with $V_{A}=\\{a,b\\}$, $V_{S}=\\{x,y\\}$,
$X=\\{1,2,3,4,5\\}$ with the counting measure and
$[[\cdot]]_{A},[[\cdot]]_{S}$ defined below.

$[[a]]_{A}=\\{1,2,3,4\\},\ \ \ \ \ [[b]]_{A}=\\{2,3,4,5\\},$
$[[x]]_{S}=\\{1,2,3\\},\ \ \ \ \ \ \ \ \ \ \ [[y]]_{S}=\\{3,4,5\\}.$

The poset $\mathcal{S}(V)$ along with the “birth times” of each sequent in
$\mathcal{S}(V)$ is shown in Figure 1.

Figure 1. The poset $\mathcal{S}(V)$.

The sub-posets that appear in the filtration
$\mathcal{F}^{\prime\prime}([[\cdot]])$ (Filtration II) induced by the above
data with the minimal elements marked in black rectangles are shown in Figure
2.

(a) $t=0$

(b) $t=0.2$

(c) $t=0.4$

(d) $t=0.6$

(e) $t=0.8$

(f) $t=1$

Figure 2. Sub-posets $\mathcal{S}^{\prime\prime}_{t}([[\cdot]])$ in the
filtration when $t$ varies from 0 to 1.

Finally, we show the $\mathrm{barcode}(\mathcal{F}^{\prime\prime}([[\cdot]])$
in Figure 3.

Figure 3. The $\mathrm{barcode}(\mathcal{F}^{\prime\prime}([[\cdot]]))$.

###  2.4. Stability of sequent barcodes

As mentioned in the Introduction, a very important property of barcodes
arising in the theory of persistent homology is that of stability. The
stability property implies that small changes in the data cases only small
changes in the barcode. This property is key to the utility of barcodes in
practice. In this section we discuss an analogous property for sequent
barcodes. In the following discussion we only consider Filtration $I$ and omit
$I$ from the subscript.

The stability property for sequent barcodes should imply that with a properly
defined notion of distance between two sequent barcodes and that between two
data maps, one can bound the former in terms of the latter. With this in mind,
we first define notion of distances between sequent two barcodes corresponding
to two filtrations and also a distance between two data maps.

####  2.4.1. Distance between barcodes of two different filtrations of a fixed
poset

######  Definition 2.10 (Distance between sequence barcodes of two
filtrations).

Suppose
$\mathcal{F}=(P_{t})_{t\in[0,1]},\mathcal{F}^{\prime}=(P_{t}^{\prime})_{t\in[0,1]}$
be two filtrations of a poset $P$. We denote

$\textsf{barcode-dist}(\mathcal{F},\mathcal{F}^{\prime})=\sum_{p\in
P}|I_{p}(\mathcal{F})\Delta I_{p}(\mathcal{F}^{\prime})|,$

$\cdot\Delta\cdot$ denotes symmetric difference.

######  Definition 2.11 (Distance between two data maps).

Given $[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M},[[\cdot]]^{\prime}:V_{A}\cup
V_{S}\rightarrow\mathfrak{M},$ we denote

$\textsf{data-dist}([[\cdot]],[[\cdot]]^{\prime})=\sum_{v\in V_{A}\cup
V_{S}}m([[v]]\Delta[[v]]^{\prime}).$

####  2.4.2. Assumptions

We will prove our stability result under certain assumptions on the data maps
which will be usually satisfied in applications.

The first assumption on the data map is the property of being
${\varepsilon}$-granular.

######  Definition 2.12 (${\varepsilon}$-granular).

For $0<{\varepsilon}\leq 1$, we will say that a data map: $[[\cdot]]:V_{a}\cup
V_{S}\rightarrow\mathfrak{M}$ is ${\varepsilon}$-granular if for each $a\in
V_{A},x\in V_{S}$, $m([[a]]),m([[x]])>{\varepsilon}$.

The second assumption that we need is to restrict our attention to those
sequents $\Gamma\vdash\Delta$, whose antecedent $\Gamma$ is sufficiently
significant given the data. This is quantified in the following definition.

######  Definition 2.13.

For $0\leq\delta\leq 1$, and a given map: $[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M}$, we denote by $\mathcal{F}_{\delta}([[\cdot]])$
the sub-filtration of $\mathcal{F}^{\prime}([[\cdot]])$ in which only sequents
$s=(\Gamma\vdash\Delta)$, with

$m(\bigcap_{b\in\Gamma}[[b]])/m([[a]])>\delta$

appear for each $a\in\Gamma$.

We are now in a position to state and prove the following stability result.

######  Theorem 5 (Stability).

Let $0<{\varepsilon},\delta\leq 1$. There exists a constant $C>0$ (depending
on $\mathrm{card}(V_{A}),\mathrm{card}(V_{S}),{\varepsilon},\delta$) such that
for any two ${\varepsilon}$-granular data maps,
$[[\cdot]],[[\cdot]]^{\prime}:V_{A}\cup V_{S}\rightarrow\mathfrak{M},$ such
that the set of sequents appearing in $\mathcal{F}_{\delta}([[\cdot]])$ and
$\mathcal{F}_{\delta}([[\cdot]]^{\prime})$ are the same,

$\textsf{barcode-
dist}(\mathcal{F}_{\delta}([[\cdot]]),\mathcal{F}_{\delta}([[\cdot]]^{\prime}))\leq
C\cdot\textsf{data-dist}([[\cdot]],[[\cdot]]^{\prime}).$

The proof of the theorem will follow from the following lemma. For a sequent
$s=(\Gamma\vdash\Delta)$, and a map $[[\cdot]]:V_{A}\cup
V_{S}\rightarrow\mathfrak{M}$, we denote

$t(s,[[\cdot]])=\inf\\{t\;\mid\;s\in\mathcal{S}_{t}^{\prime}([[\cdot]]\\}.$

######  Lemma 2.1.

With the same hypothesis as in Theorem 5, there exists a
$C=C(\mathrm{card}(V_{A}\cup V_{S},{\varepsilon},\delta))>0$ such that, for
any sequent $s=(\Gamma\vdash\Delta)$,

$|t(s,[[\cdot]])-t(s,[[\cdot]]^{\prime})|\leq C\cdot\textsf{data-
dist}([[\cdot]],[[\cdot]]^{\prime})$

###### Proof.

Let

$p=m(\bigcap_{a\in\Gamma}[[a]]\cap\bigcup_{x\in\Delta}[[x]]),$
$q=m(\bigcap_{a\in\Gamma}[[a]]),$

so that

$t(s,[[\cdot]])=\frac{p}{q}.$

Similarly, let

$p^{\prime}=m(\bigcap_{a\in\Gamma}[[a]]^{\prime}\cap\bigcup_{x\in\Delta}[[x]]^{\prime}),$
$q^{\prime}=m(\bigcap_{a\in\Gamma}[[a]]^{\prime}),$

so that

$t(s,[[\cdot]]^{\prime})=\frac{p^{\prime}}{q^{\prime}}.$

Let $\Delta p=p^{\prime}-p,\Delta q=q^{\prime}-q$. Without loss of generality
we can assume $\Delta q\geq 0$ (otherwise exchange roles of $s$ and
$s^{\prime}$).

Observe that it follows from the hypothesis that

(2.1) $|\Delta p|,|\Delta q|\leq\mathrm{card}(V_{A}\cup
V_{S})\cdot\textsf{data-dist}([[\cdot]],[[\cdot]]^{\prime}),$

and also that

(2.2) $q\geq\delta\cdot{\varepsilon}.$

Then,

$\displaystyle\left|\frac{p}{q}-\frac{p^{\prime}}{q^{\prime}}\right|$
$\displaystyle=$ $\displaystyle\left|\frac{p}{q}-\frac{p+\Delta p}{q+\Delta
q}\right|$ $\displaystyle=$ $\displaystyle\left|\frac{p(\Delta q)-(\Delta
p)q}{q(q+\Delta q)}\right|$ $\displaystyle=$
$\displaystyle\left|\frac{p}{q}\cdot\frac{\Delta q}{q+\Delta q}-\frac{\Delta
p}{q+\Delta q}\right|$ $\displaystyle\leq$
$\displaystyle\left|\frac{p}{q}\cdot\frac{\Delta q}{q+\Delta
q}\right|+\left|\frac{\Delta p}{q+\Delta q}\right|$ $\displaystyle\leq$
$\displaystyle\left|\frac{1}{q+\Delta q}\right|\left|(\Delta p+\Delta
q)\right|$ $\displaystyle\leq$ $\displaystyle\frac{1}{q}(|\Delta p|+|\Delta
q|).$

The lemma now follows from (2.1) and (2.2).

∎

###### Proof of Theorem 5.

Let $\mathcal{S}_{\delta}$ denote the set of sequents appearing in
$\mathcal{F}_{\delta}([[\cdot]])$ (equivalently in
$\mathcal{F}_{\delta}([[\cdot]])$). Recall from Definition 2.10 that

$\textsf{barcode-
dist}(\mathcal{F}_{\delta}([[\cdot]]),\mathcal{F}_{\delta}([[\cdot]^{\prime}))=\sum_{s\in\mathcal{S}_{\delta}}|I_{s}(\mathcal{F}_{\delta}([[\cdot]]))\Delta
I_{s}(\mathcal{F}_{\delta}([[\cdot]])^{\prime})|.$

It follows from Lemma 2.1 that there exists a constant
$C=C(\mathrm{card}(V_{A}\cup V_{S}),{\varepsilon},\delta)>0$ such that the
left as well as the right endpoints of the intervals
$I_{s}(\mathcal{F}_{\delta}([[\cdot]])),I_{s}(\mathcal{F}_{\delta}([[\cdot]]^{\prime}))$
differ by at most $C$. The theorem follows. ∎

##  3\. Filtrations posets and persistent homology

In this section we establish a relationship between the barcode of a
filtration of a poset with the persistent homology barcodes of a filtration of
a natural simplicial complex that we associate to the filtration of poset.

We assume that the reader is familiar with the basic definition of barcodes in
the theory of persistent homology. All necessary background is included in the
Appendix (Section A).

There is a very well studied and natural simplicial complex $\Delta(P)$
(called the order complex of the poset) that is associated to a finite poset
$P$. The simplices of $\Delta(P)$ corresponds to chains of the poset $P$.

######  Example 3.1.

Consider the poset whose Hasse diagram is shown below.

$\textstyle{1}$$\textstyle{2}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{5\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{6\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

The order complex $\Delta(P)$ is depicted in Figure 4.

Figure 4. The order complex, $\Delta(P)$

A filtration $\mathcal{F}=(P_{t})_{t\in[0,1]}$ gives rise to a filtration of
$\Delta(\mathcal{F})=(\Delta(P_{t}))_{t\in[0,1]}$. It is natural to try to
establish a connection between $\mathrm{barcode}(\mathcal{F})$ and
$\mathrm{barcode}(\Delta(\mathcal{F}))$ where for any filtration
$(\Delta)_{t})_{t\in[0,1]}$ we denote by
$\mathrm{barcode}((\Delta_{t})_{t\in[0,1]})$ the persistent homology barcode
of the filtration $(\Delta_{t})_{t\in[0,1]}$ (see Definition A.9).

Unfortunately, the order complex $\Delta(P)$ of a poset $P$, while being a
very useful topological object for studying properties of the poset $P$, the
homology groups of $\Delta(P)$ does not retain enough information about the
$\mathrm{Min}(P)$. Note that the sets $\mathrm{Min}(P_{t}),t\in[0,1]$ play a
crucial role in the definition of $\mathrm{barcode}(\mathcal{F})$.

For example consider the barcode of a filtration $\mathcal{F}$ of posets
depicted in Figure 5.

Figure 5. Barcode of the poset filtration $\mathcal{F}$.

The barcode of the order complex of the poset filtration $\mathcal{F}$
depicted above is shown in Figure 6. Notice that this does not give any
information about the barcode of the poset filtration $\mathcal{F}$ (defined
in Figure 5).

Figure 6. Barcode of the order complex of the poset filtration
$\Delta(\mathcal{F})$.

In order to remedy this deficiency of the order complex we introduce a variant
of the order complex which we call denote by $\widetilde{\Delta}(P)$.

The key difference between $\Delta(P)$ and $\widetilde{\Delta}(P)$ is that
instead of including a simplex of dimension $p$ for every chain $c_{p}$ in $P$
of length $p+1$, we include a certain iterated based suspension,
$\widetilde{\Delta}(c_{p})$ that we define next.

We define $\widetilde{\Delta}(c_{p})$ for a chain $c_{p}=(s_{0}\prec
s_{1}\prec\cdots\prec s_{p})$ of $P$ of length $p+1$ by induction. Let for
$0\leq i\leq p$, $c_{i}$ denote the chain $s_{0}\prec\cdots\prec s_{i}$.

For any based simplicial space $(X,x_{0})$, we denote by $\Sigma(X,x_{0})$ the
reduced suspension

$X\times[0,1]/X\times\\{0\\}\cup X\times\\{1\\}\cup\\{x_{0}\\}\times[0,1].$

The reduced suspension is a basic construction in algebraic topology (see
[15]).

######  Remark 6.

We consider simplicial spaces since the reduced suspension as defined above of
a simplicial complex would in general be a simplicial space.

######  Definition 3.1.

$\displaystyle\widetilde{\Delta}(c_{0})$ $\displaystyle=$
$\displaystyle\Sigma(\emptyset\coprod\\{s_{0}\\},\\{s_{0}\\})$
$\displaystyle=$ $\displaystyle\\{s_{0}\\};$
$\displaystyle\widetilde{\Delta}(c_{i+1})$ $\displaystyle=$
$\displaystyle\Sigma(\widetilde{\Delta}(c_{i})\coprod\\{s_{i+1}\\},\\{s_{i+1}\\}),0<i<p.$

Notice that for any sub-chain $c^{\prime}_{q}=(s_{i_{0}}\prec\cdots\prec
s_{i_{q}})$ of the chain $c_{p}$ there is a natural inclusion

(3.1)
$\widetilde{\Delta}(c^{\prime}_{q})\hookrightarrow\widetilde{\Delta}(c_{p}).$

The simplicial sets $\widetilde{\Delta}(c_{p})$ for $p=0,1,2$ is depicted
below.

Figure 7. The simplicial sets $\widetilde{\Delta}(c_{p})$ for $p=0,1,2$.

We now define

######  Definition 3.2 ($\widetilde{\Delta}(P)$).

We define $\widetilde{\Delta}(P)$ as the union over all chains $c$ of $P$ of
the simplicial space $\widetilde{\Delta}(P)$ modulo the identifications
implied by (3.1)

Note that the space $\widetilde{\Delta}(P)$ as defined above below will be a
simplicial space (whose set of $0$-simplices coincides with $P$) instead of a
simplicial complex. We can obtain canonically a simplicial complex from
$\widetilde{\Delta}(P)$ by taking a barycentric subdivision of each simplex in
$\widetilde{\Delta}(P)$.

Finally for a filtration $\mathcal{F}=(P_{t})_{t\in[0,1]}$, we denote by
$\widetilde{\Delta}(\mathcal{F})$ the filtration
$(\widetilde{\Delta}(P_{t}))_{t\in[0,1]}$ of the corresponding simplicial
spaces defined in Definition 3.2.

We now consider the persistent barcodes of the filtration
$\widetilde{\Delta}(\mathcal{F})$ (see Definition A.9). It is clear from the
construction that if $p\in P$ is a minimal element in poset $P$, then each
chain $c$ of length $\ell$ with $p$ as its minimum element gives rise to a
non-zero homology class in dimensions $0$ to $\ell-1$. Moreover, for an
element $p\succ q$ in the poset $P$, with $p\neq q$, then each chain $c$ of
$P$ with $p$ as its minimum element is a subchain of some chain $d$ with $q$
as its minimum element. The linear maps $\mbox{\rm
H}_{i}(\widetilde{\Delta}(c))\rightarrow\mbox{\rm
H}_{i}(\widetilde{\Delta}(d))$ induced by the inclusion
$\widetilde{\Delta}(c)\hookrightarrow\widetilde{\Delta}(d)$ are $0$ for $i>0$.
This observation leads to the following theorem.

######  Theorem 7.

Let $(P,\preceq)$ be a finite poset and $\mathcal{F}=(P_{t})_{t\in[0,1]}$ a
filtration of $P$ by subposets $P_{t}$, such that $P_{0}=\\{p_{0}\\}$, where
$p_{0}$ is the unique maximal element of $P$. Then, for each $p\in
P-\\{p_{0}\\}$ such that $(p,I_{p})\in\mathrm{barcode}(\mathcal{F})$ with
$I_{p}=[t,t^{\prime}]$, there exists $i\geq 0$ such that
$\mu^{t,t^{\prime}}_{i}(\widetilde{\Delta}(\mathcal{F}))>0$.

###### Proof.

Follows easily from the prior discussion. ∎

As illustration of Theorem 7 we show the barcode
$\mathrm{barcode}(\widetilde{\Delta}(\mathcal{F}))$ for the same poset
filtration $\mathcal{F}$ whose barcode is depicted in Figure 5. Observe that
the barcode of the poset filtration $\mathcal{F}$ depicted in Figure 5 is
_embedded_ in that of the persistent homology filtration
$\widetilde{\Delta}(\mathcal{F})$. Figure 6 shows that this is not true for
the filtration $\Delta(\mathcal{F})$ of the order complex of $P$.

Figure 8. The barcode $\mathrm{barcode}(\widetilde{\Delta}(\mathcal{F}))$.

##  4\. Application

In this section, we present an example using real-world data to demonstrate
the applications of our proposed method.

###  4.1. Genetic dependencies in cancer cell lines

Identifying genes that are essential for the survival and proliferation of
cancer cells is a key step in the development of target-based drugs. This
process can be carried out by analyzing the genetic dependencies of in vitro
cancer cell lines [14]. However, models that are able to automatically predict
gene dependencies are of a great importance to help scientists with this aim
[5, 4]. In a recent study [9], the authors systematically analyze the
predictive power of a comprehensive set of multi-omics features across
hundreds of CRISPR screens in cancer cell lines. They use random forest
regressors to predict gene dependencies and to rank important features. Their
results demonstrate that gene expression values are more predictive for cancer
cell lines vulnerabilities than genomics features. However, they show that
there are a few exceptions such as BRAF, KRAS, and NRAS whose gene
dependencies are best predicted with their own mutation values. In this
section, we examine the latter result using our proposed approach.

###  4.2. Dataset

We downloaded the data from DepMap portal111https://depmap.org/. Gene
dependency values and their probabilities are taken from the
CRISPR_gene_effect and Achilles_gene_dependency files respectively in DepMap
Public 21Q4. The corresponding mutation data are taken unaltered from the
files listed below:
CCLE_mutations_bool_hotspot,
CCLE_mutations_bool_damaging,
CCLE_mutations_bool_nonconserving.
Gene expressions and copy numbers also are taken from the CCLE_expression and
CCLE_gene_cn files respectively. This all amounted to 894 cell lines.

###  4.3. Method

We selected gene dependency probabilities of ‘HRAS (3265)’, ‘KRAS (3845)’,
‘BRAF (673)’, and ‘NRAS (4893)’ and used a threshold of $0.5$ to create the
binary labels. Therefore, we have the propositional variables $V_{S}$ and
$V_{A}$ as follows.

$V_{S}=$ {‘HRAS (3265)’, ‘KRAS (3845)’, ‘BRAF (673)’, ‘NRAS (4893)’},

$\displaystyle V_{A}=$ $\displaystyle\ \\{\text{`HRAS (3265)\\_Hot', `KRAS
(3845)\\_Hot', `BRAF (673)\\_Hot', }$ ‘NRAS (4893)_Hot’, ‘KRAS (3845)_Dam’,
‘BRAF (673)_Dam’, ‘NRAS (4893)_Dam’, ‘HRAS (3265)_NonCon’, ‘KRAS
(3845)_NonCon’, $\displaystyle\text{`BRAF (673)\\_NonCon', `NRAS
(4893)\\_NonCon'\\}},$

where the suffixes _Hot, _Dam, and _NonCon correspond to hotspot, damaging,
and nonconserved mutations respectively. We used definition 2.9 to compute the
filtration of the posets and obtained the associated barcode, shown in Figure
9.

Figure 9. Barcode of the gene dependencies and their corresponding mutations

To compare the results with those reported in [9], we followed their pipeline
to filter and train the regression models using expression values, copy
numbers, and mutation data to predict the gene dependency values. We computed
the Pearson correlation between the predicted values and the observed gene
dependencies and obtained the top predictive features. Table 1 reports the
models’ performance for the selected target genes222The reported results are
similar to those published in [9]..

Table 1. Performance of the trained random forest regressors. Gene |  Pearson correlation
---|---
‘HRAS (3265)’ |  0.48
‘KRAS (3845)’ |  0.81
‘BRAF (673)’ |  0.79
‘NRAS (4893)’ |  0.78

###  4.4. Results and Discussion

Given a set $\Delta$, the longest bar with the sequent $\Gamma\vdash\Delta$,
compared to the shorter bars with sequents $\Gamma^{\prime}\vdash\Delta$,
implies that the features in $\Gamma$ have the most decisive role in
estimating the gene dependencies of the genes in $\Delta$. In Figure 9, for
$\Delta=\\{\text{`KRAS (3845)'}\\}$ we have two long bars corresponded to the
sequents

$\displaystyle\ \vdash$ $\displaystyle[\text{`KRAS (3845)'}],$
$\displaystyle[\text{`KRAS (3845)\\_Hot'}]$ $\displaystyle\ \vdash$
$\displaystyle[\text{`KRAS (3845)'}].$

This implies that among all the elements of $V_{A}$, the most important
features for ‘KRAS (3845)’ are ‘KRAS (3845)_Hot’ and ‘KRAS (3845)_NonCon’.
Similarly, sequents corresponded to the top two longest bars for
$\Delta=\\{\text{`NRAS (4893)'}\\}$ and those for $\Delta=\\{\text{`BRAF
(673)'}\\}$ are listed below.

$\displaystyle\ \vdash$ $\displaystyle[\text{`NRAS (4893)'}],$
$\displaystyle[\text{`NRAS (4893)\\_Hot'}]$ $\displaystyle\ \vdash$
$\displaystyle[\text{`NRAS (4893)'}].$

$\displaystyle\ \vdash$ $\displaystyle[\text{`BRAF (673)'}],$
$\displaystyle[\text{`BRAF (673)\\_Hot'}]$ $\displaystyle\ \vdash$
$\displaystyle[\text{`BRAF (673)'}].$

If $\Delta=\\{\text{`HRAS (3265)'}\\}$, there is not a significant long bar in
Figure 9. However, if we restrict the bars to those with
$\Delta=\\{\text{`HRAS (3265)'}\\}$, among the longest bars, we have the
sequents listed below.

$\displaystyle\ \vdash$ $\displaystyle[\text{`HRAS (3265)'}],$
$\displaystyle[\text{`HRAS (3265)\\_Hot'}]$ $\displaystyle\ \vdash$
$\displaystyle[\text{`HRAS (3265)'}],$

Comparing Figure 9 and Table 1 suggests that the length of a bar corresponded
to the sequent $\Gamma\vdash\Delta$ could be a major factor, if not the only
one, in estimating the predictive power of the features in $\Gamma$. In this
example, ‘HRAS (3265)_NonCon’ for ‘HRAS (3265)’ is not as predictive as ‘KRAS
(3845)_NonCon’ for ‘KRAS (3845)’.

Note that the important features mentioned above are consistent with the top
features obtained from the trained random forest regressors [9].

## References

  * [1] Michael Barr and Charles Wells, _Category theory for computing science_ , Repr. Theory Appl. Categ. (2012), no. 22, xviii+538. MR 2981171
  * [2] Saugata Basu and Negin Karisani, _Persistent homology of semi-algebraic sets_ , 2022.
  * [3] Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot, _The structure and stability of persistence modules_ , SpringerBriefs in Mathematics, Springer, [Cham], 2016. MR 3524869
  * [4] Yu-Chiao Chiu, Siyuan Zheng, Li-Ju Wang, Brian S. Iskra, Manjeet K. Rao, Peter J. Houghton, Yufei Huang, and Yidong Chen, _Predicting and characterizing a cancer dependency map of tumors with deep learning_ , Science Advances 7 (2021), no. 34, eabh1275, _eprint: https://www.science.org/doi/pdf/10.1126/sciadv.abh1275.
  * [5] Guohui Chuai, Hanhui Ma, Jifang Yan, Ming Chen, Nanfang Hong, Dongyu Xue, Chi Zhou, Chenyu Zhu, Ke Chen, Bin Duan, and others, _DeepCRISPR: optimized CRISPR guide RNA design by deep learning_ , Genome biology 19 (2018), no. 1, 1–18, Publisher: Springer.
  * [6] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer, _Stability of persistence diagrams_ , Discrete Comput. Geom. 37 (2007), no. 1, 103–120. MR 2279866
  * [7] David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Yuriy Mileyko, _Lipschitz functions have $L_{p}$-stable persistence_, Found. Comput. Math. 10 (2010), no. 2, 127–139. MR 2594441
  * [8] David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov, _Persistent homology for kernels, images, and cokernels_ , Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 1011–1020. MR 2807543
  * [9] Joshua M. Dempster, John M. Krill-Burger, James M. McFarland, Allison Warren, Jesse S. Boehm, Francisca Vazquez, William C. Hahn, Todd R. Golub, and Aviad Tsherniak, _Gene expression has more power for predicting in vitro cancer cell vulnerabilities than genomics_ , bioRxiv (2020).
  * [10] Tamal Dey and Yusu Wang, _Computational topology for data analysis_ , Cambridge University Press, forthcoming.
  * [11] Herbert Edelsbrunner and John Harer, _Persistent homology—a survey_ , Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 257–282. MR 2405684 (2009h:55003)
  * [12] Herbert Edelsbrunner and John L. Harer, _Computational topology_ , American Mathematical Society, Providence, RI, 2010, An introduction. MR 2572029
  * [13] Negin Karisani, _Applied Topology and Algorithmic Semi-Algebraic Geometry_ , PhD Thesis, Purdue University Graduate School (2022).
  * [14] Ann Lin and Jason M. Sheltzer, _Discovering and validating cancer genetic dependencies: approaches and pitfalls_ , Nature Reviews Genetics 21 (2020), no. 11, 671–682.
  * [15] J. P. May, _A concise course in algebraic topology_ , Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 1999. MR 1702278
  * [16] E. H. Spanier, _Algebraic topology_ , McGraw-Hill Book Co., New York, 1966. MR 0210112 (35 #1007)
  * [17] Gaisi Takeuti, _Proof theory_ , second ed., Studies in Logic and the Foundations of Mathematics, vol. 81, North-Holland Publishing Co., Amsterdam, 1987, With an appendix containing contributions by Georg Kreisel, Wolfram Pohlers, Stephen G. Simpson and Solomon Feferman. MR 882549
  * [18] Shmuel Weinberger, _What is $\ldots$persistent homology?_, Notices Amer. Math. Soc. 58 (2011), no. 1, 36–39. MR 2777589

##  Appendix A Simplicial complexes, filtrations, persistent homology and
persistent barcodes

In this section we give some background on persistent homology for the
reader’s benefit.

###  A.1. Background on homology theory

Homology theory is a classical tool in mathematics for studying topological
spaces. A particular homology theory (such as simplicial, singular, Čech,
sheaf etc. [16]) associates to any topological space $X$, a certain vector
space (assuming we take coefficients in a field) graded by dimension, denoted

$\mbox{\rm H}(X)=\bigoplus_{p\geq 0}\mbox{\rm H}_{p}(X)$

in a functorial way (maps of spaces give rise to linear maps of the
corresponding vector spaces, and compositions are preserved). The dimension of
$\mbox{\rm H}_{p}(X)$ (called the $p$-th Betti number of $X$) has a geometric
meaning. It is equal to the number of independent $p$-dimensional “holes” of
$X$. In particular, the dimension of $\mbox{\rm H}_{0}(X)$ is the number of
connected components of $X$, and if $X$ is a graph embedded in
$\mathrm{R}^{d}$, then the dimension of $\mbox{\rm H}_{1}(X)$ is the number of
“independent cycles” of $X$. The dimension of $\mbox{\rm H}_{1}(X)$ is equal
to $0$ if $X$ is the $2$-dimensional sphere, while it is equal to $2$ is $X$
is the torus, reflecting the fact that the sphere does not have
$1$-dimensional holes while the torus has two independent ones. Finally, the
dimension of $\mbox{\rm H}_{2}(X)$ equals $1$ for either the sphere or the
torus indicating that they both have a $2$-dimensional hole.

###  A.2. Simplicial homology

The homology theory that is relevant for this paper is _simplicial homology
theory_ which associates to any simplicial complex $K$ (defined below), its
_simplicial homology groups_ , $\mbox{\rm H}_{*}(K)$. It is useful to think of
simplicial complexes as higher dimensional generalizations of graphs (with no
multiple edges or self loops). A $p$-dimensional simplex is spanned by
$(p+1)$-vertices of the complex (just as an edge in a graph is spanned by two
vertices). An edge in a graph is just a $1$-simplex.

###  A.3. Simplicial complexes

######  Definition A.1.

A _finite simplicial complex_ $K$ is a set of ordered subsets of
$[N]=\\{0,\ldots N\\}$ for some $N\geq 0$, such that if $\sigma\in K$ and
$\tau$ is a subset of $\sigma$, then $\tau\in K$.

######  Notation A.1.

If $\sigma=\\{i_{0},\ldots,i_{p}\\}\in K$, with $K$ a finite simplicial
complex, and $i_{0}<\cdots<i_{p}$, we will denote
$\sigma=[i_{0},\ldots,i_{p}]$ and call $\sigma$ a _$p$ -dimensional simplex of
$K$_. We will denote by $K^{(p)}$ the set of $p$-dimensional simplices of $K$.

A simplicial complex $K$ is a combinatorial object but it comes with an
associated topological space $|K|$ (the so called geometric realization of
$K$), and the simplicial homology groups, $\mbox{\rm H}_{*}(K)$, are actually
topological invariants of $|K|$ (two simplicial complexes having homeomorphic
geometric realizations have isomorphic simplicial homology groups). The
geometric realization functor $|\cdot|$ will play no role in the paper but is
useful to keep in mind for visualization purposes (and also to connect
simplicial homology of a simplicial complex to the notion of homology being a
functor from the category of topological spaces to vector spaces as stated in
the previous paragraphs).

What is simplicial homology ?

Let $K$ denote a finite simplicial complex and for $p\geq 0$, let $K^{(p)}$
denote the set of $p$-dimensional simplices of $K$.

######  Definition A.2 (Chain groups and their standard bases).

Suppose $K$ is a finite simplicial complex. For $p\geq 0$, we will denote by
$C_{p}(K)=C_{p}(K,\mathrm{R})$ (the $p$-th chain group), the
$\mathrm{R}$-vector space generated by the elements of $K^{(p)}$, i.e.

$C_{p}(K)=\bigoplus_{\sigma\in K^{(p)}}\mathbb{Q}\cdot\sigma.$

######  Definition A.3 (The boundary map).

We denote by $\partial_{p}(K):C_{p}(K)\rightarrow C_{p-1}(K)$ the linear map
(called the $p$-th _boundary map_) defined as follows. Since
$\left(\sigma\right)_{\sigma\in K^{(p)}}$ is a basis of $C_{p}(K)$ it is
enough to define the image of each $\sigma\in C_{p}(K)$. We define for
$\sigma=[i_{0},\ldots,i_{p}]\in K^{(p)}$,

$\partial_{p}(K)(\sigma)=\sum_{0\leq j\leq
p}(-)^{j}[i_{0},\ldots,\widehat{i_{j}},\ldots,i_{p}]\in C_{p-1}(K),$

where $\widehat{\cdot}$ denotes omission.

One can easily check that the boundary maps $\partial_{p}$ satisfy the key
property that

$\partial_{p+1}(K)\;\circ\;\partial_{p}(K)=0,$

or equivalently that

$\mathrm{Im}(\partial_{p+1}(K))\subset\ker(\partial_{p}(K)).$

######  Notation A.2 (Cycles and boundaries).

We denote

$Z_{p}(K)=\ker(\partial_{p}(K)),$

(the space of _$p$ -dimensional cycles_) and

$B_{p}(K)=\mathrm{Im}(\partial_{p+1}(K))$

(the space of _$p$ -dimensional boundaries_).

######  Definition A.4 (Simplicial homology groups).

The _$p$ -dimensional simplicial homology group $\mbox{\rm H}_{p}(K)$_ is
defined as

$\mbox{\rm H}_{p}(K)=Z_{p}(K)/B_{p}(K).$

###  A.4. Persistent homology

We now define persistent homology (taken from [2]).

Let $T$ be an ordered set, and $\mathcal{F}=(X_{t})_{t\in T}$, a tuple of
subspaces of $X$, such that $s\leq t\Rightarrow X_{s}\subset X_{t}$. We call
$\mathcal{F}$ a filtration of the topological space $X$.

We now recall the definition of the _persistent homology groups_ associated to
a filtration [11, 18]. Since we only consider homology groups with rational
coefficients, all homology groups in what follows are finite dimensional
$\mathbb{Q}$-vector spaces.

######  Notation A.3.

For $s,t\in T,s\leq t$, and $p\geq 0$, we let $i_{p}^{s,t}:\mbox{\rm
H}_{p}(X_{s})\longrightarrow\mbox{\rm H}_{p}(X_{t})$, denote the homomorphism
induced by the inclusion $X_{s}\hookrightarrow X_{t}$.

######  Definition A.5.

[11] For each triple $(p,s,t)\in\mathbb{Z}_{\geq 0}\times T\times T$ with
$s\leq t$ the _persistent homology group_ , $\mbox{\rm
H}_{p}^{s,t}(\mathcal{F})$ is defined by

$\displaystyle\mbox{\rm H}_{p}^{s,t}(\mathcal{F})$ $\displaystyle=$
$\displaystyle\mathrm{Im}(i_{p}^{s,t}).$

Note that $\mbox{\rm H}_{p}^{s,t}(\mathcal{F})\subset\mbox{\rm H}_{p}(X_{t})$,
and $\mbox{\rm H}_{p}^{s,s}(\mathcal{F})=H_{p}(X_{s})$.

######  Notation A.4.

We denote by $b_{p}^{s,t}(\mathcal{F})=\dim_{\mathbb{Q}}(\mbox{\rm
H}_{p}^{s,t}(\mathcal{F}))$.

Persistent homology measures how long a homology class persists in the
filtration, in other words considering the homology classes as topological
features, it gives an insight about the time (thinking of the indexing set $T$
of the filtration as time) that a topological feature appears (or is born) and
the time it disappears (or dies). This is made precise as follows.

######  Definition A.6.

For $s\leq t\in T$, and $p\geq 0$,

  * •

we say that a homology class $\gamma\in\mbox{\rm H}_{p}(X_{s})$ is _born_ at
time $s$, if $\gamma\notin\mbox{\rm H}_{p}^{s^{\prime},s}(\mathcal{F})$, for
any $s^{\prime}<s$;

  * •

for a class $\gamma\in\mbox{\rm H}_{p}(S_{s})$ born at time $s$, we say that
$\gamma$ _dies_ at time $t$,

    * –

if $i_{p}^{s,t^{\prime}}(\gamma)\notin\mbox{\rm
H}_{p}^{s^{\prime},t^{\prime}}(\mathcal{F})$ for all $s^{\prime},t^{\prime}$
such that $s^{\prime}<s\leq t^{\prime}<t$,

    * –

but $i_{p}^{s,t}(\gamma)\in\mbox{\rm
H}_{p}^{s^{\prime\prime},t}(\mathcal{F})$, for some $s^{\prime\prime}<s$.

######  Remark 8.

Note that the homology classes that are born at time $s$, and those that are
born at time $s$ and dies at time $t$, as defined above are not subspaces of
$\mbox{\rm H}_{p}(X_{s})$. In order to be able to associate a “multiplicity”
to the set of homology classes which are born at time $s$ and dies at time $t$
we interpret them as classes in certain _subquotients_ of $\mbox{\rm
H}_{*}(X_{s})$ in what follows.

First observe that it follows from Definition A.5 that for all $s^{\prime}\leq
s\leq t$ and $p\geq 0$, $\mbox{\rm H}_{p}^{s^{\prime},t}(\mathcal{F})$ is a
subspace of $\mbox{\rm H}^{s,t}_{p}(\mathcal{F})$, and both are subspaces of
$\mbox{\rm H}_{p}(X_{t})$. This is because the homomorphism
$i^{s^{\prime},t}_{p}=i^{s,t}_{p}\circ i^{s^{\prime},s}_{p}$, and so the image
of $i^{s^{\prime},t}_{p}$ is contained in the image of $i^{s,t}_{p}$. It
follows that, for $s\leq t$, the union of $\bigcup_{s^{\prime}<s}\mbox{\rm
H}^{s^{\prime},t}_{p}(\mathcal{F})$ is an increasing union of subspaces, and
is itself a subspace of $\mbox{\rm H}_{p}(X_{t})$. In particular, setting
$t=s$, $\bigcup_{s^{\prime}<s}\mbox{\rm H}^{s^{\prime},s}(\mathcal{F})$ is a
subspace of $\mbox{\rm H}_{p}(X_{s})$.

With the same notation as above:

######  Definition A.7 (Subspaces of $\mbox{\rm H}_{p}(X_{s})$).

For $s\leq t$, and $p\geq 0$, we define

$\displaystyle M^{s,t}_{p}(\mathcal{F})$ $\displaystyle=$
$\displaystyle\bigcup_{s^{\prime}<s}(i^{s,t}_{p})^{-1}(\mbox{\rm
H}^{s^{\prime},t}_{p}(\mathcal{F})),$ $\displaystyle N^{s,t}_{p}(\mathcal{F})$
$\displaystyle=$ $\displaystyle\bigcup_{s^{\prime}<s\leq
t^{\prime}<t}(i^{s,t^{\prime}}_{p})^{-1}(\mbox{\rm
H}^{s^{\prime},t^{\prime}}_{p}(\mathcal{F})),$

######  Remark 9.

The “meaning” of these subspaces are as follows.

  1. (a)

For every fixed $s\in T$, $M^{s,t}_{p}(\mathcal{F})$ is a subspace of
$\mbox{\rm H}_{p}(K_{s})$ consisting of homology classes in $\mbox{\rm
H}_{p}(K_{s})$ which are

“born before time $s$, or born at time $s$ and dies at $t$ or earlier”

  2. (b)

Similarly, for every fixed $s\in T$, $N^{s,t}_{p}(\mathcal{F})$ is a subspace
of $\mbox{\rm H}_{p}(K_{s})$ consisting of homology classes in $\mbox{\rm
H}_{p}(K_{s})$ which are

“born before time $s$, or born at time $s$ and dies strictly earlier than $t$”

We now define certain _subquotients_ of the homology groups of $\mbox{\rm
H}_{p}(K_{s}),s\in T,p\geq 0$, in terms of the subspaces defined above in
Definition A.7.

######  Definition A.8 (Subquotients associated to a filtration).

For $s\leq t$, and $p\geq 0$, we define

$\displaystyle P^{s,t}_{p}(\mathcal{F})$ $\displaystyle=$ $\displaystyle
M^{s,t}_{p}(\mathcal{F})/N^{s,t}_{p}(\mathcal{F}),$ $\displaystyle
P^{s,\infty}_{p}(\mathcal{F})$ $\displaystyle=$ $\displaystyle\mbox{\rm
H}_{p}(K_{s})/\bigcup_{s\leq t}M^{s,t}_{p}(\mathcal{F}).$

We will call

  1. (a)

$P^{s,t}_{p}(\mathcal{F})$ the _space of $p$-dimensional cycles born at time
$s$ and which dies at time $t$_; and

  2. (b)

$P^{s,\infty}_{p}(\mathcal{F})$ the _space of $p$-dimensional cycles born at
time $s$ and which never die_.

Finally, we define:

######  Definition A.9 (Persistent multiplicity, barcode).

We will denote for $s\in T,t\in T\cup\\{\infty\\}$,

(A.1) $\mu^{s,t}_{p}(\mathcal{F})=\dim P^{s,t}_{p}(\mathcal{F}),$

and call $\mu^{s,t}_{p}(\mathcal{F})$ the _persistent multiplicity of
$p$-dimensional cycles born at time $s$ and dying at time $t$ if
$t\neq\infty$, or never dying in case $t=\infty$_.

We will call the set

(A.2)
$\mathcal{B}_{p}(\mathcal{F})=\\{(s,t,\mu^{s,t}_{p}(\mathcal{F}))\mid\mu^{s,t}_{p}(\mathcal{F})>0\\}$

_the $p$-dimensional barcode associated to the filtration $\mathcal{F}$_.

We will call an element
$b=(s,t,\mu^{s,t}_{p}(\mathcal{F}))\in\mathcal{B}_{p}(\mathcal{F})$ a _bar of
$\mathcal{F}$ of multiplicity $\mu^{s,t}_{p}(\mathcal{F}$_).

We now give a concrete example of a barcode associated to a (infinite)
filtration (the following example is taken from [13]).

######  Example A.1.

Let $S$ be the two-dimensional torus (topologically $\mbox{${\bf
S}$}^{1}\times\mbox{${\bf S}$}^{1}$) embedded in $\mathbb{R}^{3}$, and
$\mathcal{F}$ be the filtration of the torus by the sub-level sets of the
height function (depicted in Figure 10). We denote by $S_{\leq t}$ the subset
of the torus having “height” $\leq t$.

We consider homology in dimensions $0$, $1$ and $2$.

Informally, one observes that a $0$-dimensional homology class is born at time
$t_{0}$ which never dies. There are two $1$-dimensional homology classes, the
horizontal loop born at time $t_{2}$ and the vertical loop born at time
$t_{4}$, which also never die. Lastly, there is a $2$-dimensional homology
class born at time $t_{5}$ which never dies. Since there are no homology
classes of the same dimension being born and dying at the same time,
multiplicities in all the cases are 1.

More formally, following Definitions A.7, A.8 and A.9, we obtain:

  1. (Case p = 0)

If $t_{0}\leq t<\infty$ then (using Definition A.7)

$M^{t_{0},t}_{0}(\mathcal{F})=0,$

and hence (using Definitions A.8 and A.9)

$P^{t_{0},t}_{0}(\mathcal{F})=0,\mbox{ and }\mu^{t_{0},t}_{0}(\mathcal{F})=0.$

On the other hand,

$P^{t_{0},\infty}_{0}(\mathcal{F})=\mbox{\rm H}_{0}(S_{\leq t_{0}}),$

implying

$\mu^{t_{0},\infty}_{0}(\mathcal{F})=1.$

  2. (Case p = 1)

For $t_{2}\leq t<\infty$,

$M^{t_{2},t}_{1}(\mathcal{F})=0,$

and hence

$P^{t_{2},t}_{1}(\mathcal{F})=0,\mbox{ and }\mu^{t_{2},t}_{1}(\mathcal{F})=0.$

Moreover,

$P^{t_{2},\infty}_{1}(\mathcal{F})=\mbox{\rm H}_{1}(S_{\leq t_{2}}),$

and therefore,

$\mu^{t_{2},\infty}_{1}(\mathcal{F})=1.$

For $t_{4}\leq t<\infty$,

$M^{t_{4},t}_{1}(\mathcal{F})=N^{t_{4},t}_{1}(\mathcal{F})=\mbox{\rm
H}_{1}(S_{<t_{4}}),$

and hence

$P^{t_{4},t}_{1}(\mathcal{F})=0,\mbox{ and }\mu^{t_{4},t}_{1}(\mathcal{F})=0.$

Moreover,

$P^{t_{4},\infty}_{1}(\mathcal{F})=\mbox{\rm H}_{1}(S_{\leq t_{4}})/\mbox{\rm
H}_{1}(S_{<t_{4}}),$

and therefore

$\mu^{t_{4},\infty}_{1}(\mathcal{F})=1.$

  3. (Case p = 2)

For $t_{5}\leq t<\infty$,

$M^{t_{5},t}_{2}(\mathcal{F})=0,$

and hence

$P^{t_{5},t}_{2}(\mathcal{F})=0,\mbox{ and }\mu^{t_{5},t}_{2}(\mathcal{F})=0.$

Moreover,

$P^{t_{5},\infty}_{2}(\mathcal{F})=\mbox{\rm H}_{2}(S),$

and therefore

$\mu^{t_{5},\infty}_{2}(\mathcal{F})=1.$

Therefore the barcodes are as follows (using Eqn. (A.2)).

${\small\begin{array}[]{ccl}\mathcal{B}_{0}(\mathcal{F})&=&\\{(t_{0},+\infty,1)\\},\\\
\mathcal{B}_{1}(\mathcal{F})&=&\\{(t_{2},+\infty,1),(t_{4},+\infty,1)\\},\\\
\mathcal{B}_{2}(\mathcal{F})&=&\\{(t_{5},+\infty,1)\\}.\end{array}}$

Figure 10 illustrates the corresponding bars. Notice that even though the
filtration $\mathcal{F}$ is an infinite filtration indexed by $\mathbb{R}$,
the barcodes, $\mathcal{B}_{p}(\mathcal{F})$, are finite.

Figure 10. (a) Torus filtered by the sub-level sets of the height function,
(b) corresponding barcodes for homology classes of dimension 0, 1 and 2.