Lecture 5: Simplicial Complex

2-Manifolds, Simplex and Simplicial Complex

Scribed by: Lei Wang

First part of this lecture finishes 2-Manifolds. Rest part of this lecture talks about simplicial complex.

1 2-Manifolds
1.1 Comparing Curves
Given two curves P, Q on a 2-manifold M. Measure the similarity between P and Q is an interesting
problem. Traditional metric, like Hausdroff distance, is not suitable here. As can be seen in Figure 1, the
Hausdroff distance between P and Q can be very small while they are of great difference. We need other
similarity measurements.
Fréchet distance is a good similarity measurement for curves in Euclidean
space. It can be simply described by a daily example. Suppose a dog and its P
owner are walking along two different paths (curves), connected by a leash. Q
Both of them are moving continuously and forwards only, at any speed or even
stop. Then length of the shortest leash is the Fréchet distance between the two
Figure 1: Two greatly dif-
paths (curves). Fréchet distance is a good similarity measurement for curves in
ferent curves have a small
Euclidean space. For curves on surfaces, distance between two points can be
Hausdroff distance
hard to compute.
Another way is using the minimal area swept when continuously deforming P and Q into one as their
distance. However, it has the same problem as Fréchet distance when handling curves on surfaces. This
measurement also requires P and Q to share the same start point and end point, i.e., they form a loop. If
they do not, we can connect their start points and end points, respectively, to get a loop.
To handle curves on surfaces, we can map them to a space where similarity
measurements like Fréchet distance or minimal deformation area are easy to be
computed. Recall that the universal cover of M is planar, which is computation
friendly to Fréchet distance and minimal deformation area. We can map P and
Q
Q to the universal cover of M, and use the distance between their images to
measure the similarity of P and Q.
However, not any two curves on M can be measured in this way. For ex- P
ample, as Figure 2 shows, P and Q can not be deformed to each other, because
they are not homotopic.
Figure 2: P and Q can not
be continuously deformed
1.2 Homotopy to each other.
Definition 1.1 Let X and Y be two topological spaces. Two continuous maps
f, g : X → Y are homotopic if there exist a continuous map H : [0, 1] × X → Y such that H(0, ·) = f and
H(1, ·) = g, denoted as f ∼ g. The continuous map H is called a homotopy between f and g.
Consider [0, 1] as a time interval, f and g are homotopic means we can find a family of maps H such
that f and g are continuously deformed: at time 0 we have f , and at time 1 we have g.

1
Definition 1.2 Two topological spaces X and Y are homotopic equivalent if there exist two continuous maps
f : X → Y and g : Y → X, such that f ◦ g ∼ idY and g ◦ f ∼ idX .

Definition 1.3 Given a topological space X, and its subspace A ⊆ X. A continuous map f : [0, 1] × X → A
is a deformation retraction from X onto A if for any x ∈ X and any a ∈ A, there is f (0, x) = x, f (1, x) ∈ A
and f (1, a) = a. A is called a deformation retract of X.
We can consider a deformation retraction f as a continuous deformation process squeezing X to A. A
well known example of deformation retraction is to deforming an annulus to a cycle, as Figure 3 shows. All
points in the annulus moves straightly towards center until reach the inner cycle boundary. Notice that this
deformation retraction is irreversible.

2 Simplicial Complex
Simplicial complex provides an good way for representing topological struc-
tures in computers. It is also an interesting topic of algebraic topology due to its
combinatorial nature. In following lectures, we will know simplicial complex
is the basis of simplicial homology. A simplicial complex is built by gluing its
blocks, called simplex, together.

2.1 Simplex Figure 3: Deforming an

annulus to a cycle
A given set of points {p0 , p1 , ..., pd } ⊆ IRd is geometrically independent if the
set of vectors {pi −p0 } is linearly independent. Here, two vectors vi , vj are linearly independent if there does
not exist two constant ai , aj such that ai vi + aj vj = 0 and either ai or aj should be non-zero. In IRd we can
have at most d−1 geometrically independent points. A combination x = di=0 ai pi is a convex combination,
P
Pd
if i=0 ai = 1 and all ai are non-negative. The convex hull of a given point set {p0 , p1 , ..., pd } is the set of
all convex combinations, denoted as CH({p0 , p1 , ..., pd }) = { di=0 ai pi | di=0 ai = 1 and ai ≥ 0}.
P P

Definition 2.1 A d-simplex σ is the convex hull of d + 1 geometrically independent points {p0 , p1 , ..., pd },
i.e., σ = CH({p0 , p1 , ..., pd }). We also say the point set {p0 , p1 , ..., pd } spans σ. d is called dimension of σ,
denoted as dim σ = d.
First few low dimensional simplices have their own names: 0-simplex, 1-simplex, 2-simplex and 3-
simplex are also called vertex, edge, triangle and tetrahedron, respectively. Figure 4 shows them.

Figure 4: From left to right show a vertex, an edge, a triangle and a tetrahedron

Any non-empty subset A of a point set {p0 , p1 , ..., pd } spans a simplex σA ⊆ σ. σA is called a face of
σ. If A is a proper subset, then σA is called a proper face of σ. The boundary of σ, denoted as ∂σ, is the
union of all proper faces of σ.
From its definition, we know a d-simplex σ must be convex. It also has many good topological proper-
ties: σ is homeomorphic to a Bd ; its boundary is homeomorphic to Sd−1 ; and the interior of σ is homeomor-
phic to IRd , i.e., σ \ ∂σ ≈ IRd . Actually, all d-simplex are homeomorphic.

2
 P on {p0 , p1 , ..., pd }, then any point p ∈ σ can be represented
P 2.2 Let σ be a d-simplex defined
Definition
as p = di=0 ai pi , where ai ≥ 0 and di=0 ai = 1. The vector ha0 , a1 , ..., ad i is called the barycentric
coordinate of p.

2.2 Simplicial Complex

Definition 2.3 A simplicial complex K is a collection of simplices such that
(1) If σ ∈ K, then for any face σ 0 of σ, we have σ 0 ∈ K;
(2) For two simplices σ1 , σ2 ∈ K, σ1 ∩ σ2 is either ∅ or a face of both σ1 and σ2 .
From its definition, we can see K is a combinatorial representation of a topological space. All simplices
in K meet nicely and have no improper intersection in K. The dimension of K is the highest dimension of
any of K’s simplices. The set of simplices shown in Figure 5a is a simplicial complex, whereas the one in
Figure 5b is not a simplicial complex.

(a) (b)

Figure 5: (a) A simplicial complex. (b) Not a simplicial complex

Definition 2.4 j-skeleton of K, denoted as K (j) , is the collection {σ ∈ K|dim (σ) ≤ j}.
From the definition we know 0-skeleton is the set of vertices, 1-skeleton is the set of vertices and edges,
2-skeleton is the set of vertices, edges and triangles and so on.

Definition 2.5 A subcomplex of K is a subset K 0 ⊆ K which itself is still a simplicial complex.

Topological spaces studied in previous lectures are continuous. However, from the above discussion we
can see simplical complex is discrete. The underlying space |K| of K, which is defined as |K| = {x ∈
σ|∀σ ∈ K}, associates the discrete simplical complex with continuous topological space. Two simplicial
complices are equivalent if their underlying space are homeomorphic.
The star of a 0-simplex v ∈ K is defined as the set of all simplices having v as a face, denoted as St(v) =
{σ ∈ K|v ∈ σ}. Notice that v is a face of itself, so v ∈ St(v). The closed star (or closure) of v, St(v), is
the smallest subcomplex of K containing St(v). The link of v, Lk(v), is defined as Lk(v) = St(v) − St(v).
St(v) can be considered as a open neighborhood of v in topological space, then St(v) corresponds to the
concept of closed neighborhood and Lk(v) is the boundary of St(v). Figure 6 show the star, closed star and
link of a vertex. Notice that the concepts of star, closed star and link for a 0-simplex are just special cases
of a set of d-simplices. Please refer to [1] for their definitions.

Definition 2.6 An abstract simplicial complex is a finite collection of sets K such that if a set σ ∈ K, then
for any subset σ 0 ⊆ σ, σ 0 ∈ K.

3
 (a) (b)

(c) (d)

Figure 6: (a) A vertex v. (b) St(v). (c) St(v). (d) Lk(v).

Loosely speaking, abstract simplicial complex is a simplicial complex without the associated geometric
information. It it pure combinatorial. With embedded geometry, an abstract simplicial complex K 0 becomes
a geometric simplicial complex K, and such K is called a geometric realization of K 0 . K can be embedded
in Euclidean space. The following theorem tells us abstract simplicial complex does not does not mess up
geometric information.

Theorem 2.7 Any abstrct d-dimensional simplicial complex has a geometric realization in Euclidean space
IR2d+1 .
Proof:
Let K be a d-dimensional abstract simplicial complex, f be an injection f : K → IR2d+1 . We need
to prove f (K) is a geometric realization of K. Obviously, f preserves the topological structure of K, i.e.,
if a simplex σ ∈ K and τ ∈ σ, then f (τ ) ∈ f (σ) ∈ f (K). We only need to show there is no improper
intersection in f (K).
Let σ0 and σ1 be two simplices in K with a0 = dim (σ0 ), a1 = dim (σ1 ). We have cardinality of union
of the two simplices is card (σ0 ∪ σ1 ) = card (σ0 ) + card (σ1 ) ≤ a0 + 1 + a1 + 1 ≤ 2d + 2. This means
points in f (σ0 ∪ σ1 ) are geometrically independent. Then any convex combination of points in f (σ0 ∪ σ1 )
has a unique barycentric coordinate.
Consider f is injective, we have f (σ0 ) ∩ f (σ1 ) = f (σ0 ∩ σ1 ). If f (σ0 ) ∩ f (σ1 ) 6= ∅, then any
convex combination x ∈ f (σ0 ) ∩ f (σ1 ) iff x is a convex combination of f (σ0 ∩ σ1 ). That is to say,
CH(f (σ0 ) ∩ f (σ1 )) = CH(f (σ0 ∩ σ1 )). We already know CH(f (σ0 ∩ σ1 )) is a simplex, so the intersection
of f (σ0 ) and f (σ1 ) is either empty or a simplex. This proves there is no improper intersection in f (K).
In sum, f (K) is a geometric realization of K.
By this theorem, we know a Klein bottle can be embedded in IR5 . Actually, it can be embedded in IR4 ,
so the bound is not tight.

2.3 Push operation

We already know deformation retraction does not change topological structure (homotopy type) while trans-
forming one topological space to another. There is a similar process for simplicial complex.
Given a simplicial complex K, a simplex σ ∈ K is free if σ ∈ ∂K. Push free faces of σ towards its
non-free faces, under certain conditions, is essentially a deformation retraction.

4
Definition 2.8 Push operation for a d-dimensional simplicial complex continuously deforms the set of free
faces of a simplex onto the set of its non-free faces, if both sets are homeomorphic to Bd−1 .
Push operation forms a deformation retraction of the input simplex. Performing a sequence of push
operations to the input simplicial complex does not change its homotopy type, and can be used to somewhat
“simplify” a simplicial complex.

References
[1] H. Edelsbrunner and J. Harer. Computational topology: an introduction. 2009.