Lecture 3

Download as pdf or txt
Download as pdf or txt
You are on page 1of 14

Simplicial complexes

Žiga Virk
October 13, 2021

Topological and computational treatment of metric spaces relies on


their convenient description. Given a metric space, we would like to
have a finite combinatorial description, that can be used for computa-
tions. In the previous lectures we introduced planar triangulations as
an example of such a description for planar subsets. In this lecture we
will introduce simplicial complexes, which will form the basic structure
upon which all our later computations will depend.
Simplicial complexes are higher-dimensional analogues of planar
triangulations. While the later are collections of triangles that fit
together nicely, simplicial complexes are collections of higher dimen-
sional simplices (generalizations of triangles) that fit together nicely.
Essentially we will be building spaces from simple building blocks
(simplices) given a rule describing how these blocks fit together... just
like LEGO cubes.

1 Affine independence
Figure 1: Some geometric simplices:
a point, a line segment, a triangle, a
A point, a line segment, a triangle, a tetrahedron, etc. These are
tetrahedron.
some of the geometric simplices. They are basic building blocks of
geometric simplicial complexes. A geometric simplex is a convex hull
of a finite collection of points. Before we state their formal definition
we need to clarify a general position property required of a set of
points spanning such a simplex. Under this property we want a pair of
points to span a line segment, a triple of points to span a triangle (and
not just a line segment), etc.
Choose d, k ∈ N and let V = {v0 , v1 , . . . , vk } ⊂ Rd be a collection of
points. Their affine combination is any sum of the form
k k
∑ αi vi , with ∑ αi = 1. Figure 2: The affine hull of the two
i =0 i =0
points on the left is a line. The affine
The affine hull of V is the collection of all affine combinations of ele- hull of the three colinear points on
the right is also a line, implying
ments of V. An affine hull is always an affine linear subspace in Rd ,
these three points are not affinely
meaning it is obtained from a linear subspaces of Rd by a translation. independent.
Points {v0 , v1 , . . . , vk } are affinely independent if no vi can be ex-
pressed as an affine combination of points V \ {vi }. Proposition 1.1
explains how to test points for affine independence using linear inde-
pendence, and why each affine hull is a translated linear subspace.

Proposition 1.1. Points of V = {v0 , v1 , . . . , vk } ⊂ Rd are affinely


independent iff {v1 − v0 , v2 − v0 , . . . , vk − v0 } are linearly indepen-
simplicial complexes 2

dent. z
y
Proof. Assume points of V are not affinely independent. Then, with-
out the loss of generality, v0 = ∑ik=1 αi vi and ∑ik=1 αi = 1, which
implies equality ∑ik=1 αi (vi − v0 ) = 0 and not all αi are zero. We
conclude that the points of V are not linearly independent.
On the other hand assume ∑ik=1 β i (vi − v0 ) = 0 with not all β i
being zero. We define β 0 = − ∑ik=1 β i and observe that
k k x
∑ β i v i + β 0 v0 = 0 and ∑ βi = 0.
i =1 i =0 Figure 3: The convex hull of three
affinely independent points is a trian-
Choose K ∈ {0, 1, . . . , k } so that β K 6= 0. Then gle.
k k
βi βi
vK = ∑ − v
βK i
and ∑ −
βK
= 1.
i =0, i 6=K i =0, i 6=K

Hence points of V are not affinely independent.


T A linearly independent collection
of vectors in Rd can have at most d
elements. An affinely independent
Proposition 1.2. Suppose points of V = {v0 , v1 , . . . , vk } ⊂ Rd are collection of points in Rd can have at
affinely independent. Then for each point x ∈ Conv(V ) there ex- most d + 1 elements.

ist unique coefficients αi ∈ [0, 1], i ∈ {0, 1, . . . , k}, such that

k k
x= ∑ αi vi and ∑ αi = 1.
i =0 i =0

Coefficients αi in are called barycentric coordinates of point x in


Conv(V ).

Proof. The existence of such coefficients αi follows from x ∈ Conv(V ).


In order to prove the coefficients are unique assume the statement
holds for two different sets of coefficients αi and αi0 , i.e.,
k k k k
x= ∑ αi vi = ∑ αi0 vi and ∑ αi = ∑ αi0 = 1.
i =0 i =0 i =0 i =0

At some index i the coefficients αi and αi0 differ. Without the loss of
generality we can assume that index is zero, i.e., α0 − α00 6= 0. Then
k
(α0 − α00 )v0 = ∑ (αi0 − αi )vi
i =1

and
kαi0 − αi
v0 = ∑ α − α 0 vi ,
i =1 0 0
which contradicts the assumption that the points of V are affinely
independent.
simplicial complexes 3

2 Geometric simplicial complex

We are now ready to define our basic building blocks.

Definition 2.1. Let k, d ∈ {0, 1, . . .}, k ≤ d. A geometric sim-


plex σ in Rd is the convex hull of an affinely independent family V =
{v0 , v1 , . . . , vk } ⊂ Rd , i.e., σ = Conv(V ).

The following is some terminology related to a geometric simplices


σ = Conv({v0 , v1 , . . . , vk }):
Figure 4: A two-dimensional simplex
• Dimension: dim(σ) = k. We sometimes express it by writing it as has six simplices as faces (three edges
supscript: σ = σk . and three vertices), three of which are
facets (edges).
• Vertices of σ: v0 , v1 , . . . , vk .

• Edges of σ: convex hulls of pairs of vertices.

• We say that σ is spanned by the set of its vertices.

• If simplex τ is spanned by a subset of the vertices of σ, we say that:

– τ is a face of σ.
– σ is a coface of τ.
– τ is a facet of σ if dim(τ ) = dim(σ ) − 1.
T All our simplicial complexes will

Note that ∼
σk
= D k . By Proposition 1.2 each point of σ is uniquely
be finite. For that reason we will be
dropping the word “finite”. There
described by its barycentric coordinates using the vertices of σ. also exist simplicial complexes with
We can now use these building blocks to assemble more complicated infinitely many simplices. However, a
proper definition of infinite simplicial
spaces. complexes brings along additional
technicalities which we want to avoid
in our context.
Definition 2.2. Let d ∈ {0, 1, . . .}. A (finite) geometric simpli-
cial complex K ⊂ Rd is a (finite) collection of geometric simplices,
such that:

a: If σ ∈ K and τ is a face of σ, then τ ∈ K.

b: If σ, τ ∈ K, then σ ∩ τ is either empty or a common face of both.

Each planar triangulation has a corresponding simplicial complex


consisting of all triangles, edges and vertices of the triangulation.
Let K be a simplicial complex. We define: Figure 5: The smallest two-
dimensional simplicial complex con-
• Dimension dim(K ) = maxσ∈K dim(σ ). A one-dimensional simplicial sists of a triangle and all its faces:
complex is a graph. three edges and three vertices.

• Vertices of K as the collection of all vertices of all simplices of K.


simplicial complexes 4

• Edges of K as the collection of all edges of all simplices of K.

• A geometric simplicial complex L is a subcomplex of K [notation:


L ≤ K], if L ⊂ K.

• For n ∈ {0, 1, . . .} the n−skeleton of K [notation: K (n) ] is the sim-


plicial subcomplex of K consisting of all simplices of K of dimension
at most n. For example, K (0) is the set of vertices of K.
Figure 6: The simplicial complex
• The body of K [notation: |K |] is the union of all simplices of K. from Figure 5 (left) and its 1-skeleton
(right) consisting of three edges and
Formally speaking, a geometric simplicial complex in Rd is a collec- three vertices.
tion of simplices and its body is a subset in Rd . In practice however
we will be often identifying the two objects in geometric discussions.
From now on we will be visualizing simplicial complexes by drawing
their body and assuming the underlying structure of asimplicial com-
plex. Figure 7: On the left there is a geo-
We are now ready to describe a connection between a metric sub- metric simplicial complex presented
by drawing its body. Each edge of
space of a Euclidean space and its combinatorial description. a sketched triangle and each vertex
of a sketched edge is assumed to be
in the complex. On the right is the
Definition 2.3. Let d ∈ {0, 1, . . .}. A triangulation of a subspace 1-skeleton of the simplicial complex on
X ⊂ Rd is a simplicial complex K in Rd , such that |K | ∼= X. the left.

Not every subspace of Rd admits a triangulation. However, all the


subsets that will arise in our context will admit it. Triangulations of
BR2 ((0, 0), 1) include examples in Figure 8 and Delaunay triangula-
tions. A geometric simplicial complex is a triangulation of its body.
Occasionally we will want to refine the triangulation of a space,
meaning we will want to decrease the size of simplices in order to
improve visualisation, level of details, etc. Such refinements are called
subdivisions. Given a geometric simplicial complex K, a geometric Figure 8: Some triangulations of D2 .
simplicial complex L is its subdivision, if each simplex of K is the
union of a collection of simplices from L. As an example we already
mentioned the barycentric subdivision of planar triangulations, which
also exists for simplicial complexes. At this point we will refrain from
introducing the formal definition. The lower right part of Figure 8 Figure 9: Some triangulations of S1 .

depicts a subdivision of a single 2-simplex, see also Figure 10.

3 Abstract simplicial complex

When buying a commercial object to be assembled, be it a piece


of furniture, a toy or a model made of cubes, or a picture made of
puzzles, the package usually arrives in a big box. On the box is a
picture of the object, which in our context represents the body of a Figure 10: A simplicial complex and
its subdivision.
geometric simplicial complex. On the picture we can often determine
pieces, which in our setting would be geometric simplicial complexes.
simplicial complexes 5

Pieces on that picture have specific locations and just like geometric
simplices, could be described by specific coordinates. However, the as-
sembly instructions contain no coordinates. There is a good reason for
that1 . In order to assemble the object, the instructions only provide a 1
Besides the fact that nobody would
list of pieces and instructions about how to put them together. That purchase such an item.

information is sufficient to reconstruct the object. Abstract simplicial


complex plays a role of such instructions.
Assume we want to describe a geometric simplicial complex. That
means we have to provide a list of all simplices. A simplex could be
provided by a list of coordinates of its vertices, but then we also have
to make sure the simplices intersect appropriately. It would be much
easier to just list the simplices and describe how they fit together in a
coordinate free way. Here is a way to do it.

Definition 3.1. Let V be a finite set. An abstract simplicial com- T In some sources the non-empty
condition in the definition of an
plex L on V is a family of non-empty subsets of V, such that if σ ∈ abstract simplicial complex is omitted
L and τ ⊆ σ is non-empty, then τ ∈ L. and the empty set is always included
as an abstract simplex of dimension
−1.
A few more accompanying definitions using the notation of Defini-
tion 3.1:
• An abstract simplex σ is an element of L. Its dimension is dim(σ ) =
|σ| − 1.
• If τ ⊆ σ ∈ L, then:

– τ is a face of σ.
– σ is a coface of τ.
– τ is a facet of σ if dim(τ ) + 1 = dim(σ ).

• Dimension dim( L) of L is the maximal dimension of a simplex in L.

• The (closed) star of a vertex v ∈ K is StK (v) = St(v) = {σ ∈ K |


σ ∪ {v} ∈ K } ≤ K.

• The link of a vertex v ∈ K is LkK (v) = Lk(v) = {τ ∈ St(v) | v ∈


/
τ } ≤ St(v).
A geometric simplex is a subset of an Euclidean space, provided as
the convex hull of the collection of its vertices. Each vertex is given Figure 11: A star (left) and a link
as a point in space, usually in terms of coordinates. A geometric sim- (right) of a vertex.

plicial complex is a set of such simplices, contains all faces and has to
satisfy the intersection properties of Definition 2.2.
An abstract simplex is just a collection of vertices. No coordinates
are needed. An abstract simplicial complex is a set of such collections
which contains all faces (all subsets of its elements). There are no
intersections to be checked. It is a complete combinatorial description
of a topological space.
simplicial complexes 6

Example 3.2. Let K be a geometric simplicial complex provided by


Figure 12. As a geometric simplicial complex, K contains specific
geometric simplices described by the coordinates of their vertices. We
can construct a corresponding abstract simplicial complex L. Label the
vertices as demonstrated by the figure. Then d
L = {{ a, c, d}, { a, b}, {b, c}, {c, d}, {d, a}, { a, c}, { a}, {b}, {c}, {d}, }.

No coordinates are involved. We could also only list the inclusion-


maximal simplices, which completely determine the simplicial complex:
{{ a, c, d}, { a, b}, {b, c}}.
a c
A simpler structure of an abstract simplicial complex will suffice
for most of our topological analysis of spaces and the corresponding
computations. Indeed, it will simplify them. A geometric simplicial
complex however is still useful when we want to visualise a complex.
For example, outputs of various scans come in a form of geometric b
simplicial complexes modelling the scanned shape. While geometric Figure 12: A picture accompanying
Example 3.2.
simplicial complexes describe geometric information about the space
(various sizes, lengths, etc.), abstract simplicial complexes contain only
topological information (homeomorphic type).
It is easy to turn a geometric simplicial complex into an abstract
simplicial complex: replace each coordinate given vertex by a unique
label. The opposite is a bit harder. Turning an abstract simplicial
complex into a geometric simplicial complex requires us to choose co-
ordinates of vertices in line with the requirements for a geometric sim-
plicial complex. If it can be done, such a geometric simplicial complex
is called a geometric realization (or just realization) of the original
abstract simplicial complex. It turns out that geometric realizations
always exists, although obtaining them in a low-dimensional space is x1 x2 x3
typically hard. The following are two special cases of such realizations.

Theorem 3.3. Every abstract simplicial complex K with n vertices ad-


mits a geometric realization in Rn−1 .

Proof. Simplicial complex K is a subcomplex of the full simplicial


complex L on n vertices, i.e., the simplicial complex, whose simplices
are all subsets of vertices of K. As L admits a realization in Rn−1 as
an (n − 1)-simplex (i.e., the convex hull of a collection of n affinely
independent points), so does K as its subspace.

y1 y2 y3
Figure 13: A sketch of a one-
Theorem 3.4. Every abstract simplicial complex of dimension d ad-
dimensional abstract simplicial
mits a geometric realization in R2d+1 . complex (graph) with no realiza-
tion in R2 . The complex consists of
all edges between xi and y j .
simplicial complexes 7

A proof of Theorem 3.4 is provided in Appendix.


As an example consider graphs, i.e., one-dimensional simplicial
complexes. It is well known that some graphs are planar, which means
they admit a geometric realization in the plane. However, there are
graphs, that are not planar. These graphs can only be realized in
R3 = R2·1+1 (and, of course, in Rm for m > 3). See Figure 13.
One of the goals of this course is the following: given an abstract c
simplicial complex, extract topological properties of its geometric
realization. We will study and analyze spaces by working with their
triangulations.
a b
Remark 3.5. It is important to understand the differences between a Figure 14: A metric space (left) and
metric space, its triangulation and a corresponding abstract simpli- the corresponding geometric simplicial
cial complex. In practice however, we will be frequently vague in our complex (right). The correspond-
ing abstract simplicial complex is
expression for the sake of simplicity, ofter referring to just simplicial {{ a, b, c}, { a, b}, {b, c}, { a, c}, { a}, {b}, {c}}.
complex. Given a picture of a space like the one in Figure 12, we will
keep in mind the three possible interpretations and use the one that fits
the context at the moment.
Also note that the nomenclatures are essentially the same for the
abstract and geometric simplicial complexes. We declare this to be
the case for all further2 definitions as well. For example, an abstract 2
Including the concepts of link and
simplicial complex L is a triangulation of a metric space X if the cor- star of a complex at a point.

responding geometric simplicial complex is, i.e., if the body of a geo-


metric realization of L is homeomorphic to X.

Example 3.6. One of our standard examples of a metric space will


be torus T. It is a two-dimensional metric space, actually a surface,
depicted in Figure 15. A triangulation of T in terms of an abstract
simplicial complex is provided by Figure 17.
Topologically speaking, torus can be obtained from a square by iden-
tifying the opposite sides along the same direction. This construction is
depicted in Figure 16.
Figure 15: Torus.
As a result we can obtain a structure of an abstract simplicial com-
plex by triangulating a square and respecting the mentioned identifica-
tions. This provides a convenient topological visualisation of a torus.
Observe that a triangulation of T in terms of a geometric simplicial
complex would be more complicated and not presentable in the plane.
simplicial complexes 8

a Figure 16: Torus arising from a


a square. Starting with a square (top
left) we identify its pairs of opposite
sides along the same direction as the
b b labels and arrows suggest. Identifying
b b the sides a we obtain a cylinder (top
right). Identifying the other pair of
sides, which represent loops b in the
cylinder, we obtain the torus (bottom
right).
a

b b

The mentioned abstract simplicial complex is provided by Figure 17.


We divide the square into 18 triangles and keep in mind the identifi-
cations suggested by the arrows. The two sides of the square along the x v w x
single arrows get identified along the direction of the arrows, and the
same holds for the two sides along the double arrows. For the sake of
clarity we also labeled the outer vertices of the triangles as each label z z
appears at least twice due to the identifications.

Example 3.7. Choose n ∈ {1, 2, . . .}. In this example we provide the y y


simplest triangulations of discs and spheres.
Let σn be an n-simplex and define K to be the simplicial complex
whose only maximal simplex is σn , i.e., K contains σn and all of its x x
faces. Simplicial complex K is a triangulation of D n . v w
Figure 17: A triangulation of a torus
To obtain a triangulation of Sn−1 remove from K the maximal sim- in terms of an abstract simplicial
plex, i.e., K 0 = K \ {σn }. Simplicial complex K consists of all faces of complex.
σn but does not contain σn itself. Simplicial complex K 0 is a triangula-
tion of Sn−1 .

Two invariants
Here we provide two invariants (of a space) that can be extracted
from a triangulation. Both are homotopy invariants (and hence also
topological invariants), meaning they coincide for homotopically equiv-
Figure 18: A triangle as a triangu-
alent spaces. A space typically has infinitely many possible triangu- lation of D2 and its boundary as a
lations. Imagine all possible Delaunay triangulations: they are all triangulation of S1 . In a similar way
a solid tetrahedron is a triangula-
triangulations of D2 . We conclude that the numbers of vertices, edges,
tion of D3 while its boundary is a
triangulation of S2 .
simplicial complexes 9

or higher dimensional simplices in a triangulation can’t be topological


invariants.
The first invariant is the number of components. Given a triangula-
tion K, it is easy to extract that number from K (1) (which is a graph)
Figure 19: A complex with two
using standard approaches of graph theory. Later we will explain in components.
detail how to obtain this number in terms of homology. For example,
the simplicial complex in Figure 19 has two components.
The second invariant is the Euler characteristic, which can be de-
fined for simplicial complexes.

Definition 3.8. Suppose K is a simplicial complex and let ni denote


the number of i-simplices in K. The Euler characteristic χ(K ) ∈
Z is defined as χ(K ) = n0 − n1 + n2 − n3 + . . . .
The Euler characteristic of a metric space is the Euler character-
istic of any of its triangulations.

As was mentioned above, the Euler characteristic is homotopy


invariant. Using this fact we can compute the following cases: Figure 20: A series of homeomorphic
simplicial complexes, each differing
from the previous one by a small
• Let X be a one-point space. Then χ( X ) = 1. Since each Delaunay
modifications. Note that the modifica-
triangulation K is homotopic to a point (meaning that |K | ' X), tions preserve the Euler characteristic.
we also conclude χ(K ) = 1, a statement which we have already In the first step we add a point and
a vertex; in the second step a point
proved directly. In fact, the homotopy invariance implies that each we add a vertex, two edges and a tri-
triangulation of a contractible space is of Euler characteristic 1. angle; and so on. Each new addition
contributes a total of 0 to the Euler
• The Euler characteristic of a torus is 0. It can be computed di- characteristic.

rectly from the triangulation presented by Figure 17, which has 18


triangles, 27 edges and 9 vertices (keep in mind the identifications).

• Let n ∈ {0, 1, 2, . . .}. Then χ(Sn ) = 1 + (−1)n .

Proof. Let σn+1 be an (n + 1)-simplex and define K to be the


simplicial complex whose only maximal simplex is σn+1 . As we
know K is a triangulation of D n+1 . As D n+1 is contractible, χ(K ) =
1. We also mentioned that K 0 = K \ σn+1 is a triangulation of Sn .
As K 0 is obtained from K by removing an (n + 1)-simplex, χ(K 0 ) T χ(Sn ) could also be computed from
the triangulation K 0 directly using the
is obtained from χ(K ) by removing a contribution of that simplex,
binomial formula.
which is (−1)n+1 . Hence χ(Sn ) = 1 − (−1)n+1 = 1 + (−1)n .

4 Simplicial maps

Just as simplicial complexes provide a convenient combinatorial


description of metric spaces, simplicial maps provide a combinatorial
description of continuous maps. We first define them in the abstract
setting.
simplicial complexes 10

Definition 4.1. Suppose K and L are abstract simplicial complexes.


A simplicial map between K and L is an assignment f : K (0) → L(0)
on vertices, such that for each abstract simplex {v0 , v1 , . . . , vk } ∈ K
its image { f (v0 ), f (v1 ), . . . , f (vk )} is an abstract simplex in L. ,→

Figure 21: An embedding of a sim-


plicial subcomplex L ≤ K into K is
Remark 4.2. A simplicial map will be usually denoted by f : K → L. identity on the vertices and always a
However, since K and L are collections of sets, such a notation would simplicial map.
formaly include maps that map, say, a vertex to an edge, a highly
unfavourable occurence. When talking about simplicial maps K → L
we thus always consider only maps in the sense of Definition 4.1, i.e.,
maps that map a vertex to a vertex, while images on simplices are
always determined by the values on the vertices:

• For each vertex v ∈ K we define a corresponding vertex f (v).

• For each abstract simplex σ = {v0 , v1 , . . . , vk } ∈ K its image


f (σ ) = { f (v0 ), f (v1 ), . . . , f (vk )} is determined by the values on its
vertices.

• Note that f (σ ) is a set, meaning there are no repetitions of ele-


ments. In particular this means that each vertex appears at most
once in f (σ), even if it appears multiple times as f (vi ). As a re-
sult the image of an n-dimensional simplex can be of dimension less
than or equal to n, but never more than n.
b
Example 4.3. Let K be the simplicial complex in Figure 22. Assign-
ment a 7→ a; b 7→ c; c 7→ c; d 7→ d; e 7→ b can be verified e
to induce a simplicial map K → K. Note that triangle { a, b, c} gets a d
mapped to edge { a, c}.

We are now ready to define simplicial maps in the geometric set-


ting. c
Figure 22: Simplicial complex K of
example 4.3.
Definition 4.4. Suppose K and L are geometric simplicial complexes.
A map f : K → L is a simplicial map, if:

1. For each vertex v of K its image f (v) is a vertex of L.

2. The corresponding map between the corresponding abstract sim-


plicial complexes is simplicial, i.e., if {v0 , v1 , . . . , vk } span a geo-
metric simplex in K then { f (v0 ), f (v1 ), . . . , f (vk )} span a geomet-
ric simplex in L.

3. Map f is linear on simplices (in terms of barycentric coordinates),


simplicial complexes 11

i.e.,
k k k
∀ti ∈ [0, 1], ∑ ti = 1, ∀ v i ∈ K (0) : f ( ∑ ti vi ) = ∑ t i f ( v i ).
i =0 i =0 i =0

Given a simplicial map between geometric simplicial complexes the


induced map (i.e., the restriction to vertices) between abstract simpli-
cial complexes is simplicial. Conversely, each simplicial map between
abstract simplicial complexes corresponds to the unique simplicial map
between the corresponding geometric simplicial complexes: the exten-
sion from vertices to geometric simplices is defined using the formula
of item 3 of Definition 4.4. In accordance with our declarations simpli-
cial maps will be used to denote maps either in geometric or abstract
setting: in case of a preferred interpretation it will be stated explicitly
or should be obvious from the context.
Simplicial maps between geometric simplicial complexes are con-
tinuous maps as they are linear (hence) continuous on each simplex.
Surprisingly enough, each continuous map can be (up to homotopy)
represented by a simplicial map, which means that as long as we are
interested in homotopical properties, we can restrict ourselves to sim-
plicial maps.

Theorem 4.5. Suppose f : K → L is a continuous map between ge-


ometric simplicial complexes. Then there exist sufficiently fine sub-
divisions K 0 of K and L0 of L, and a simplicial map f 0 : K 0 → L0 ,
such that f ' f 0 . We call f 0 a simplicial approximation of f .

The subdivisions above can be taken to be sufficiently fine barycen-


tric subdivision. A continuous map between simplicial complexes is
Figure 23: The upper part of the
formally a map between the bodies of the simplicial complexes. In this
figure presents a simplicial complex.
sense both f and f 0 are maps |K | = |K 0 | → | L| = | L0 | hence f ' f 0 The middle part consists of a smooth
makes sense. curve (bold) superposed on the sim-
plicial complex. The bottom part
consists of a simplicial approximation
Elementary collapses (bold red) of a smooth curve super-
posed on the simplicial complex and
Elementary collapses are minor local modifications of simplicial the curve. The indicated simplicial
approximation requires a triangulation
complexes, which preserve its homotopy type. Conveniently enough, of the domain S1 with at least 12
they can be described in purely combinatorial terms. Their impor- edges.
tance stems from the following Lemma.

Lemma 4.6. Let K be a geometric simplicial complex containing sim-


plex σ = {v0 , v1 , . . . , vk } and let τ = {v1 , . . . , vk } be its facet. If σ
is the only coface3 of τ, then the inclusion i : K \ {τ, σ } ,→ K is a 3
i.e., a simplex which contains τ.
homotopy equivalence.

Proof. The proof is sketched in Figure 24.


simplicial complexes 12

We first need to subdivide σ and τ. Choose a point a in the middle


of τ and connect it to all vertices of σ. This induces a subdivision of σ
and τ and in fact of K as no other simplex contains4 σ or τ. 4
If there was another simplex contain-
In order to obtain a continuous deformation5 from K to K \ {τ, σ }, ing σ, then that simplex would have
been a coface of τ, which contradicts
slide a towards v0 . This sliding is a linear homotopy and can be easily our assumptions. In particular, If σ is
described in the barycentric coordinates of the new subdivision of the only coface, then τ is a facet of σ.
This fact also refers to conditions of
K. Definition 4.7.
5
Homotopy equivalence.

τ σ a v0

Figure 24: Elementary collapse from


Lemma 4.6 with σ being the triangle
and τ its left side.
Definition 4.7. Let K be a simplicial complex, τ (k−1) ⊂ σ(k) ∈ K,
and assume σ is the only coface of τ. A removal K → K \ {τ, σ }
is called an elementary collapse.

By Lemma 4.6 each elementary collapse preserves the homotopy


type of a complex. Note that the collapsing map K → K \ {τ, σ} is
not6 a simplicial map on K. It is, however, a simplicial map on the
subdivision of K employed in Lemma 4.6, defined by mapping a 7→ v0
and keeping all the other vertices intact. Its homotopy inverse is the
Figure 25: The elementary collapse of
inclusion K \ {τ, σ } ,→ K, which is a simplicial map. Figure 24 is usually indicated by an
Elementary collapses are convenient because they provide us with a arrow from τ into σ.
6
Except if τ is a vertex.
simple combinatorial condition that can be used to induce homotopy
equivalence on abstract simplicial complexes. This idea will be further
expanded later within the context of Discrete Morse Theory.

Figure 26: An example of a simpli-


fication of (the homotopy type of) a
simplicial complex using elementary
collapses.
simplicial complexes 13

5 Concluding remarks

Recap (highlights) of this chapter


• Geometric simplex;

• Geometric simplicial complex;

• Abstract simplicial complex;

• Geometric realization;

• Simplicial map;

• Simplicial approximation and elementary collapse.

Background and applications


Simplicial complexes model spaces in a wide spectrum of theory and
applications. Great portions of topology and geometry are based on
them due to their simple structure and amenability to combinatorial
treatment. On the applied side simplicial complexes are typically used
to model shapes.

Appendix: Proof of Theorem 3.4


Before we begin with the proof we clarify a fact that will be used.
A generic7 (random) collection of n + 1 points in Rn is affinely inde- 7
Notion “generic” as used in this
pendent. Geometrically this is easy to believe: appendix is usually referred to as
“general linear position” in the litera-
ture.
• Generic two points in R will be different;

• Generic three points in R2 will not be colinear;

• Generic four points in R3 will not be coplanar.

Similarly, even for k > n + 1 a generic set V of k points in Rn has


the same property: each a collection of n + 1 points in V is affinely
independent. For example, in a generic collection of points in the
plane no triple of points will be collinear. We will only use the fact
that generic collections exist. This fact can be proved using linear
algebra.

Proof of Theorem 3.4. Let K be an abstract simplicial complex of di- Figure 27: A generic collection of 5
mension d, whose vertices are v0 , v1 , . . . , vk . Choose a generic collection points in the plane, meaning that no
three are collinear. Only by adding
of points V = { x0 , x1 , . . . , xk } ⊂ R2d+1 , meaning that each collection a point on any grey line does the
of 2d + 2 points from V is affinely independent. We will prove that the generic condition brake. If we add
any other point to this collection, the
correspondence vi ↔ xi for all i ∈ {0, 1, . . . , k} provides a geometric
obtained collection of 6 points is still
realization of K. generic.
simplicial complexes 14

For each abstract simplex σ ∈ K spanned by v j0 , v j1 , . . . , v jm , the


corresponding geometric simplex σ0 is spanned by the affinely indepen-
dent collection x j0 , x j1 , . . . , x jm . It remains to prove that if σ, τ ∈ K,
then σ0 ∩ τ 0 = (σ ∩ τ )0 .
As (σ ∩ τ )0 ⊆ σ0 , τ 0 by the definition, we have σ0 ∩ τ 0 ⊇ (σ ∩ τ )0 .
To prove the other inclusion we will make use of the dimension
assumption. Let z ∈ σ0 ∩ τ 0 , which means that z can be expressed as a
convex combination of vertices in σ0 and also as a convex combination
of vertices in τ 0 . As the total number of vertices in τ 0 and σ0 is at
most 2n + 2 (by the dimension assumption), the generic condition
implies these are affinely independent, and thus the convex (affine)
combinations above coincide as they have to be unique by Proposition
1.2. In particular, this means that only the barycentric coordinates
corresponding to the vertices that lie in both simplices (i.e., σ ∩ τ)
can be non-zero, which implies z ∈ (σ ∩ τ )0 and hence σ0 ∩ τ 0 ⊆
(σ ∩ τ )0 .

You might also like