Topological Data Analysis - Exercises

Lucas Moschen, EMAp/FGV February 10, 2021

Contents
1 General topology 2
1.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Homeomorphisms 6
2.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Homotopies 11
3.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Simplicial complexes 15
4.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Homological algebra 19
5.1 Important Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6 Incremental algorithm 23
6.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.2 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

7 Topological inference 28
7.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

8 Datasets have topology 34

8.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

9 Decomposition of persistence modules 36

9.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
9.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

10 Stability of persistence modules 41

10.1 Important definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
10.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1
11 Python tutorial 42

1 General topology
1.1 Important definitions
Definition 1.1.1. A topological space is a pair (X, T ) where X is a set and T is a collection
of subsets of X such that:

1. ∅ ∈ T , X ∈ T .

2. for every infinite collection {Oα }α∈A ⊂ T , we have ∈T.

S
α∈A Oα

3. for every finite collection {Oi }1≤i≤n ⊂ T , we have ∈T.

T
1≤i≤n Oi

Definition 1.1.2. Let x ∈ Rn and r > 0. The open ball of center x and radius r, denoted
B(x, r), is defined as: B(x, r) = {y ∈ Rn , ||x − y|| < r}.
Definition 1.1.3. Let A ⊂ R and x ∈ A. We say that A is open around x if there exists r > 0
such that B(x, r) ⊂ A. We say that A is open if for every x ∈ A, A is open around x.
Definition 1.1.4. Let (X, T ) be a topological space, and Y ⊂ X. We define the subspace
topology on Y as the following set:

T|Y = {O ∩ Y, O ∈ T }

Definition 1.1.5. Let f : X → Y be a map. We say that f is continuous if for every O ∈ U ,

the preimage f −1 (O) = {x ∈ X, f (x) ∈ O} is in T .

1.2 Exercises
Exercise 1. Let X = {0, 1, 2} be a set with three elements. What are the different topologies
that X admits?

Proof. As we know every Topology contains ∅ and {0, 1, 2}, so we can disconsider when writing
the topologies, that is, all below contain these subsets.

• (2) Basic: {∅, {0, 1, 2}} - P({0, 1, 2}).

• (8) With {0}: {{0}} − {{0}, {0, 1}} − {{0}, {1, 2}} − {{0}, {0, 2}} − {{0}, {0, 2}, {0, 1}}
{{0}, {2}, {0, 2}} − {{0}, {2}, {0, 2}, {1, 2}} − {{0}, {2}, {0, 2}, {0, 1}}

• (8) With {1}: {{1}} − {{1}, {0, 1}} − {{1}, {1, 2}} − {{1}, {0, 2}} − {{1}, {1, 2}, {0, 1}}
{{0}, {1}, {0, 1}} − {{0}, {1}, {0, 1}, {1, 2}} − {{0}, {1}, {0, 1}, {0, 2}}

• (8) With {2}: {{2}} − {{2}, {0, 1}} − {{2}, {1, 2}} − {{2}, {0, 2}} − {{2}, {0, 2}, {1, 2}}
{{1}, {2}, {1, 2}} − {{1}, {2}, {1, 2}, {0, 1}} − {{1}, {2}, {1, 2}, {0, 2}}

• (3) No singleton: {{0, 1}} − {{1, 2}} − {{0, 2}}

2
Exercise 2. Let Z be the set of integers. Consider the cofinite topology T on Z, defined as
follows: a subset O ⊂ Z is an open set if and only if O = ∅ or c O is finite. Here, c O = {x ∈
Z, x 6∈ O} represents the complementary of O in Z

Proof. 1. Show that T is a topology on Z.

Let’s verify the three axioms:

(a) ∅ is an open set by definition and Z is open set because c Z = ∅ is finite.

(b) Let {Oα }α∈A ⊂ T . So c O = c α∈A Oα =⇒ O ⊂ Oα , ∀α ∈ A. If
c c c
S
T
α∈A Oα =
∀α, Oα = ∅, then c O = c∅ =⇒ O = ∅ and O is open. On the other hand, if there
exists α ∈ A such that Oα 6= ∅ we have c Oα being finite, so is c O, given the inclusion.
We conclude O is open set.
T 
(c) Let {Oi }1≤i≤n ⊂ T . So c O = c cO . If Oi = ∅ for some
S
1≤i≤n Oi = 1≤i≤n i
1 ≤ i ≤ n, O = ∅ because of the intersection. Alternatively, if ∀i, Oi 6= ∅ we have that
cO
i is finite and a finite union of finites is finite. We conclude that O is open set.

By (a), (b) and (c), T is a topology on Z.

2. Exhibit an sequence of open sets {On }n∈N ⊂ T such that is not an open set.
T
n∈N On

Let On = c {1, ..., n}. Thus c On = {1, ..., n} is finite and

!
\ [ [
c c
On = On = {1, ..., n} = N,
n∈N n∈N n∈N

that is not finite. Therefore, this intersection is not an open set.

Exercise 3. Let x ∈ Rn , and r > 0. Let y ∈ B(x, r). Show that

B(y, r − ||x − y||) ⊂ B(x, r)

Proof. Let z ∈ B(y, r − ||x − y||), so ||z − y|| < r − ||x − y|| =⇒ ||z − y|| + ||x − y|| < r. We can
conclude that, by the triangular inequality,

||x − z|| ≤ ||x − y|| + ||z − y|| < r.

In that sense, z ∈ B(x, r) and B(y, r − ||x − y||) ⊂ B(x, r).

Remark. In the notes, the exercise is to prove B(y, ||x − y||) ⊂ B(x, r), however, this does not
hold, because if we take y next the border of B(x, r), ||x − y|| ≈ r and B(y, r − ) 6⊂ B(x, r).

Exercise 4. Let x, y ∈ Rn , and r = ||x − y||. Show that

 
x+y r
B , ⊂ B(x, r) ∩ B(y, r)
2 2

3
 x+y  r
Proof. Denote m = . Take z ∈ B m, . Thus, using the triangular inequality,
2 2
1
||x − z|| ≤ ||x − m|| + ||m − z|| = ||x − y|| + ||m − z|| < r/2 + r/2 = r
2
1
||y − z|| ≤ ||y − m|| + ||m − z|| = ||y − x|| + ||m − z|| < r/2 + r/2 = r
2
So z ∈ B(x, r), z ∈ B(y, r) and z ∈ B(x, r) ∩ B(y, r). Therefore B(m, 2r ) ⊂ B(x, r) ∩ B(y, r).

Exercise 5. Show that the open balls B(x, r) of Rn are open sets (with respect to the Euclidean
topology).

Proof. We have to prove that for every y ∈ B(x, r), there exists  > 0 such that B(y, ) ⊂ B(x, r).
Put  = r − ||x − y||. As we have proved in exercise 3, B(y, ) ⊂ B(x, r). So B(x, r) is open set.

Exercise 6. Consider X = R endowed with the Euclidean topology. Are the following sets open?
Are they closed?

Proof. 1. [0, 1]. It’s not open set because for every  > 0, B(0, ) = (−, ) 6⊂ [0, 1]. It’s closed
because [0, 1]c = (−∞, 0) ∪ (1, ∞) is an union of two open sets, as we prove in item 3.

2. [0, 1). It’s not open for the same reason as before. It’s not closed because B(1, ) =
(1 − , 1 + ) 6⊂ (−∞, 0) ∪ [1, ∞].

3. (−∞, 1). It’s open because: take x < 1. Put r = 1 − x and take z ∈ B(x, r). If z > x,
|x − z| < 1 − x =⇒ z < 1. If z < x, it follows z < 1. It proves z < 1 and (−∞, 1) is open.
It’s not closed cause ∀ > 0, B(1, ) 6⊂ [1, ∞).

4. the singletons. It’s not open cause ∀ > 0, x+/2 ∈ B(x, ). It’s close cause (−∞, x)∪(x, ∞)
is union of open sets.

5. Q. It’s not open because for every open ball around a rational, there are irrationals, that
is, let x ∈ Q and take  > 0, then there exists y ∈ (R − Q) ∩ B(x, ). It’s not closed for the
same reason, for every irrational, there is rationals for every open ball.
Remark. We shall prove the rationals are dense in the reals. Let x ∈ Q and  > 0. If  is
irrational, take x − /2 ⊂ (x − , x + ). Suppose x − /2 is rational, then 2x−
2 = m
n for
some integers m and n, that is, 2x −  = 2m/n and  = 2(x − m
n) ∈ Q, contradiction. So
there is an irrational in B(x, ). If  is rational, consider

1 1 √
y = √ (x − ) + (1 − √ )(x + ) = (x + ) −  2
2 2

That is a convex combination, so y ∈ B(x, ). Moreover, y is irrational, with a similar proof
by contradiction. This proves the statement.

4
 On the other hand, we must prove for every two irrationals (a, b), there is a rational between
them. Denote c = b − a > 0. Let n ∈ N such that n > 1
c =⇒ cn > 1 =⇒ (bn − an) > 1.
So exists m ∈ (an, bn) =⇒ m/n ∈ (a, b). This proves the second statement.

Exercise 7. A map is continuous if and only if the preimage of closed sets are closed sets.

Proof. First we shall prove that f −1 ( c A) = c (f −1 (A)). Let’s prove the double inclusion. Take
x∈ f −1 ( c A). So there exists y ∈ cA such that f (x) = y. Suppose that x ∈ f −1 (A). It implies
the existence of z ∈ A such that y = f (x) = z, absurd. So x ∈ c (f −1 (A)).
Now take x ∈ c (f −1 (A)). Therefore, ∀y ∈ A, f (x) 6= y. In that case, f (x) ∈ cA =⇒ x ∈
f −1 ( c A). Then we have showed the equality.

Now let’s prove the equivalence. Suppose f is a continuos map and take a closed set F . We
shall prove that f −1 (F ) is closed. Well, c (f −1 (F )) = f −1 ( c F ) is open, because cF is open, by
the continuity. We conclude that f −1 (F ) is closed.
Suppose that for every closed set F , we have f −1 (F ) being closed. We will use that A is open
if c A is closed. This is true because c (c (A)) = A. Take an open set A. c (f −1 (A)) = f −1 ( c A) is
closed, because cA is. Thus f −1 (A) is open and we have proved the continuity of f .

5
2 Homeomorphisms
2.1 Important definitions
Definition 2.1.1. Let (X, T ) and (Y, U) be two topological spaces, and f : X → Y a map. We
say that f is a homeomorphism if

1. f is a bijection,

2. f : X → Y is continuos,

3. f −1 : Y → X is continuos.

If there exists such a homeomorphism, we say that the two topological spaces are homeomorphic.
Definition 2.1.2. Let (X, T ) be a topological space. We say that X is connected if for every
open sets O, O0 ∈ T such that O ∩ O0 = ∅ (i.e., they are disjoint), we have

X = O ∪ O0 =⇒ O = ∅ or O0 = ∅.

Definition 2.1.3. Let (X, T ) be a topological space. Suppose that there exists a collection of n
non-empty, disjoint and connected open sets (O1 , ..., On ) such that
[
Oi = X.
1≤i≤n

Then we say that X admits n connected components.

Definition 2.1.4. Let (X, T ) be a topological space, and n ≥ 0. We say that it has dimension
n if the following is true: for every x ∈ X, there exists an open set O such that x ∈ O, and a
homeomorphism O → Rn .

2.2 Exercises
Exercise 8. Show that the topological spaces Rn and B(0, 1) ⊂ Rn are homeomorphic.
x
Proof. Let f : B(0, 1) → Rn be defined as f (x) = . I observe it’s well defined because
1 − ||x||
||x|| < 1. We shall prove f is a homeomorphism.

1. Injective: Take x, y ∈ B(0, 1) and suppose that

x y
= .
1 − ||x|| 1 − ||y||

Applying the norm in both sides, we obtain the equation

||x||(1 − ||y|||) = ||y||(1 − ||x||) =⇒ ||x|| = ||y||.

On the other side x and y points to the same direction, given that

1 − ||y||
y= x = αx,
1 − ||x||

with α = 1 because of the same norm. We conclude x = y.

6
 2. Surjective: Take y ∈ Rn . We shall prove that there exists x ∈ B(0, 1) such that f (x) = y,
that is,
x
=y
1 − ||x||
||y||
Applying the norm we observe that if that is true, ||x|| = ||y|| − ||y||||x|| =⇒ ||x|| = 1+||y|| .
y
And x = (1 − ||x||)y = 1
1+||y|| y. We conclude that for every y ∈ Rn , if we take x = 1+||y|| ,

y/(1 + ||y||)
f (x) = =y
1 − ||y||/(1 + ||y||)

3. Continuity of f: Consider an open set A ⊂ Rn . Let B = f −1 (A). We shall prove B is

open, that is, for every x ∈ B, exists r > 0 such that B(x, r) ⊂ B. Take x = f −1 (y) ∈ B.
Because A is open, there is  > 0 such that B(y, ) ⊂ A. Take δ such that

δ
(1 + ||y||) < 
1 − ||x|| − δ

and z = f −1 (w) ∈ B(x, δ).

x z 1 1 − ||x||
||y − w|| = − = x− z
1 − ||x|| 1 − ||z|| 1 − ||x|| 1 − ||z||
1 1 − ||x||
= x−z+z− z
1 − ||x|| 1 − ||z||
 
||x − z|| 1 1 − ||x||
≤ + 1− ||z||
1 − ||x|| 1 − ||x|| 1 − ||z||
||x − z|| ||z|| ||x|| − ||z||
= +
1 − ||x|| 1 − ||x|| 1 − ||z||
1
≤ ||x − z||(1 + ||w||)
1 − ||x||
1
≤ ||x − z||(1 + ||y − w|| + ||y||)
1 − ||x||
||x − z||
=⇒ ||y − w|| ≤ (1 + ||y||)
1 − ||x|| − ||x − z||
δ
< (1 + ||y||) < 
1 − ||x|| − δ

So w ∈ B(y, ) ⊂ A =⇒ z ∈ B, what proves B is open. It concludes the continuity of f .

4. Continuity of f −1 : The inverse is given by

y
f −1 (y) =
1 + ||y||

The demonstration is quite similar to the previous item, given that the only difference is
the signal.

By items (1) - (4), we conclude f is a homeomorphism and B(0, 1) ' Rn .

Exercise 9. Show that B(x, r) and B(y, s) are homeomorphic.

7
Proof. Consider the function f : B(0, 1) → B(c, r) given by f (x) = r · x + c. Let’s prove f is a
homeomorphism.

1. Injective: If x, y ∈ B(0, 1) and rx + c = ry + c =⇒ x = y, because r > 0 by definition.

So f is injective.

2. Surjective: Let y ∈ B(c, r) and x = (y − c)/r. So ||x|| = ||y − c||/r < 1, by definition. So
x ∈ B(0, 1) and f (x) = y what proves this function is surjective.

3. Continuity of f: Let A ⊂ B(c, r) open set and denote B = f −1 (A). Take x = f −1 (y) ∈ B.
We know there exists  > 0 such that B(y, ) ⊂ A. Define δ = /r and take z = f −1 (w) ∈
B(x, δ).
||y − w|| = ||rx + c − (rz + c)|| = r||x − z|| < rδ = 

Therefore w ∈ B(y, ) ⊂ A =⇒ z ∈ B. So B(x, δ) ⊂ B, what proves B is open. This

concludes the continuity of f .

4. Continuity of f −1 : The inverse is given by

y−c
f −1 (y) =
r

This function is continuos for the same argument as before.

By items (1) - (4), we conclude f is a homeomorphism and B(0, 1) ' B(c, r). Since this is an
equivalence relation, we have that

B(0, 1) ' B(x, r) and B(0, 1) ' B(y, s) implies B(x, r) ' B(y, s).

Exercise 10. Show that S(0, 1), the unit circle of R2 , is homeomorphic to the ellipse
  x 2  y 2 
2
S(a, b) = (x, y) ∈ R , + =1 ,
a b

for any a, b > 0.

Proof. Consider the function f : S(0, 1) → S(a, b) defined as f (x, y) = (ax, by). Let’s prove it is
a homeomorphism.

1. Injective: Let (x1 , y1 ), (x2 , y2 ) ∈ S(0, 1) such that (ax1 , by1 ) = (ax2 , by2 ). Since a, b > 0,
we have x1 = x2 and y1 = y2 . It proves f is injective.
z w
2. Surjective: Let (z, w) ∈ S(a, b) and (x, y) = , . It’s clear that f (x, y) = (z, w) and
2 2
a b
x2 + y 2 = az 2 + wb2 = 1, so (x, y) ∈ S(0, 1). It proves f is surjective.

3. Continuity of f: Let A ⊂ S(a, b) open set and denote B = f −1 (A). Take (x, y) =
f −1 (z, w) ∈ B. We know there exists  > 0 such that B((z, w), ) ⊂ A. Put δ as defined

8
 below and take (x0 , y 0 ) = f −1 ((z 0 , w0 )) ∈ B((x, y), δ). Consider the norm 1

||(z 0 , w0 ) − (z, w)||1 = ||(ax0 , by 0 ) − (ax, by)||1 = || a(x0 − x), b(y 0 − y) ||1

= a|x0 − x| + b|y 0 − y|, define c = max{a, b}

≤ c(|x0 − x| + |y 0 − y|) = c||(x0 − x, y 0 − y)||1

By the equivalente of the norms, there exists constants k1 , k2 such that

||(z 0 , w0 ) − (z, w)|| ≤ k1 ||(z 0 , w0 ) − (z, w)||1 ≤ ck1 ||(x0 − x, y 0 − y)||1 ≤ ck1 k2 ||(x0 − x, y 0 − y)||

Then we need δ = 
ck1 k2 in order to prove that (z 0 , w0 ) ∈ B((z, w), ) ⊂ A =⇒ (x0 , y 0 ) ∈ B.
So B((x, y), δ) ⊂ B, what proves B is open. This concludes the continuity of f .

4. Continuity of f −1 : The inverse is given by

f −1 ((z, w)) = (z/a, w/b)

This function is continuos for the same argument as before.

By items (1) - (4), we conclude f is a homeomorphism and S(0, 1) ' S(a, b).

Exercise 11. Show that [0, 1) and (0, 1) are not homeomorphic.

Proof. We shall prove by contradiction. Suppose these exists a homeomorphism f : [0, 1) →

(0, 1). Let 0 < z = f (0) < 1 and define the following function

g : (0, 1) → (0, z) ∪ (z, 1)

x 7→ g(x) = f (x)

This function is well defined given that z is not image of other point but 0. The function is
injective because if g(y) = g(x) =⇒ f (y) = f (x) =⇒ x = y, given that f is injective. This
function is also surjective since f is and 0 < w < 1 and w 6= z, it’s clear that f (0) 6= w. As g is
an induced map of a continuos function, by Proposition 1.21 from the notes, it’s continuos and
so is its inverse. We conclude g is a homeomorphism.
Now I will prove that (0, 1) admits only 1 connected component, that is, it’s connected.
Suppose it’s not and there exists O, O0 ⊂ (0, 1) open disjoint sets such that (0, 1) = O ∪ O0
and none of them are empty sets. Let a ∈ O, b ∈ O0 with a < b without loss of generality.
Define α = sup{x ∈ R : [a, x) ⊂ O}. It’s well defined because this set is not empty, given O
is open and b is an upper bound. Then α ≤ b. Suppose α ∈ O0 , then there exists r > 0 such
that (α − r, α + r) ⊂ O0 . We know that for every  > 0, there exists w ∈ (α − , α] such that
[a, w) ⊂ O. That is a contradiction since there exists w ∈ (α − r, α) such that [a, w) ⊂ O. So
α ∈ O =⇒ (α − r, α + r) ⊂ O, for some r. We infer that [a, α + r) ⊂ O, what is an absurd.
Therefore (0, 1) is connected.
For a similar argument, we prove that (0, z) and (z, 1) are connected. This implies that the
union admits 2 connected components.

9
 In that sense, we have a homeomorphism between a topological space with 1 connected
component and other with 2 connected components, what is a contradiction by Proposition 2.14
from the notes. We conclude that [0, 1) and (0, 1) are not homeomorphic.

10
3 Homotopies
3.1 Important definitions
Definition 3.1.1. Let (X, T ) and (Y, U) be two topological spaces, and f, g : X → Y two
continuous maps. A homotopy between f and g is a map F : X × [0, 1] → Y such that:

1. F (·, 0) is equal to f ,

2. F (·, 1) is equal to g,

3. F : X × [0, 1] → Y is continuous.

If such a homotopy exists, we say that the maps f and g are homotopic.
Remark. Before asking for F : X × [0, 1] → Y to be continuous, we have to give X × [0, 1]
a topology. The topology we choose is the product topology. Consider the topological space
(X, T ), and endow [0, 1] with the subspace topology of R, denoted T|[0,1] . The product topology
on X × [0, 1], denoted T ⊗ T|[0,1] , is defined as follows: a set O ⊂ X × [0, 1] is open if and only
if it can be written as a union Uα∈A Oα × Oα0 where every Oα is an open set of X and Oα0 is an
open set of [0, 1].
Definition 3.1.2. Let (X, T ) and (Y, U) be two topological spaces. A homotopy equivalence
between X and Y is a pair of continuous maps f : X → Y and g : Y → X such that:

1. g ◦ f : X → X is homotopic to the identity map id : X → X,

2. f ◦ g : Y → Y is homotopic to the identity map id : Y → Y ,

If such a homotopy equivalence exists, we say that X and Y are homotopy equivalent.
Definition 3.1.3. Let (X, T ) be a topological space and Y ⊂ X a subset, endowed with the
subspace topology T|Y . A retraction is a continuous map r : X → Y such that ∀y ∈ Y, r(y) = y.
A deformation retraction is a homotopy F : X × [0, 1] → Y between the identity map id :
X → X and a retraction r : X → Y .

3.2 Exercises
Exercise 12. Let f : Rn → X be a continuous map. Then f is homotopic to a constant map.

Proof. I must prove that there exists a homotopy between f and a constant map. Consider the
function F : Rn × [0, 1] → X defined as

F (x, t) = f (tx)

It’s clear that F (x, 0) = f (0), for every x ∈ Rn . So it’s the constant map f (0). We also have
that F (x, 1) = f (x), ∀x ∈ Rn . Moreover, let’s prove F is continuos. Denote F 0 : Rn × R → X
the function F 0 (x, t) = f (xt) and g : Rn × R → Rn the function g(x, t) = xt. So F 0 = f ◦ g.
Let’s prove g is a continuous function. As we are dealing with a real-valued function, by
Proposition 1.19 from the notes, I can use the  − δ proof. Let (x, t) ∈ Rn+1 and  > 0. In the

11
proof I use the norm 1, without loss of generality because of the equivalence of norms in Rn . Put

δ = min{1, max{||x||,|t|+1} } and suppose ||(x, t) − (x0 , t0 )|| = ||x − x0 || + |t − t0 | < δ. So,

||xt − x0 t0 || = ||xt − xt0 + xt0 − x0 t0 ||

≤ |t − t0 |||x|| + |t0 |||x − x0 ||
≤ |t − t0 |||x|| + (|t| + δ)||x − x0 ||
< max{||x||, |t| + δ}δ
≤ max{||x||, |t| + 1}δ ≤ 

By this, g is a continuos function. Since f is also continuos, the composition F 0 is also

continuos, by Proposition 1.18. By Proposition 1.21, when we endow F 0 in Rn × [0, 1], we obtain
a continuos function, that is F is continuos. Then we conclude that f is homotopic to a constant
function.

Exercise 13. Let f : S1 → S2 be a continuous map which is not surjective. Prove that it is
homotopic to a constant map where the unit sphere Sn−1 = {x ∈ Rn , ||x|| = 1}.

Proof. Let x0 ∈ S2 such that x0 6∈ f (S1 ) and consider the constant map g(x) = −x0 , for every
x ∈ S1 . Let F : S1 × [0, 1] → S2 be defined as

(1 − t)f (x) − tx0

F (x, t) =
||(1 − t)f (x) − tx0 ||

The first thing we must prove it’s well defined. Suppose that (1 − t)f (x) − tx0 = 0. If t = 1,
then x0 = 0, an absurd given that ||x0 || = 1. If t < 1, f (x) = t
1−t x0 and applying the norm on
both sides 1 = ||f (x)|| = t
1−t ||x0 || = t
1−t =⇒ t = 1/2. If that is the case, f (x) − x0 = 0 =⇒
f (x) = x0 , contradiction. Moreover, for all x and t, ||F (x, t)|| = 1 =⇒ F (S1 , [0, 1]) ⊂ S2 .
Now let’s prove it’s a homotopy:

f (x)
1. F (x, 0) = ||f (x)|| = f (x), ∀x ∈ S1 .
−x0
2. F (x, 1) = ||x0 || = −x0 , ∀x ∈ S1 .

3. Consider the extension of the function F 0 : S1 × [0, 1] → R3 . This function is continuous

because it’s a combination os continuos function. So F is continuos because it’s a restriction
of F 0 . I needed to extend the function because (1 − t)f (x) is not necessary in the sphere,
so I couldn’t prove it’s continuos. However, when extended we see each part is continuos.

By (1) - (3), we have proved F is a homotopy and f are homotopic to a constant function.
Remark. If the function is not surjective, it’s harder to prove, and I couldn’t yet. For instance,
this is a reference1 (but the answers use specialized tools)

1
[Link]

12
Exercise 14. Show that being homotopic is a transitive relation between maps: for every triplet
of maps f, g, h : X → Y , if f , g are homotopic and g, h are homotopic, then f , h are homotopic.

Proof. We shall prove there exist a homotopy H between f and h. By assumption, there exists
a homotopy F between f and g and a homotopy G between g and h. Define H : X × [0, 1] → Y
such that 
F (x, 2t), 0 ≤ t ≤ 1/2
H(x, t) =
G(x, 2t − 1), 1/2 < t ≤ 1

that is, H behaves as F until it reaches a half. When that occurs, H(x, 1/2) = F (x, 1) =
g(x) = G(x, 0). After that, H follows G until the end of the interval. So, it’s clear that
H(x, 0) = F (x, 0) = f (x), ∀x ∈ X and H(x, 1) = G(x, 1) = h(x), ∀x ∈ X. Moreover, let’s prove
H is continuos. Let A ⊂ Y closed set. So

H −1 (A) = {(x, t) : F (x, 2t) ∈ A, t ≤ 1/2} ∪ {(x, t) : G(x, 2t − 1) ∈ A, t ≥ 1/2}

= F̃ −1 (A) ∪ G̃−1 (A),

where F̃ (x, t) = F (x, 2t) and G̃(x, t) = G(x, 2t − 1), with domain being, respectively, X × [0, 1/2]
and X × [1/2, 1]. As we see in the following remark, both functions are continuos, so F̃ −1 (A) ∪
G̃−1 (A) is closed, what proves H is continuos and, therefore, f and h are homotopic.
Remark. The map (x, t) 7→ (x, 2t) is continuos. In order to see that, take A ⊂ X × [0, 1] open.
So it can be written as a Oa × Ia , where Ia ⊂ [0, 1] is an open interval and Oa ⊂ X is open.
S

The pre-image of A is given by a Oa × 12 Ia , that is still open. With that and using the fact
S

that combination of continuos functions is continuos, F̃ is continuos. For a similar argument, G̃

is continuos.

Exercise 15. Show that being homotopy equivalent is an equivalence relation (reflexive, sym-
metric and transitive).

Proof. 1. (reflexive): Consider the identity map id : X → X, that is continuos. We shall

prove that this function is homotopic to itself. Consider F : X × [0, 1] → X given by
F (x, t) = x for every x and t. It’s clear this is a homotopy because F (x, 0) = F (x, 1) = x
and it’s continuos. Moreover id ◦ id = id by definition of identity. Therefore, there exists
a homotopy equivalence between id and itself. We conclude X ≈ X.

2. (symmetric): Suppose X ≈ Y . So, there exists continuos functions f : X → Y and

g : Y → X that form a homotopy equivalence. This means that g : Y → X and f : X → Y
are a homotopy equivalence as well. So Y ≈ X.

3. (transitive): Suppose X ≈ Y , and let f1 : X → Y and g1 : Y → X form a homotopy

equivalence. Also suppose Y ≈ Z and let f2 : Y → Z and g2 : Z → Y form a homotopy
equivalence. Define f3 = f2 ◦f1 and g3 = g1 ◦g2 . Let’s proof this is a homotopy equivalence.
Both functions are continuos given that they are a composition of continuos functions.

(a) g3 ◦ f3 = g1 ◦ g2 ◦ f2 ◦ f1 is homotopic to id : X → X.

13
 Let F1 be a homotopy between g1 ◦ f1 and id and F2 a homotopy between g2 ◦ f2 and
id. Define 
g ◦ F (·, 2t) ◦ f (x), 0 ≤ t ≤ 1/2
1 2 1
F3 (x, t) =
F (x, 2t − 1), 1/2 < t ≤ 1
1

So F3 (x, 0) = g1 (F2 (f1 (x), 0)) = g1 (g2 (f2 (f1 (x)))) = g3 ◦ f3 (x), for every x and
F3 (x, 1) = F1 (x, 1) = x, for every x. When t = 1/2,

F3 (x, 1/2) = g1 (F2 (f1 (x), 1)) = g1 (f1 (x)) = F1 (x, 0)

F3 is continuos by a similar proof written in the last exercise. This implies that g3 ◦ f3
is homotopic to the identity.
(b) f3 ◦ g3 = f1 ◦ f2 ◦ g2 ◦ g1 is homotopic to id : Z → Z.
This follows a quite similar demonstration and can be omitted.

By the points above f3 and g3 is a homotopy equivalence what proves X ≈ Z. Consequently,

homotopy equivalence is an equivalence relation.

Exercise 16. Classify the letters of the alphabet into homotopy equivalence classes.

Proof. I will consider the upper case alphabet and each letter will be considered as a topological
space (a subset from R2 ), for example the letter O is homotopy equivalent to a circle, while L is
to an interval, or equivalently, a point. Observe that most of the letters are equivalent to a point,
because we can think in a continuos reduction. When we have a hole, such as A, D, R, O, P, Q,
this continuity is impossible since we’ll have a point break. B is a special case because we can’t
deform into a point without breaking points and also we cannot join the holes in one. So there
is three classes, given by its representatives

1. O

2. B

3. I

A B C D E F G H I J K L M
1 2 3 1 3 3 3 3 3 3 3 3 3

N O P Q R S T U V W X Y Z
3 1 1 1 1 3 3 3 3 3 3 3 3

14
4 Simplicial complexes
4.1 Important definitions
Definition 4.1.1. The standard simplex of dimension n is the following subset of Rn+1 ,

n+1
X
∆n = {x = (x1 , ..., xn+1 ) ∈ Rn+1 |∀i, xi ≥ 0 and x1 = 1}.
i=1

For any collection of points a1 , ..., ak ∈ Rn , we define their convex hull as:
 
 X X 
conv({a1 , ..., ak }) = ti ai | ti = 1, t1 , ..., tk ≥ 0
 
1≤i≤k 1≤i≤k

Definition 4.1.2. Let V be a set (called the set of vertices). A simplicial complex over V is
a set K of subsets of V (called the simplices) such that, for every σ ∈ K and every non-empty
τ ⊂ σ, we have τ ∈ K. If σ ∈ K is a simplex, its non-empty subsets τ ⊂ σ are called faces of σ,
and σ is called a coface of τ . Moreover, its dimension is |σ| − 1 and the dimension of a simplicial
is the maximum dimension of its simplices.
Definition 4.1.3. Let K be a simplicial complex, with vertex V = [[1, n]]. In Rn , consider, for
every i ∈ [[1, n]], the vector ei = (0, ..., 1, 0, ..., 0) (ith coordinate 1, the other ones 0). Let |K| be
the subset of Rn defined as:
[
|K| = conv({ej , j ∈ σ}).
σ∈K

Endowed with the subspace topology, (|K|, T||K| ) is a topological space, that we call the topological
realization of K.
Definition 4.1.4. Let (X, T ) be a topological space. A triangulation of X is a simplicial complex
K such that its topological realization (|K|, T||K| ) is homeomorphic to (X, T ).
Definition 4.1.5. Let K be a simplicial complex of dimension n. Its Euler characteristic is the
integer
X
χ(K) = (−1)i · (number of simplices of dimension i).
0≤i≤n

Definition 4.1.6. The Euler characteristic of a topological space is the Euler characteristic of
any triangulation of it.

4.2 Exercises
Exercise 17. Give a triangulation of the cylinder.

Proof. We can think a triangulation of the cylinder in that following form: each circular section
is mapped into a triangle graph. On the other hand, the line can be mapped to an edge. Since
a cylinder can be written as S1 × R, the triangulation as well.
Let’s write down:

K = {[0, 1, 3], [0, 2, 3], [2, 3, 5], [2, 4, 5], [4.5, 1], [4, 1, 0]}

15
 0 1

2 3

4 5

0 1

Exercise 18. What are the Euler characteristics of Examples 4.5 and 4.6? What is the Euler
characteristic of the icosahedron?

Proof. Exemplo 4.5:

K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0], [0, 2], [1, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]}.

χ(K) = 4 − 6 + 4 = 2

Exemplo 4.6:

K = {[0], [1], [2], [3], [0, 1], [1, 2], [1, 3], [0, 2], [2, 3], [3, 0],
[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]}.

χ(K) = 4 − 6 + 4 − 1 = 1

D20: It has 20 faces (dimension 2), 30 edges (dimension 1) and 12 vertices (dimension 0),
its Euler characteristic is 12 − 30 + 20 = 2 (Euler relation).

Exercise 19. Let K be a simplicial complex (with vertex set V ). A sub-complex of K is a set
M ⊂ K that is a simplicial complex. Suppose that there exists two sub-complexes M and N of
K such that K = M ∪ N . Show the inclusion-exclusion principle:

χ(K) = χ(M ) + χ(N ) − χ(M ∩ N )

Proof. Denote ki the number of simplices of dimension i, that is, χ(K) = 0≤i≤k (−1) ki , with
i
P

k being its dimension. Each simplex of dimension i belongs to M , to N or both. Denote kiM , kiN
and kiM N the number od simplices of dimension i in M , N and M ∩ N respectively. So

ki = kiM + kiN − kiM N .

16
Therefore,
X X X X
χ(K) = (−1)i (kiM + kiN − kiM N ) = (−1)i kiM + (−1)i kiN − (−1)i kiM N
0≤i≤k 0≤i≤k 0≤i≤k 0≤i≤k

Let m and n be the dimension of M and N , respectively. Now I shall prove M ∩ N is a simplicial
complex. Take σ ⊂ M ∩ N and τ ⊂ σ, then τ ⊂ σ ∈ M and τ ⊂ σ ∈ N , what implies τ ∈ M ∩ N .
It proves its a simplicial complex with dimension p. We know the dimension of M is m, so it
implies that for all i > m, kiM = 0. Suppose not and let kjM > 0 for some j > m, we would
have a simplex with dimension greater or equal than m. This is a contradiction, because the the
dimension of M is the maximum dimension of its simplices. This holds for N and M ∩ N .
X X X X
χ(K) = (−1)i (kiM + kiN − kiM N ) = (−1)i kiM + (−1)i kiN − (−1)i kiM N
0≤i≤k 0≤i≤k 0≤i≤k 0≤i≤k

We conclude that
X X X
χ(K) = (−1)i kiM + (−1)i kiN − (−1)i kiM N = χ(M ) + χ(N ) − χ(M ∩ N )
0≤i≤m 0≤i≤n 0≤i≤p

Exercise 20. What is the Euler characteristic of a sphere of dimension 1? 2? 3?

Proof. We may find the Euler characteristic of one triangulation of the sphere. So we first need
to find a triangulation for the sphere Sn ⊂ Rn+1 . We can think in the simplex in this space. In
R2 it’s the triangle, in R3 it’s the tetrahedron, in R4 it’s the 5-cell and so on. The simplex in
Rn+1 has n + 2 vertices and each vertex connect to all the other. We have also n + 2 simplices of
dimension n, because each has n + 1 points, that is, n+2
n+1 = n + 2. For each of them, we must

include all its subsets.

Now we can calculate the Euler characteristic for each triangulation and therefore each sphere.

χ(S1 ) = −3 + 3 = 0

χ(S2 ) = 4 − 6 + 4 = 2

χ(S3 ) = −5 + 10 − 10 + 5 = 0

χ(S4 ) = 6 − 15 + 20 − 15 + 6 = 2

Exercise 21. Using the previous exercise, show that R3 − {0} and R4 − {0} are not homotopy
equivalent.

Proof. Suppose that R3 − {0} and R4 − {0} are homotopy equivalent. By Example 3.15, Sn−1 is
homotopic equivalent to Rn − {0}. By this and using the transitive property we conclude that
S2 and S3 are homotopic equivalent. If that is true, we infer that they have the same Euler

17
characteristic, what is a contraction by the last exercise. Hence R3 − {0} and R4 − {0} are not
homotopy equivalent.

The computational exercises (22 - 26) can be found in the Github2

Exercise 22. Build triangulations of the letters of the alphabet, and compute their Euler char-
acteristic.
Exercise 23. For every n, triangulate the bouquet of n circles (see below). Compute their Euler
characteristic.
Exercise 24. Implement the following triangulation of the torus.
Exercise 25. Consider the following dataset of 30 points x0 , ..., x29 in R2 .
Write a function that takes as an input a parameter r ≥ 0, and returns the simplicial complex
G(r) defined as follows:

1. the vertices of G(r) are the points x0 , ..., x29 ,

2. for all i, j ∈ [[0, 29]] with i 6= j, the edge [i, j] belongs to G(r) if and only if ||xi − xj || ≤ r.

Compute the number of connected components of G(r) for several values of r. What do you
observe?
Exercise 26. A Erdos–Renyi random graph G(n, p) is a simplicial complex obtained as follows:

1. add n vertices 1, ..., n,

2. for every a, b ∈ [[1, n]], add the edge [a, b] to the complex with probability p.

Builds a function that, given n and p, outputs a simplicial complex G(n, p). Observe the
influence of p on the number of connected components of G(10, p) and G(100, p).

2
[Link]/lucasmoschen/topological-data-analysis/blob/main/tutorials/[Link]

18
5 Homological algebra
5.1 Important Definitions
Definition 5.1.1. Let K be a simplicial complex. For any n ≥ 0, define the sets

Kn = {σ ∈ K, dim(σ) ≤ n}

K(n) = {σ ∈ K, dim(σ) = n}.

The first set is a simplicial complex, called the n-skeleton of K.

Definition 5.1.2. Let n ≥ 0. The n-chains of K is the set Cn (K) whose elements are the
formal sums
X
σ · σ where ∀σ ∈ K(n) , σ ∈ Z/2Z.
σ∈K(n)

We can give Cn (K) a group structure via

X X X
σ · σ + ησ · σ = (σ + ησ ) · σ.
σ∈K(n) σ∈K(n) σ∈K(n)

Definition 5.1.3. Let n ≥ 1, and σ ∈ K(n) a simplex of dimension n. We define its boundary
as the following element of Cn−1 (K):
X
∂n σ = τ
τ ⊂σ,|τ |=|σ|−1

and
X X
∂n σ · σ = σ · ∂n σ
σ∈K(n) σ∈K(n)

Definition 5.1.4. We define

1. The n-cycles: Zn (K) = Ker(∂n ),

2. The n-boundaries: Bn (K) = Im(∂n+1 ).

We say that two chains c, c0 ∈ Cn (K) are homologous if there exists b ∈ Bn (K) such that c = c0 +b.
Definition 5.1.5. The nth homology group of K is Hn (K) = Zn (K)/Bn (K).
Definition 5.1.6. Let K be a simplicial complex and n ≥ 0. Its nth Betti number is the integer
βn (K) = dim Hn (K).
Definition 5.1.7. The homology groups of a topological space are the homology groups of any
triangulation of it. We define their Betti numbers similarly.

5.2 Exercises
Exercise 27. Let V be a Z/2Z-vector space, and W a linear subspace. Prove that

dim V /W = dim V − dim W.

19
Proof. Suppose V is finite-dimensional, such that dim V = n + m and dim W = m. As we have
a finite basis and a finite field, we only have finite number of combinations from the vector of
this basis. In special V is finite. By Proposition 5.2, V has cardinal 2m+n and W has cardinal
2m . Let’s prove that V /W has cardinal 2n . We know the quotient space has finite dimension
k, because it’s finite. So it has 2k elements. Let V /W = {[v1 ], ..., [v2k ]} where vi represents an
equivalence class. We know for each v ∈ V there exists i such that v ∈ vi + W and there is
w ∈ W with x = vi + w. As each class is disjoint, we first choose one of the 2k classes vi . After
we pick out one element of this class. We have 2m elements in W . Let’s see |vi + W | = 2m . Take
w, w0 ∈ W and suppose vi + w = vi + w0 . Summing vi in both sides we obtaing that w = w0 . So
we have 2k 2m ways of forming elements os V . We conclude k must be n, what finishes our proof.
Remark. Consider the following proof slightly more general.
Suppose V is finite-dimensional and let {w1 , ..., wm } be a basis of W . So we can extend
this to a basis on V , namely, {w1 , ..., wm , v1 , ..., vn }, where, dim V = m + n. Consider the set
{v1 + W, ..., vn + W }. First, let’s prove it’s free.
 
n
X n
X
0+W = λj (vj + W ) =  λj vj  + W,
j=1 j=1

P 
n
So j=1 λj vj ∈ W . But it implies it can be written as a linear combination of {w1 , ..., wm },
what contradicts the fact that {w1 , ..., wm , v1 , ..., vn } is linear independent.
Now take v + W ∈ V /W , where v = m
Pn
j=1 λj+m vj . So
P
j=1 λj wj +

 
Xm n
X
v+W = λ j wj + λj+m vj  + W
j=1 j=1
m
X n
X
= λj (wj + W ) + λj+m (vj + W )
j=1 j=1
n
X
= λj+m (vj + W )
j=1

We conclude {v1 , ..., vn } is a basis what implies dim V /W = n = m + n − m.

Exercise 28. Let (G, +) be a group, potentially non-commutative. Prove that

∀g ∈ G, g + g = 0 =⇒ G is commutative.

Proof. Let u, v ∈ G. So u + v + v = u + (v + v) = u + 0 = u. With that in mind, we see that

u + v + v + u = 0 =⇒ (u + v) + (v + u) = 0

We know v + u and u + v are elements of G. So we can add to each side and obtain

(u + v) + (v + u) + (v + u) = (v + u) =⇒ u + v = v + u

20
As u and v are arbitrary, G is commutative.

Exercise 29. Compute the Betti numbers β0 (K), β1 (K) and β2 (K) of the following simplicial
complex:
K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0]}.

Proof. Z0 (K) = C0 (K)

B0 (K) = {[0] + [1], [1] + [2], [2] + [3], [3] + [0], [0] + [2], [1] + [3], [0] + [1] + [2] + [3], 0}
As B0 have 23 elements and Z0 has 24 , we deduce that

β0 (K) = dim Z0 (K) − dim B0 (K) = 4 − 3 = 1

Z1 (K) = {[0, 1] + [1, 2] + [2, 3] + [3, 0], 0}

B1 (K) = {0}
Nesse caso, observamos que, utilizando a mesma ideia do ponto anterior

β1 (K) = 1 − 0 = 1.

K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0]}.

Z2 (K) = {0}
B2 (K) = {0}
Portanto β2 (K) = 0.

Exercise 30. Compute the Betti numbers β0 (K), β1 (K) and β2 (K) of the following simplicial
complex:

K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0], [0, 2], [1, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]}.

Proof. Z0 (K) = C0 (K)

B0 (K) = {[0] + [1], [1] + [2], [2] + [3], [3] + [0], [0] + [2], [1] + [3], [0] + [1] + [2] + [3], 0}
As B0 have 23 elements and Z0 has 24 , we deduce that

β0 (K) = dim Z0 (K) − dim B0 (K) = 4 − 3 = 1

Z1 (K) = {[0, 1] + [1, 2] + [0, 2]; [0, 1] + [0, 3] + [1, 3]; [0, 2] + [2, 3] + [0, 3];
[1, 2] + [2, 3] + [1, 3]; [0, 1] + [1, 2] + [2, 3] + [0, 3]; [0, 1] + [1, 3] + [2, 3] + [2, 0];
[0, 2] + [1, 2] + [1, 3] + [0, 3]; 0} (1)

21
B1 (K) = {[0, 1] + [1, 2] + [0, 2]; [0, 1] + [0, 3] + [1, 3]; [0, 2] + [2, 3] + [0, 3];
[1, 2] + [2, 3] + [1, 3]; [0, 1] + [1, 2] + [2, 3] + [0, 3]; [0, 1] + [1, 3] + [2, 3] + [0, 2];
[0, 2] + [1, 2] + [1, 3] + [0, 3]; 0} (2)

Observe que os conjuntos são iguais e, portanto,

β1 (K) = 0.

Z2 (K) = {[0, 1, 2] + [0, 1, 3] + [0, 2, 3] + [1, 2, 3], 0}

B2 (K) = {0}
Portanto β2 (K) = 1.

22
6 Incremental algorithm
6.1 Important definitions
Definition 6.1.1. Let i ∈ [[1, n]], and d = dim(σi ). The simplex σi is positive if there exists a
cycle c ∈ Zd (K i ) that contains σi . Otherwise, σi is negative.
Definition 6.1.2. Defines for a set V = {0, 1, ..., n} a simplicial complex

∆n = {S ⊂ C, S 6= ∅}

and call it simplicial standard n-simplex with boundary

∂∆n = ∆n /V

Definition 6.1.3. Define the boundary matrix of K, denoted ∆ as follows: ∆ is a n × n matrix,

whose 
1, if σi ⊂ σj and |σ i | = |σ j | − 1
∆i,j =
0, else

6.2 Exercise
Exercise 31. Compute again the Betti numbers of the simplicial complexes of Exercises 29 and
30, using the incremental algorithm.

Proof. 1. K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0]}.
First we determine the ordering to be as placed in the set. It fulfills the required property.
After, we find the sign s for it σ i . The first four elements are positive, because, ∂0 has
C0 (K i ) as kernel. On the other hand [0, 1], [1, 2] and [2, 3] are negatives. At last [3, 0] is
positive, because [0, 1] + [1, 2] + [2, 3] + [3, 0] belongs to Z1 (K 8 ). Now we can follow the
algorithm thorough a table:

- σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8
Sign + + + + - - - +
β0 (K) 1 2 3 4 3 2 1 1
β1 (K) 0 0 0 0 0 0 0 1
β2 (K) 0 0 0 0 0 0 0 0

2. K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0], [0, 2], [1, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]}.
First we determine the ordering to be as placed in the set. It fulfills the required property.
After, we find the signs for it σ i . The vertices have positive sign. The following three
edges cannot form any cycle, so they are negative. The last three edges are part of a cycle
considering three other already placed of its dimension. When we achieve the simplices
with dimension 2, the first three must be negative, because when we sum every combination
of them, the boundary has image different from 0. The last, however will be positive. Now
we can follow the algorithm thorough a table:

23
 - σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 σ9 σ 10 σ 11 σ 12 σ 13 σ 14
Sign + + + + - - - + + + - - - +
β0 (K) 1 2 3 4 3 2 1 1 1 1 1 1 1 1
β1 (K) 0 0 0 0 0 0 0 1 2 3 2 1 0 0
β2 (K) 0 0 0 0 0 0 0 0 0 0 0 0 0 1

The result corroborates with those found previously.

Exercise 32. Prove that ∂∆n is a triangulation of the (n − 1)-sphere Sn−1 ⊂ Rn .

Proof. It’s clear that ∂∆n is a simplicial complex, because, for every simplex σ ∈ ∂∆n and
τ ⊂ σ, τ ∈ ∆n - since it’s a simplicial complex - and τ 6= V , then τ ∈ ∂∆n . I shall prove that the
topological realization of ∆n , denoted as Bn , is homeomorphic to the Sn−1 . We can describe it
n
X
Bn = {(α0 , ..., αn ) ∈ [0, 1] n+1
, αi = 1 and for some i, αi = 0}
i=0

Pn
Let H = {(x0 , ..., xn ) ∈ Rn+1 | i=0 xi = 1}. It’s clear that Bn ⊂ H. Define Cn := ∂B(b, r) ∩ H
such that Cn ⊂ interior ∆n . We’ll show it’s homeomorphic to Bn .
Let b = 1
n+1 (1, ..., 1) ∈ Rn+1 and take x ∈ Cn . Consider the half line which start in b and
crosses x. Its equation can be described as b + α(x − b). It intersects Bn when at least one of
its coordinates is zero and the other are between 0 and 1. The sum will be always 1 because we
are in H. Denote x(m) = min{xi : ith coordinate of x}. Let’s take α such that

1
b(m) + α(x(m) − b(m) ) = 0 =⇒ α =
1 − (n + 1)x(m)

For every other i 6= (m),

 
1 1
bi + α(xi − bi ) = 1+ (xi (n + 1) − 1)
n+1 1 − (n + 1)x(m)
 
1 1
= 1− (1 − xi (n + 1))
n+1 1 − (n + 1)x(m)
 
1 xi − xm
= (n + 1)
n+1 1 − (n + 1)x(m)
xi − xm
= ≥0
1 − (n + 1)x(m)
Pm
since x(m) < 1/(n + 1). Note that 1 = j=0 xj ≥ xi + nx(m) =⇒ 1 − (n + 1)x(m) ≥ xi − xm
and we conclude that bi + α(xi − bi ) ∈ [0, 1], that is, b − α(x − b) ∈ Bn . Denote this map f .
Let’s prove it’s a homeomorphism.

1. f is injective: suppose not. In this case, there is some point p ∈ Bn and two points
c1 , c2 ∈ Cn such that there are two segments starting at p and crossing Bn at p, however it
one passes thorough c1 and c2 respectively. So both segments have two points in common,
what implies they are equal. Suppose, no loss of generality, that c1 is between p and c2 .
Then 1 = ||c2 − b|| < ||c1 − b|| = 1, a contradiction and f is injective.

24
 2. f is surjective: Take y from Bn and make the half segment b to y. It’s clear it crosses Cn
because p is in its interior.

3. f is continuos: First we note that the map x 7→ x(m) is continuos. α can be seen as map
from Bn to [1, +∞). If we extend this map to a map α0 : Rn+1 → R, we see that α0 is
continuous by composing continuous functions and its restriction α will be continuos as
well. Using the composition property, we infer f is continuos.

4. f −1 is continuos: The inverse is quite similar. We consider y ∈ Bn and the half line
b + α(y − b). We map y to the value such ||b + α(y − b)||2 = r2 . We obtain, using the norm
2,
r2 (n + 1) − 1
α=
(n + 1)||y − b||
what is a continuous function of y.

Therefore Bn and Cn are homeomorphic by f . Now we must prove that Cn is homeomorphic

to Sn−1 , because if this is true, by transitivity, Bn ' Sn−1 .

Exercise 33. Show that the algorithm stops after a finite number of steps.

Proof. Consider the algorithm

Algorithm 1: Reduction of the boundary matrix
Input: a boundary matrix ∆
Output: a reduced matrix ∆˜
for j ← 1 to n do
while ∃i < j such that δ(i) = δ(j) do
add column i to column j
end
end

Remark. I’d add a condition in the algorithm for undefined δ(i), that is, we should consider the
values in the domain of δ.
I have to prove that for every 1 ≤ j ≤ n, the while block stops after a finite number of
steps. That is, in a finite number of steps ∀i < j, δ(i) 6= δ(j). Let’s prove by induction on j. If
j = 1, there is no i < 1 = j, then the algorithm goes to j = 2. Now suppose by finite number of
operations, ∀i < j, δ(i) 6= δ(j). Then the process goes to j + 1. Suppose it’s defined and there is
k = δ(i) = δ(j + 1). That means 1 = ∆k,i = ∆k,j+1 and ∆s,i = ∆s,j+1 = 0, s > k. When we add
columns i and j + 1, we will have ∆s,j+1 = 0 for all s ≥ k. Therefore δ(j + 1) < δ(i) or it’s not
defined (the latter implies the while block ends). As we can decrease one unit at most δ(j + 1)
times, we only have a finite number of steps, in this case, a finite number of additions. Since we
have only finite values for j, the algorithm ends in a finite number of steps.

Exercise 34. Apply Algorithm to solve Exercise 31.

25
Proof. So as to solve both exercises, the order will be as placed in the set for each case. After we
build the boundary matrix and apply the Algorithm from the last exercise to obtain the reduced
matrix and with it, define σ i as negative if δ(i) is defined and positive, otherwise.

1. K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0]}.
This is the boundary matrix

- σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8
σ1 0 0 0 0 1 0 0 1
σ2 0 0 0 0 1 1 0 0
σ3 0 0 0 0 0 1 1 0
σ4 0 0 0 0 0 0 1 1
σ5 0 0 0 0 0 0 0 0
σ6 0 0 0 0 0 0 0 0
σ7 0 0 0 0 0 0 0 0
σ8 0 0 0 0 0 0 0 0

When we apply the algorithm, we start in i = 5. However we do not enter the while block
until j = 8 when δ(7) = δ(8) = 4. So we sum this columns, after σ6 to σ8 and at last σ5 to
σ8 . So σ8 will be the 0-column, while the other remain unaltered. By this, we obtain the
signs in order to calculate the Betti numbers.

- σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8
Sign + + + + - - - +
β0 (K) 1 2 3 4 3 2 1 1
β1 (K) 0 0 0 0 0 0 0 1
β2 (K) 0 0 0 0 0 0 0 0

2. K = {[0], [1], [2], [3], [0, 1], [1, 2], [2, 3], [3, 0], [0, 2], [1, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]}.
The boundary matrix is larger than the previous one.

- σ1,2,3,4 σ5 σ6 σ7 σ8 σ9 σ10 σ11 σ12 σ13 σ14

σ1 0 1 0 0 1 1 0 0 0 0 0
σ2 0 1 1 0 0 0 1 0 0 0 0
σ3 0 0 1 1 0 1 0 0 0 0 0
σ4 0 0 0 1 1 0 1 0 0 0 0
σ5 0 0 0 0 0 0 0 1 1 0 0
σ6 0 0 0 0 0 0 0 1 0 0 1
σ7 0 0 0 0 0 0 0 0 0 1 1
σ8 0 0 0 0 0 0 0 0 1 1 0
σ9 0 0 0 0 0 0 0 1 0 1 0
σ10 0 0 0 0 0 0 0 0 1 0 1
σ11 0 0 0 0 0 0 0 0 0 0 0
σ12 0 0 0 0 0 0 0 0 0 0 0
σ13 0 0 0 0 0 0 0 0 0 0 0
σ14 0 0 0 0 0 0 0 0 0 0 0

26
This matrix has several more things to deal. First we make the column σ8 be a 0-column
again. After we make the same to σ9 , being replaced by σ5 +σ6 +σ9 and σ10 by σ6 +σ7 +σ10 .
We will have

- σ1,2,3,4 σ5 σ6 σ7 σ8 σ9 σ10 σ11 σ12 σ13 σ14

σ1 0 1 0 0 0 0 0 0 0 0 0
σ2 0 1 1 0 0 0 0 0 0 0 0
σ3 0 0 1 1 0 0 0 0 0 0 0
σ4 0 0 0 1 0 0 0 0 0 0 0
σ5 0 0 0 0 0 0 0 1 1 0 0
σ6 0 0 0 0 0 0 0 1 0 0 1
σ7 0 0 0 0 0 0 0 0 0 1 1
σ8 0 0 0 0 0 0 0 0 1 1 0
σ9 0 0 0 0 0 0 0 1 0 1 0
σ10 0 0 0 0 0 0 0 0 1 0 1
σ11 0 0 0 0 0 0 0 0 0 0 0
σ12 0 0 0 0 0 0 0 0 0 0 0
σ13 0 0 0 0 0 0 0 0 0 0 0
σ14 0 0 0 0 0 0 0 0 0 0 0

The next column to deal is σ13 . Summing it with σ11 will solve the problem. With σ14 we
need to replace with σ12 + σ13 σ14 , considering the new σ13 . But this will turn σ14 to be a
0-column. We know, then, the signs for each column.

- σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 σ9 σ 10 σ 11 σ 12 σ 13 σ 14
Sign + + + + - - - + + + - - - +
β0 (K) 1 2 3 4 3 2 1 1 1 1 1 1 1 1
β1 (K) 0 0 0 0 0 0 0 1 2 3 2 1 0 0
β2 (K) 0 0 0 0 0 0 0 0 0 0 0 0 0 1

27
7 Topological inference
7.1 Important definitions
Definition 7.1.1. For every t ≥ 0, the t-thickening of the set X, denoted X t , is the set of points
of the ambient space with distance at most t from X:

X t = {y ∈ Rn , ∃x ∈ X, ||x − y|| ≤ t}.

Equivalently, X t can be seen as a union of closed balls centered around every point of X.
Definition 7.1.2 (Hausdorff distance). Let X be any subset of Rn . The function distance
to X is the map

dist (·, X) : Rn → R
y 7→ dist (y, X) = inf{||y − x||, x ∈ X}

A projection of y ∈ Rn on X is a point x ∈ X which attains this infimum. If such a point x

exists and is unique, we denote it proj (y, X).
Then the Hausdorff distance cna be written as

dH (X, Y ) = max(sup dist (y, X), sup dist (x, Y ))

y∈Y x∈X

Definition 7.1.3. Let X be any subset of Rn . The medial axis of X is the subset med(X) ⊂ Rn
which consists of points y ∈ Rn that admit at least two projections on X:

med(X) = {y ∈ Rn , ∃x, x0 ∈ X, x 6= x0 , ||y − x|| = ||y − x0 || = dist(y, X)}.

Definition 7.1.4. Now, we define the reach of X as its proximity from its medial axis:

reach(X) = inf{dist(y, X), y ∈ med(X)} = inf{||x − y||, x ∈ X, y ∈ med(X)}

Equivalently
reach(X) = sup{t ≥ 0, X t ∩ med(X) = ∅}

Definition 7.1.5. Let X be a topological space, and U = {Ui }1≤i≤N a cover of X. The nerve
of U is the simplicial complex with vertex set {1, ..., N } and whose m-simplices are the subsets
{i1 , ..., im } ⊂ {1, ..., N } such that ∩m
k=0 Uik 6= ∅. It is denoted N (U ).

Definition 7.1.6. Let t ≥ 0 and consider the collection V t = {B̄(x, t), x ∈ X}. Its nerve is
denoted Cecht (X) and is called the Cech complex of X at time t.
Definition 7.1.7. Given a graph G, the corresponding clique complex is the simplicial complex
whose vertices are the vertices of G, and whose simplices are the sets of vertices of the cliques of
G. Some authors also call it the expansion of G .
Definition 7.1.8. The Rips complex of X at time t is the clique complex of the graph Gt defined
above. We denote it Ripst (X).

28
7.2 Exercises
Exercise 35. Prove that, when X is closed and bounded, a projection always exists. A set is
bounded if there exists R > 0 such that X ⊂ B(R, 0).

Proof. Let X a closed and bounded subset of Rn . So it’s compact by the Heine-Borel theorem.
The map y 7→ ||y − x|| is continuos because for y ∈ Rn and  > 0, if we take δ = , and
||y − w|| < δ,
 > ||y − w|| = ||(y − x) − (w − x)|| ≥ |||y − x|| − ||w − x|||

By the Weierstrass theorem, the function y 7→ ||y − x|| has a global minimum in X, that is,
there exist x∗ ∈ X such that ||y − x∗ || ≤ ||y − x||, ∀x ∈ X. So the infimum is well defined and a
projection always exist. However the uniqueness is not guaranteed.

Exercise 36. Let || · || + ∞ be the sup norm of function f : Rn → Rm : ||f ||∞ = supx∈Rn ||f (x)||.
Prove that dH (X, Y ) = ||dist(·, X) − dist(·, Y )||∞ .

Proof. We have that

||dist (·, X) − dist (·, Y )||∞ = sup |dist(x, X) − dist(x, Y )|

x∈Rn

≥ sup (dist(x, X) − dist(x, Y ))

x∈Rn

≥ supy∈Y dist(y, X)

given that Y ⊂ Rn and dist(y, Y ) = 0. Also

||dist (·, X) − dist (·, Y )||∞ = sup |dist(x, X) − dist(x, Y )|

x∈Rn

≥ sup (dist(x, Y ) − dist(x, X))

x∈Rn

≥ supx∈X dist(x, Y )

In special, ||dist (·, X) − dist (·, Y )||∞ ≥ dH (X, Y ).

The other inequality can be seen as follows. If dist(x, Y ) ≤ k, ∀x ∈ X, then for all w ∈ Rn
and x ∈ X,
dist(w, Y ) ≤ dist(w, x) + dist(x, Y ) ≤ dist(w, x) + k

and hence dist(w, Y ) ≤ dist(w, X) + k, taking the infimum. Likewise, if dist(y, X) ≤ k, ∀y ∈ Y

we obtain dist(w, X) ≤ dist(w, Y ) + k. Then |dist(w, X) − dist(w, Y )| ≤ k, for all w ∈ Rn . In
particular dH (X, Y ) ≥ dist(x, Y ), ∀x ∈ X and dH (X, Y ) ≥ dist(y, X), ∀y ∈ Y . By the fact we
have proved

dH (X, Y ) ≥ sup |dist(w, X) − dist(w, Y )| = ||dist(·, X) − dist(·, Y )||∞

w∈Rn

We conclude dH (X, Y ) = ||dist(·, X) − dist(·, Y )||∞ .

29
Exercise 37. Let X, Y be two closed and bounded subsets of Rn . Show that for every t ≥ 0, the
thickenings satisfy
dH (X t , Y t ) ≤ dH (X, Y ).

Give an example for which dH (X t , Y t ) < dH (X, Y ).

Proof. Let’s do it by steps, because dealing with infimum and supremum can be trick. Let t ≥ 0
and denote dist by d.

1. Let’s prove d(w, Y t ) ≤ d(w, Y ) − t, ∀w ∈ X t /Y t .

Take y ∈ Y and denote β = ||w − y|| > t. Take the point αw + (1 − α)y such that, for
some α ∈ [0, 1], t = ||αy + (1 − α)y − y|| = αβ, that is, α = t/β < 1. So we will have
||w − αw − (1 − α)y|| = (1 − α)β = β − t. It implies d(w, Y t ) ≤ d(w, Y ) − t. After we will
see the restriction over the domain of w is not restrictive.

2. supw∈X t d(w, Y ) ≤ supx∈X d(x, Y ) + t

If w ∈ X t , there exists x ∈ X such that ||w − x|| ≤ t. So d(w, Y ) ≤ d(x, Y ) + t ≤
supx∈X d(x, Y ) + t. It values for all w, then supw∈X t d(w, Y ) ≤ supx∈X d(x, Y ) + t.

3. supw∈X t d(w, Y t ) ≤ supx∈X d(x, Y ).

For every w ∈ X t /Y t , we have d(w, Y t ) ≤ supw∈X t d(w, Y ) − t, because of what we’ve
proved on point 1. Then

sup d(w, Y t ) ≤ sup d(w, Y ) − t ≤ sup d(x, Y ),

w∈X t /Y t w∈X t x∈X

as argued on point 2. Otherwise suppose w ∈ Y t ∩X t , then d(w, Y t ) = 0 and the inequality

supw∈X t ∩Y t d(w, Y t ) = 0 ≤ supx∈X d(x, Y ) is trivial, because d is a metric. Therefore

sup d(w, Y t ) = max{ sup d(w, Y t ), sup d(w, Y t )} ≤ sup d(x, Y )

w∈X t w∈X t ∩Y t w∈X t /Y t x∈X

4. We can show similarly that supz∈Y t d(z, X t ) ≤ supy∈Y d(y, X).

5. Therefore, the last two points imply dH (X t , Y t ) ≤ dH (X, Y ).

Example
Consider the following construction. Let C0 be the origen and Ci be the circumference of
center 0 and radius i−1 −j = 2 − 21−i . Each time the adicional value to the radius of the next
P
j=0 2
circle is decreasing by half. All the circles are contained in B(0, 2). We will define
∞
[ ∞
[
X= C2i and Y = C2i+1
i=0 i=0

30
 I claim that dH (X, Y ) = 1. For every x ∈ Ci , we have that d(x, Y ) = 2−i , because the closest
point in Y is in C i+1 . We can argue the same for d(y, X). Therefore dH (X, Y ) = supi 2−i = 1.
Consider now X t and Y t for some t > 0. We are creating rings with thickness 2t. Some rings
of different sets are being joined. Let’s calculate dH (X t , Y t ). In general, d(x, Y t ) will decreased,
be unaltered (when we pick some point in a border of Cit that maps to Ci+1
t or go to 0, when
two rings join. But it shall not increase. However if we take the origin, d(0, Y ) = 1 − t, but no
other can have a greater distance. Thus, dH (X t , Y t ) = 1 − t < 1 = dH (X, Y ).

Exercise 38. Show that the Hausdorff distance is equal to

inf {t ≥ 0, X ⊂ Y t and Y ⊂ X t }

Proof. Let t such that X ⊂ Y t and Y ⊂ X t . Take x ∈ X and consider d(x, Y ). By the choice
of t, x ∈ Y t , what implies d(x, Y ) ≤ t, because we can find y ∈ Y such that ||x − y|| ≤ t. As
x is arbitrary, supx∈X d(x, Y ) ≤ t. The same can be told about supy∈Y d(y, X). That implies
dH (X, Y ) ≤ t. As we took arbitrary t, applying the infimum we obtain

dH (X, Y ) ≤ inf{t ≥ 0, X ⊂ Y t , Y ⊂ X t }.

Suppose the above inequality is strict (<). Then there is  > 0 such that dH (X, Y ) +  is still
less. Define s = dH (X, Y ) + . Then s > d(x, Y ), ∀x ∈ X and s > d(y, X), ∀y ∈ Y . As
s > d(x, Y ), there is y ∈ Y such that ||x − y|| < s =⇒ x ∈ B̄(x, y) =⇒ x ∈ Y s . This
holds for every x ∈ X, so X ⊂ Y s . Likewise we prove Y ⊂ X s . That is a contradiction, since
s < inf{t ≥ 0, X ⊂ Y t , Y ⊂ X t }. We conclude that dH (X, Y ) = inf{t ≥ 0, X ⊂ Y t , Y ⊂ X t }.

Exercise 39. Compute the reach of the following subsets of R2 :

1. the set {(0, n), n ∈ Z},

2. the segment {(t, 0), t ∈ [0, 1]},

3. the unit circle with origin S1 ∪ {(0, 0)},

4. the square {(x, y) ∈ R2 , max{|x|, |y|} = 1},

31
 5. the ellipse {(x1 , x2 ) ∈ R2 , ( xa1 )2 + ( xb2 )2 = 1}

Proof. 1. Define this set as Z. So reach(Z) = inf{d(y, Z), y ∈ med(Z)}. We have that
med(Z) = {(x, n + 1/2), x ∈ R, n ∈ Z}, the bisector os two sequential points. For each
point y in one of these lines, dist(y, Z) = ||(x, n+1/2)−(0, n)|| = ||(x, 1/2)|| = x2 + 1/4.
p

The infimum over y occurs when x = 0 and we conclude reach(Z) = 1/2.

2. Denote this set as I. Take y = (y1 , y2 ) ∈ R2 . We want the values on I which distance to
y is d(y, I) = inf{ (y1 − t)2 + y22 , t ∈ [0, 1]} = min{ (y1 − t)2 + y22 , t ∈ [0, 1]}, since I is
p p

closed and bounded, there exists a projection. We must minimize (y1 − t)2 in the interval
[0, 1], but this clearly have only one solution. We conclude med(I) = ∅ and reach(I) = ∞.

3. We have that med(S1 ∩ 0) = ∂B(0, 1/2). For each y ∈ ∂B(0, 1/2), d(y, Z) = 1/2, the
distance to the origin. Therefore reach(S ∩ 0) = 1/2.

4. The medial axis of the square is an "X" crossing the diagonals. Because each point of the
diagonal forms a smaller square which minimizes distance the adjacency borders (we have
two). Then reach(square) = 0.

5. Suppose a > b for simplification, but in the other case, we only need to change the axis,
what does not affect the reach. Let (w, z) ∈ R2 in the exterior of the ellipse. Suppose we
have two different projections of this point in the ellipse and consider the circle centered
in (w, z) with distance being this minimum. Both figures are convex, so all points in the
segment between the projections are in the interior of the circle and the ellipse, however this
is an absurd, because the arc in the ellipse between the projection points are, therefore,
inside the circle, meaning, their distance too (w, z) is smaller. So there cannot be two
projections. The existence of a projection can be given by the ellipse being closed and
bounded. I can say the same argument for points above and below the x − axis. I infer,
then, that an open interval in the x − axis is the median axis. Let’s find this interval. Let
(t, 0) ∈ R2 .
Consider the problem

min(x − t)2 + y 2
x,y
x2 y 2
s.t. 2 + 2 = 1
a b

I can translate this problem into

b2 2
min f (x) = (x − t)2 + b2 − x
x∈[−a,a] a2

Using calculus,
b2 t
f 0 (x) = 2(x − t) − 2 2
x = 0 =⇒ x =
a 1 − b2 /a2
Then our answer is x ∈ {−a, a, 1−bt2 /a2 } that minimizes f . If x 6= ±a, we have two values of
y which address the minimum and, therefore, there are two projections. Denote E to refer
the ellipse. We then have that med(E) = (−s, s) such that, if x > s, f (x) is minimized at
a and if x < −s, at −a. In order to find s, we must calculate f ( 1−bt2 /a2 ) and compare with

32
 (a − t)2 . Then
2
a2 t t2 a2
  
2 2 2 2 2 2
−t +b −b a 2 =t b b − 2 + b2 > (a − t)2
a2 − b2 (a − b2 )2 (a − b2 )2
√
Solving this inequality we find s = a2 − b2 and, then, the reach will be the distance a − s.

Exercise 40. Compute the reaches of the subsets of Exercise 39.

Exercise 41. Verify that the clique complex of a graph is a simplicial complex. If the graph
contains n vertices, give an upper bound on the number of simplices of the clique complex.

Proof. Denote the clique complex K. Let σ ∈ K and τ ⊂ σ. Then σ is a clique of the graph.
Since τ is subset, every node it contais connects to each other, because they connect in σ. So τ
is a clique, what implies τ ∈ K.
In the worst case, all the vertices connects to each other, so we’ll have
n  
X n
= 2n − 1
i
i=1

simplices.

42. Improve the previous proposition as follows: Cecht (X) ⊂ Ripst (X) ⊂ Cechct (X),
Exercise q
where c = n+1 .
2n

33
8 Datasets have topology
8.1 Important definitions
Definition 8.1.1. Let X ⊂ Rn and i ≥ 0. The ith Betti curve of X is the map

βi (t) :R+ → N
t 7→ βi (X t )

As a consequence of the nerve theorem, the map t → βi (t) is equal to t 7→ βi (Cecht (X)). In
practice, we may use the following map, called the ith Betti curve of the Rips complex of X

βiRips (t) :R+ → N

t 7→ βi (Ripst (X))

8.2 Exercises
Exercise 43. Show that t 7→ β0 (t) is non-increasing. Show that t 7→ β0Rips (t) is also non-
increasing.

Proof. In order to prove the first statement, I shall find for each t the value βi (X t ), that is, we
need to find βi (K), where K is a triangulation of X t . Actually, I’ll the weak version, where
|K| must be homotopy equivalent to X t . In particular, a consider the Cecht (X). Take s < t
and consider N (V s ), N (V t ) the nerves respectively. If {x1 , ..., xm } is m-simplex of N (V s ), we
have that m k=1 B̄(xk , s) 6= ∅. For each k ∈ [[1, m]], B̄(xk , s) ⊂ B̄(xk , t) and for that reason
T
Tm
k=1 B̄(xk , t) 6= ∅ =⇒ {x1 , ..., xm } ∈ N (V ). Therefore as t increases, no simplices are removed
t

and, maybe, more can be added.

Remember that β0 (K) = dimZ0 (K) − dimB0 (K). We already know that Z0 (K) = C0 (K),
so its dimension do not change. Otherwise, observe that C1 (N (V s )) ⊂ C1 (N (V t )), as we proved
above. In that sense, no element can be removed from B0 (N (V s )) and hence its dimension cannot
decrease (and it can increase if we add new elements to it, when new simplices in C1 (N (V t ))
are not mapped in the existing images). We conclude t 7→ β0 (N (V t )) is non-increasing, then
t 7→ β0 (X t ) is non-increasing.
We can use the same argument to prove t 7→ β0Rips (t) is non-increasing. When t increases, we
only can add edges, but not remove, as the considered difference increases (note the condition
to add edges is xi , xj such that ||xi − xj || ≤ 2t).

The computational exercises (44 - 46) can be found in the Github3

Exercise 44. In the notebook is given a subset of R4 with 200 elements. It has been sampled on
a famous 2-dimensional object. Compute the Betti curves of its Rips complex on [0, 1]. Can you
recognize which surface it is?

3
[Link]/lucasmoschen/topological-data-analysis/blob/main/tutorials/[Link]

34
Exercise 45. In the notebook is given a collection of images from https: // www. cs. columbia.
edu/ CAVE/ software/ softlib/ coil-20. php . It consists of 20 objects, for each of which 72
pictures have been taken. Each image has 128×128 pixels. Embed each collection of 72 images
in R 128×128 , and compute the Betti curves of the corresponding Rips complex.

Exercise 46. We are given the data of this paper4 . It consists in 14 correlation matrices, each
matrix representing correlations between the components of a protein. Transform the matrices
of correlations into matrices of distances. Then, compute the 1-Betti curves of the Rips complex
for each of these matrices of distances. Compare the Betti curves of the different proteins. Do
you recognize two different types of proteins (open and closed )?

4
[Link]

35
9 Decomposition of persistence modules
9.1 Important definitions
Definition 9.1.1. Let K and L be two simplicial complexes, and VK , VL their set of vertices. A
simplicial map between K and L is a map f : VK → VL such that ∀σ ∈ K, f (σ) ∈ L. When there
is no risk of confusion, we may denote a simplicial map f : K → L instead of f : VK → VL .
We define a linear map fn : Cn (K) → Cn (L) as follows (definition on the simplices, and
extended by linearity):
fn : σ 7→ f (σ)1{dim(f (σ)) = n}

Definition 9.1.2. By definition of the homology groups, we have defined a map

(fn )∗ : Hn (K) → Hn (L).

It is called the induced map in homology. Explicitly, the map (fn )∗ can be described as follows
(the following formula is to be read modulo boundaries):
X X
c= σ · σ 7→ σ · fn (σ).
σ∈K(n) σ∈K(n)

Definition 9.1.3. Let i ≥ 0, t0 ≥ 0 and consider a cycle c ∈ Hi (Cecht0 (X)). Its death time is

sup{t ≥ t0 , (itt0 )(c) 6= 0}

and its birth time is

inf{t ≥ t0, (itt0 )−1 ({c}) 6= ∅}

persistence = death time - birth time

Definition 9.1.4. A persistence module V over R+ with coefficients in Z/2Z is a pair (V, v)
where V = (V t )t∈R+ is a family of Z/2Z-vector spaces, and v = (vst : V s → V t )s≤t∈R+ a family
of linear maps such that:

1. for every t ∈ R+ , vtt is the identity map,

2. for every r, s, t ∈ R+ such that r ≤ s ≤ t, we have vst ◦ vrs = vrt

When the context is clear, we may denote V instead of (V, v).

Definition 9.1.5. An isomorphism between two persistence modules V and W is a family of
isomorphisms of vector spaces φ = (φt : V t → W t )t∈R+ such that the following diagram commutes
for every s ≤ t ∈ R+ .

vst
s
V Vt
φs φt

Ws Wt
wst

36
Definition 9.1.6. Let (V, v) and (W, w) be two persistence modules. Their sum is the per-
sistence module V ⊕ W defined with the vector spaces (V ⊕ W )t = V t ⊕ W t and the linear
maps
(v ⊕ w)ts : (x, y) ∈ (V ⊕ W )s 7→ (vst (x), wst (y)) ∈ (V ⊕ W )t .

A persistence module U is indecomposable if for every pair of persistence modules V and W such
that U is isomorphic to the sum V ⊕ W, then one of the summand has to be a trivial persistence
module, that is, equal to zero for every t ∈ R+ . Otherwise, U is said decomposable.
Definition 9.1.7. Let I ⊂ R+ be an interval. Intervals have the form [a, b], (a, b], [a, b) or
(a, b), with a, b ∈ R+ such that a ≤ b, and potentially b = +∞. The interval module associated
to I is the persistence module B[I] with vector spaces Bt [I] and linear maps vst : Bs [I] → Bt [I]
defined as  
Z/2Z if t ∈ I, id if s, t ∈ I
Bt [I] = and vst =
0 otherwise 0 otherwise

Definition 9.1.8. A persistence module V decomposes into interval module if there exists a set
{Bi , i ∈ I} of interval modules such that V is isomorphic to the sum i∈I Bi ;. In other words,
L

there exists a multiset I of intervals of T such that

M
V= B[I].
I∈I

Multiset means that I may contain several copies of the same interval I. Such a module is said
decomposable into interval modules, or simply decomposable when the context is clear.

9.2 Exercises
Exercise 47. Consider a linear map f : V → W between vector spaces. Suppose that there
exists linear subspaces A ⊂ V and B ⊂ W such that f (A) ⊂ B. Show that one can define a map
f∗ : V /A → W/B as follows: to any equivalence class v + A of V /A, let f∗ (v + A) = f (v) + B.

Proof. We have to prove f∗ is well-defined. In other words, if v1 +A = v2 +A, that is, v1 −v2 ∈ A,
then f (v1 ) + B = f (v2 ) + B. In that sense, we must prove that f (v1 ) − f (v2 ) = f (v1 − v2 ) ∈ B.
But this is true since by hypotheses v1 − v2 ∈ A =⇒ f (v1 − v2 ) ∈ f (A) ⊂ B. Then f∗ is indeed
well defined.
Let’s prove it’s linear. Let α ∈ F, and v1 , v2 ∈ V . So

f∗ ((αv1 + v2 ) + A) = f (αv1 + v2 ) + B
= αf (v1 ) + f (v2 ) + B
= α(f (v1 ) + B) + (f (v2 ) + B)
= αf∗ (v1 + A) + f∗ (v2 + A)

The third equation is true because B = αB + B, that is, if b ∈ B, then b = α0 + b ∈ αB + B and

in b ∈ αB + B, one can find b1 , b2 ∈ B such that b = αb1 + b2 . Because of the linearity of B, we
have b ∈ B. We conclude f∗ is a linear map induced by f between quotient linear spaces.

37
Exercise 48. Let the simplicial K = {[0], [1], [2], [3], [4], [5], [0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0]}
and L = {[0], [1], [2], [0, 1], [1, 2], [2, 0]}. Consider the simplicial map f : i 7→ i modulo 3. Show
that the induced map (f1 )∗ is zero.

Proof. We have that (f1 )∗ : H1 (K) → H1 (L), such that

H1 (K) = {[0, 1] + [1, 2] + [2, 3] + [3, 4] + [4, 5] + [5, 0], 0}.

This happens because Z1 (K) has only two elements not equivalents. The same can be told about
H1 (L). Then

(f1 )∗ ([0, 1] + ... + [5, 0]) = f1 ([0, 1]) + ... + f1 ([5, 0])
= f ([0, 1]) + ... + f ([5, 0])
= [0, 1] + [1, 2] + [2, 0] + [0, 1] + [1, 2] + [2, 0] = 0

And its trivial that (f1 )∗ (0) = 0 (linear map), what implies the induced map (f1 )∗ is zero.

Exercise 49. Fill the empty spaces ( ) in the following proof of Brouwer’s fixed point theorem.

Proof. Let f : B̄(0, 1) → B̄(0, 1) be a continuous map, where B̄(0, 1) denotes the closed unit
ball of Rn . Let us show that f admits a fixed point (i.e., an element x ∈ B̄(0, 1) such that
f (x) = x). By contradiction, suppose that it is not the case. We can build an application
F : B̄(0, 1) → S(0, 1) ⊂ B̄(0, 1), such that F restricted to S(0, 1) is the identity. To do so, define
F (x) as the first intersection point between the half-line [x, f (x)) and S(0, 1).
Denote the inclusion i : S(0, 1) → B(0, 1). We have that F ◦ i : S(0, 1) → S(0, 1) is the
identity. By functoriality of homology, we obtain, for all i ≥ 0, the commutative diagrams.

i F i∗ F∗
S(0, 1) B̄(0, 1) S(0, 1) Hi (S(0, 1)) Hi (B̄)(0, 1) Hi (S(0, 1))

id
(id∗ )

But choosing i = n − 1, we have Hi (S(0, 1)) ' (Z/2Z), Hi (B̄(0, 1)) ' (0) and the following
diagram cannot commute:

(Z/2Z) 0 (Z/2Z)

id

Exercise 50. Show that the interval modules are indecomposable.

Proof. WLet V and W two persistence modules whose sum is isomorphic to B[I]. Then there is
φt
φ = (φt )t∈R+ such that Bt [I] → (V ⊕ W )t are isomorphic. If t 6∈ I, We have that Bt [I] = 0 is

38
isomorphic to (V ⊕ W )t , what implies (V ⊕ W )t = (0, 0) and we are done. Otherwise, if t ∈ I,
we have (V ⊕ W )t and Z/2Z are isomorphic. It’s clear that dim(Z/2Z) = 1, because the bases
only need one element. We claim that dim((V ⊕ W )t ) = 1. We already know {φt (1 + Z)} is a set
of independent sets of (V ⊕ W )t and we shall prove it spans the space. Take (v, w) ∈ (V ⊕ W )t .
Then, for some e ∈ Z/2Z,

(v, w) = φt (e) = φt ((1 + Z)α) = αφt (1 + Z).

Therefore 1 = dim((V + W )t ) = dim(V t ) + dim(W t ) =⇒ dim(V t ) = 0 xor dim(W t ) = 0, that

is, V t = 0 xor W t = 0. In special we have for all t, we have V t = 0 or W t = 0. Suppose V t 6= 0
and W s 6= 0, for some t, s ∈ R+ . We already proved that if t 6∈ I, then V t = 0 and if s 6∈ I, then
W s = 0, so we don’t need to consider these cases.
We know W t = 0 and V s = 0 by what we’ve proved in the first paragraph. By the commu-
tative property and supposing s ≤ t with no loss of generality,

Z/2Z

φt φs

(V ⊕ W )t (V ⊕ W )s
(v ⊕ w)ts

Therefore,

φt (1 + Z) = (v, 0) and φs (1 + Z) = (0, w), then vst (0) = v, wst (w) = 0

Alternatively
φt (0 + Z) = (0, 0) and φs (0 + Z) = (0, 0), then vst (0) = 0

This is clearly a contradiction.

Exercise 51. Let M be the unit circle of R2 , and X ⊂ R2 a finite subset. Denote the Hausdorff
distance  = dH (X, M). Suppose that  is small enough. Let U denote the persistence module
of the 1st homology of the Cech filtration of X. Using Theorem 7.3, shows that there exists an
interval I on which U is constant and equal to Z/2Z. Deduce the existence of a bar in the barcode,
and give a lower bound on its persistence. Do the same with Theorem 7.4.

Proof. Let’s denote U = (H1 (Cecht (X)))t∈R+ . By theorem 7.3, if we take

t ∈ [4dH (X, M), reach(M) − 3dH (X, M))

we have X t ≈ M. Then, by Proposition 5.14, we have isomorphic homology groups H1 (X) and
H1 (M). We know H1 (circle) = Z/2Z. Then we take I = [4dH (X, M), reach(M)−3dH (X, M)).
To use Theorem
q 7.4, we need the additional supposition that X ⊂ M is finite. If we take
I = [2dH (X, M), 35 reach(M)), we have the result.

39
Exercise 52. Compute the barcode of the filtration of Subsection 6.1:

with the following

√
filtration values: t(σ) = 0 for the vertices, t(σ) = 1
2 for the edges of the square,
and t(σ) = 2
2
for the diagonal edge and the triangle.
First let’s build the boundary matrix.

- σ1,2,3,4 σ5 σ6 σ7 σ8 σ9 σ10
σ1 0 1 0 0 1 0 0
σ2 0 1 1 0 0 1 0
σ3 0 0 1 1 0 0 0
σ4 0 0 0 1 1 1 0
σ5 0 0 0 0 0 0 1
σ6 0 0 0 0 0 0 0
σ7 0 0 0 0 0 0 0
σ8 0 0 0 0 0 0 1
σ9 0 0 0 0 0 0 1
σ10 0 0 0 0 0 0 0

as already placed in the notes. After apply Gauss reduction we obtain

- σ1,2,3,4 σ5 σ6 σ7 σ8 σ9 σ10
σ1 0 1 0 0 0 0 0
σ2 0 1 1 0 0 0 0
σ3 0 0 1 1 0 0 0
σ4 0 0 0 1 0 0 0
σ5 0 0 0 0 0 0 1
σ6 0 0 0 0 0 0 0
σ7 0 0 0 0 0 0 0
σ8 0 0 0 0 0 0 1
σ9 0 0 0 0 0 0 1
σ10 0 0 0 0 0 0 0

Consider the pairs (σ δ(j) , σ j ). We do not have δ(j) = 1, then (+∞, σ 1 ) is pair. Since δ(5) = 2,
(σ 2 , σ 5 ) is another pair. Continuing this reasoning we obtain the pairs

(σ 3 , σ 6 ), (σ 4 , σ 7 ), (σ 8 , +∞), (σ 9 , σ 10 ).

We conclude the barcodes will be

I1 = {(0.5, +∞)}, I0 = {(0, 1/2), (0, 1/2), (0, 1/2), (0, +∞)}

40
10 Stability of persistence modules
10.1 Important definitions
Definition 10.1.1. Consider two barcodes P and Q, that is, multisets of intervals {(ai , bi ), i ∈
2
I} of R¯+ such that ai ≤ bi for all i ∈ I. Here, R¯+ represent the extended real line R+ ∪ {+∞}.
A partial matching between the barcodes is a subset M ⊂ P × Q such that

• for every p ∈ P , there exists at most one q ∈ Q such that (p, q) ∈ M ,

• for every q ∈ Q, there exists at most one p ∈ P such that (p, q) ∈ M .

The points p ∈ P (resp. q ∈ Q) such that there exists q ∈ Q (resp. p ∈ P ) with (p, q) ∈ M are
said matched by M . If a point p ∈ P (resp. q ∈ Q) is not matched by M , we consider that it is
matched with the singleton p̄ = [ p1 +p2 p1 +p2
2 ,
q1 +q2 q1 +q2
2 ] (resp. q̄ = [ 2 , 2 ]). The cost of a matched
pair (p, q) (resp. (p, p̄), resp. (q, q̄)) is the sup norm ||p − q||∞ = sup{|p1 − q1 |, |p2 − q2 |}. The
cost of the partial matching M , denoted cost(M ), is the supremum of all such costs.
Definition 10.1.2. The bottleck distance between two barcodes P and Q is defined as the infi-
mum of costs over all the partial matchings:

db (P, Q) = inf{cost(M ), M is a partial matching between P and Q}.

If U and V are two decomposable persistence modules, we define their bottleneck distance as

db (U, V ) = db (Diagram(U ), Diagram(V )).

Definition 10.1.3. We now define an algebraic-flavored distance. Consider two persistence

modules V and W . Given  ≥ 0, an -morphism between V and W is a family of linear maps
φ = (φt : V t → W t+ )t∈R+ such that the following diagram commutes for every s ≤ t ∈ R+ :

vst
s
V Vt
φs φt

W s+ t+ W t+

ws+

Definition 10.1.4. An -interleaving between V and W is a pair of -morphisms (φt : V t →

W t+ )t∈R+ and (ψt : W t → V t+ )t∈R+ such that the following diagrams commute for every
t ∈ R+ :

vtt+2
t V t+
V V t+2
φt ψt+ ψt φt+

W t+ Wt W t+2
wtt+2

41
Definition 10.1.5. The interleaving distance between two persistence modules V and W is
defined as
di (V, W ) = inf{ ≥ 0, V and W are  − interleaved}.

10.2 Exercises
Exercise 53. Let M be the unit circle of R2 , and X ⊂ R2 a finite subset. Denote the Hausdorff
distance  = dH (X, M). Suppose that  is small enough. Let U denote the persistence module
of the 1st homology of the Cech filtration of X. Using the stability theorem, deduce the existence
of a bar in the barcode, and give a lower bound on its persistence. Compare your result with
Exercise 51.

11 Python tutorial
The tutorial can be found in the Github on the link:
[Link]/lucasmoschen/topological-data-analysis/blob/main/tutorials/tutorial-3.
ipynb

42