This site contains: mathematics courses and book; covers: image analysis, data analysis, and discrete modelling; provides: image analysis software. Created and run by Peter Saveliev.

# Cell complex

## 1 Introduction

Cell complexes appear in real life, see Cells and cell complexes.

We have used cubical complexes as topological spaces made of simple pieces and, therefore, an appropriate subject for quantitative analysis, specifically, homology. These pieces are, in 2d, squares and segments on the grid.

Now, the best simplest complex we could use to represent a topological circle is four edges arranged in a square. But why should we need four pieces when we know that a circle is built from a single segment with the end-points glued together?

This last construction is very simple. Initially the (cubical) complex $K$ is:

Then we identify $A$ and $B \colon A \sim B$. The new complex $S$ is:

• $0$-cells: $A$;
• $1$-cells: $a$;
• boundary operator: $\partial a = 0$.

Certainly, this is not a cubical complex because we can't place these cells on the grid. However, the possibility of algebraic analysis remains since boundary operator can still be computed: $$\partial a = A + A = 0.$$

Further, the chain complex of $S$ is generated by $a$ and $A$:

• $C_0(S) = <A>$,
• $C_1(S) = <a>$,
• boundary operator: $\partial = 0 \colon C_1(S) \rightarrow C_0(S)$.

Then the homology $H_*(S)$ of $S$ is generated by the homology classes of $a$ and $A \colon [a], [A]$. Hence:

• $H_0(S) = {\bf Z}_2,$
• $H_1(S) = {\bf Z}_2.$

Observe now that the cells in a cubical complex are "open", i.e., homeomorphic to open balls, while the cells in a cell complex are "closed", i.e., homeomorphic to closed balls. The reason is that a cubical complex is built as a union of disjoint cells while the cells in a cell complex are glued to each other along their boundaries. A cubical complex can be interpreted as a cell complex in the obvious way.

Example. Let's consider how we build the cylinder from the square.

The complex $K$ of the square is:

• $0$-cells: $A, B, C, D$;
• $1$-cells: $a, b, c, d$;
• $2$-cells: $\tau$;
• boundary operator: $\partial \tau = a + b + c + d; \partial a = A + B, \partial b = B + C$, etc.

Recall, we create the cylinder $C$ by gluing two opposite edges with the following equivalence relation: $$(0,y) \sim (1,y).$$

Now, what about complexes? Can we interpret the gluing as equivalence of $a$ and $c$? Yes, but we also have to take care of the other cells as well:

• $a \sim c;$
• $A \sim D, B \sim C.$

Once again, this is not a cubical complex! However, the we still have our collection of cells (with some identified), only the boundary operator is different:

• $\partial \tau = a + b + c + d = a + b + a + d = b + d;$
• $\partial a = A + B, \partial b = B + C = 0, \partial c = A + B, \partial d = D + A = 0.$

Now, the chain complex of $K$ can be defined and its homology computed. The second line indicates that $b$ and $d$ are cycles and the first indicates that they are homologous. Hence $$H_1(C)= {\bf Z}_2.$$

Example. Suppose now that we want to build the Mobius band ${\bf M}^2$. The equivalence relation is given by $$(0,y) \sim (1,1-y).$$

Once again we can interpret the gluing as equivalence of $a$ and $c$. But this time they are attached to each other with $c$ upside down. It makes sense then to interpret this as an equivalence of cells but with a "twist": $$a \sim -c.$$ Here $-c$ represents edge $c$ with the opposite orientation. Further $$A \sim D, B \sim C.$$

The boundary operator is:

• $\partial \tau = a + b + c + d = a + b - a + d = b + d;$
• $\partial a = A + B, \partial b = B + C = 0, \partial c = A + B, \partial d = D + A = 0.$

Same as for the cylinder! Hence $$H_1({\bf M}) = {\bf Z}_2.$$

So, a cell complex is something built from cells via a quotient. This approach allows us to ignore the question of whether or not it fits into a Euclidean space.

How do we attach the cells to each other? Remember we want to be able to compute the boundary operator. Since the boundary of a $k$-cell is made of $(k-1)$-cells, we will only allow to attach $k$-cells to $(k-1)$-cells.

For example, suppose we already have a complex with two $0$-cells $A, B$ and a $1$-cell $a$. How can we add a new $1$-cell $b$ to $K$? First, we can't attach an end point of $b$ to the middle of $a$. This point can only be a $0$-cell that is already present in the complex.

Then, there are $4$ proper ways we can do that:

• from $A$ to $B$,
• from $A$ to $A$,
• from $B$ to $B$.

If we have a collection of cells of various dimensions, the general procedure of building a cell complex is:

1. start with $0$-cells,
2. attach the end points of $1$-cells to the $0$-cells,
3. attach the $2$-cells to the $1$-cells,
4. etc.

At the end of $n$-th step you have the $n$-th skeleton $K_n$ of $K$.

Example. Suppose these are the cells:

• $0$-cells: $A, B, C, D$;
• $1$-cells: $a, b, c$;
• $2$-cells: $\tau$.

One way to build a cell complex from these parts is this:

Now we can compute the boundary operator based on this procedure:

• $\partial \tau = a + b;$
• $\partial a = A + B, \partial b = A + B, \partial c = 0.$

Note: We can almost recover the whole complex from the boundary operator! The only ambiguity is that $c$ can be attached (this way) to any $0$-cell, not just $D$.

## 2 Definition and examples

The formal definition of a cell complex is inductive.

Definition. Suppose we have a finite collection of (abstract) cells $K$. Suppose $C_n$ denotes all $n$-cells in $K$. Next, the $0$-skeleton $K_0$ is defined as the disjoint union of $0$-cells: $$K_0 = \bigcup C_0.$$ Suppose that the $n$-skeleton $K_n$ has been constructed. Then the $(n+1)$-skeleton $K_{n+1}$ is constructed as follows. Suppose for each $(n+1)$-cell a there is a gluing map $$f_a \colon \partial a \rightarrow K_n.$$ Then all $(n+1)$-cells are "added" to $K_n$ resulting in the $(n+1)$-skeleton $K_{n+1}$ defined as the disjoint union of the $n$-skeleton $K_n$ and all the $(n+1)$-cells, under a certain equivalence relation: $$K_{n+1} = (K_n \bigcup C_{n+1})/ _{\sim},$$ where $\sim$ is defined by:

$x \sim f_a(x)$ for all $x \in \partial a$ and all $a \in C_{n+1}$.

The gluing maps have to satisfy an extra condition: $$f_a(\partial a) {\rm \hspace{3pt} is \hspace{3pt} the \hspace{3pt} union \hspace{3pt} of \hspace{3pt} a \hspace{3pt} collection \hspace{3pt} of \hspace{3pt} cells \hspace{3pt} of \hspace{3pt}} K.$$

Thus, cell complex $K$ is a combination of the cells, the skeleta, and the gluing maps.

Note that without the extra condition the result is called a CW complex. As you can see in the illustration, the results may differ (not homeomorphic). However, the spaces are "homotopy equivalent" and, therefore, the homology (as well as all other algebraic topological invariants) coincide. The point of this condition is to allow us to proceed directly to algebra. For example, if the (topological) boundary of an $(n+1)$-cell $\tau$ is identified with the union of $n$-cells $a, b, c$, then the (algebraic) boundary of $\tau$ is the sum of $a, b, c$: $$f_{\tau}(\partial \tau) = a \cup b \cup c \rightarrow \partial \tau = a + b + c.$$

Example. The image below illustrates the three steps of the construction of a cell complex with cells of dimension $0$ and $1$.

Example. Consider examples of building a $2$-skeleton from the same $1$-skeleton (on the right). Suppose these are the cells:

• $0$-cells: $A, B, C, D$;
• $1$-cells: $a, b, c$;
• $2$-cells: $\tau$.

We can define the gluing map for dimension $1$ based an the boundary operator:

• $\partial a = A + B$,
• $\partial b = B + C,$
• $\partial c = C + A.$

Indeed, suppose $a=[0,1]$. Then $f_a(0) = A$ and $f_a(1) = B$. Then $0 \sim A$ and $1 \sim B$. Similar for $b$ and $c$. The result is $K_1$.

Now suppose we are to attach $\tau$ to $K_1$.

Now we need to choose the gluing map for dimension $2$: $$f_{\tau} \colon \partial \tau \rightarrow K_1 {\rm \hspace{3pt} or \hspace{3pt}} f_{\tau} \colon {\bf S}^1 \rightarrow {\bf S}^1.$$

The choice of this map may be vary. The obvious choice is a homeomorphism.

Then $\tau$ is like a film of the frame made of $a, b,$ and $c$. The end result, the $2$-skeleton $K_2$, is homeomorphic to the disk.

What if the gluing map $f_{\tau} \colon {\bf S}^1 \rightarrow {\bf S}^1$ isn't a homeomorphism? The simplest choice is a constant map, for example: $$f_{\tau}(x) = A {\rm \hspace{3pt} for \hspace{3pt} all \hspace{3pt}} x \in \partial a.$$

Then $$x \sim A {\rm \hspace{3pt} for \hspace{3pt} all \hspace{3pt}} x \in \partial a,$$

i.e., the whole $\partial a$ is glued to $A$. Such gluing produces a sphere ${\bf S}^2$.

Exercise. Find other other possibilities for the gluing map $f_{\tau}(x)$ and sketch the resulting complexes.

For more examples, read Examples of cell complexes.

Theorem. $A$ finite (i.e., one with finitely many cells) is compact.

Proof. It is easy to see that a finite (disjoint) union of compact spaces is compact. So the initial union $X$ of the cells of the complex is compact. Now $K = X/ _{\sim}$, thence $K$ is compact as a quotient of a compact space (indeed, it's the image of a compact space under a continuous map). $\blacksquare$

## 3 Other types of complexes

Let's compare complexes to others.

Cell complexes:

Cells are homeomorphic to points, segments, disks, balls, ..., $n$-balls ${\bf B}^n$.

Cubical complexes:

Cells are vertices, edges, squares, cubes, ..., $n$-cubes ${\bf I}^n$ on a rectangular grid.

Simplicial complexes:

Cells are homeomorphic to points, segments, triangles, tetrahedra, ..., $n$-simplices.

Now we would like to define simplicial complexes as cell complexes whose cells are homeomorphic to simplices... It wouldn't make sense though to leave it this way because cells of any cell complex are homeomorphic to balls homeomorphic to simplices. We want the faces of simplices to be nicely attached to each other.

The problem with the second example here is that $\tau$ is glued to two faces of $\sigma$.

Definition. A cell complex $K$ is a simplicial complex if

• (1) each of its cells has the structure of a simplex, i.e., there is a homeomorphism to a geometric simplex;
• (2) the complex contains all faces of each simplex:

$$\tau \in K, \sigma < \tau \Rightarrow \sigma \in K,$$

• (3) two simplices can only share a single face:

$$\tau, \sigma \in K \Rightarrow \tau \cap \sigma < \tau.$$

Note: The last condition implies that a simplex can't be attached to itself (remember how the circle is created?).

Any cell complex can be turned into a simplicial complex. How? By subdivision, i.e., cutting the cells into smaller cells - triangles - until the above conditions are satisfied.

Sidenote: the procedure is reminiscent of the subdivision of intervals in the definition of the Riemann integral via Riemann sums.

Example. The simplest cell complex representation of the circle -- one $0$-cell and one $1$-cell -- is not a simplicial complex.

We add an extra vertex that cuts $a$ in two, but this still isn't a simplicial complex since $c$ and $d$ share two faces. For that we need another subdivision:

Representation of a cell complex or a topological space as a simplicial complex is called triangulation.

For a given space, its triangulation isn't unique. In particular, any further subdivision of the above simplicial complex will be a triangulation.

Example. The familiar representation of the cylinder isn't a triangulation simply because the $2$-cell is a square not triangle.

Cutting it in half diagonally doesn't make it a triangulation because a new $2$-cell $\alpha$ is glued to itself. Adding more edges does the job.

Exercise. Find a triangulation of the torus. Solution:

Exercise. Find a triangulation for each of the main surfaces.

Once all the cells are simplices, the triangulation can be found via the so-called barycentric subdivision: every simplex (of any dimensions) gets a new vertex inside and all possible faces are added as well.

For the $3$-simplex above, one:

1. keeps the $4$ original vertices,
2. adds $6$ new vertices on each edge,
3. adds $4$ new vertices on each face, and
4. adds $1$ new vertex inside.

Then one adds many new edges and faces.

Exercise. Find a triangulation for the cube.

Example: Let's do that for this $2$-cell, with the orientations of $1$-cells randomly assigned.

Then $$\partial \tau = -a_1 + a_2 + a_3 + a_4 - a_5 + a_6 + a_7 - a_8,$$

$$\begin{array}{l} \partial (\partial \tau) &= \partial( -a_1 + a_2 + a_3 + a_4 - a_5 + a_6 + a_7 - a_8 ) \\ &= -\partial a_1 + \partial a_2 + \partial a_3 + \partial a_4 - \partial a_5 + \partial a_6 + \partial a_7 - \partial a_8 \\ &= -(A_1 - A_2) + (A_3 - A_2) + (A_4 - A_3) + (A_5 - A_4) \\ & - (A_5 - A_6) + (A_7 - A_6) + (A_8 - A_7) - (A_8 - A_1) \\ &= 0. \end{array}$$

The pattern in clear.

Example:

In dimension $3$, there is only one $$3{\rm -cell} \colon \alpha = ABCDEFG$$ with the orientation given by this particular order of vertices. Next, $$2{\rm -cells} \colon \tau = ABCD, \sigma = BCFG, \lambda = CFED,$$ with the orientations indicated by the arrows just as in the above example. To compute the boundary of $\alpha$ we need to express its faces in terms of these $2$-cells, plus or minus. These faces are obtained by dropping one of the vertices from the list $ABCDEFG$: $$\begin{array}{l} \partial \alpha &= ABCD + BCFG + CDEF + 3 {\rm \hspace{3pt} more} \\ &= \tau + \sigma - \lambda + 3 {\rm \hspace{3pt} more}. \end{array}$$

Why the minus sign? Let's see how many transpositions it takes to turn $\lambda = CFED$ into $CDEF$. $$CFED \rightarrow CEFD \rightarrow CEDF \rightarrow CDEF.$$

Three. Since it's odd, $CDEF = - CFED = -λ$.

## 4 Overview

The spaces that we study will be made of elementary pieces with "trivial" topology.

As an example, a cubical complex has been understood as a collection of cubical cells on the grid ${\bf Z}^n$ so that the boundary operator is well defined.

Cubical complexes:

Simplicial complexes:

Now we use a more general approach as cells of all shapes are allowed. The approach is also a more abstract as we separate the complex from the space in which it resides. This allows us to make the structures purely combinatorial and, therefore, amenable to computation.

1. Cell complexes
2. Skeleton
3. Boundary operator

Alternatively, we can have no redundancy but only for "nice" spaces.

Suppose $Q_k,k=0,1,2,...,$ are finite. Then we proceed inductively.

The $0$-skeleton $K^{(0)}$ is defined as the disjoint union of $0$-cells, as points: $$K^{(0)} = Q_0.$$

Suppose that the $m$-skeleton $K^{(m)}$ has been constructed, as a topological space. Now the $(m+1)$-skeleton $K^{(m+1)}$ is constructed as follows.

Suppose for each $(m+1)$-cell $a$ there is a gluing map $$f_a \colon \partial a \rightarrow K^{(m)},$$ where $\partial a$ is the boundary of $a$ (homeomorphic to the sphere ${\bf S}^{m-1}$). Then all $(m+1)$-cells are "attached" to $K^{(m)}$ by means of these maps resulting in the $(m+1)$-skeleton $K^{(m+1)}$. More precisely, it is defined as the disjoint union of the $m$-skeleton $K^{(m)}$ and all the $(m+1)$-cells, under a certain equivalence relation: $$K^{(m+1)} = (K^{(m)} \cup Q_{m+1})/ _{\sim},$$ where $\sim$ is given by:

$x \sim f_a(x)$ if $x \in \partial a$, for $a \in Q_{m+1}$.

Our complex has now a topological counterpart, called its realization: $$|K|=\bigcup _m K^{(m)}=\bigcup _k \bigcup _{\sigma \in Q_k} \text{im } \sigma.$$ We still have our gluing maps: $$f_a \colon \partial a \rightarrow K,$$ The images of the cells under these maps can also be called cells.

The gluing maps have to satisfy this condition:

$f_a(\partial a)$ is the union of a collection of cells of $K$.

The topology of the cell complex is understood via the equivalence of the following three statements about a subset $A$:

• it is open/closed,
• its preimage under the gluing map is open/closed,
• its intersection with each cell is open/close in that cell.

Combinatorially, cell complex $K$ is the combination of

• the collection of cells $K=\bigcup _m Q_m$,
• the skeleta $\{K^{(0)},K^{(1)},..\}$, and
• the collection of the gluing maps $\{f_a \colon \partial a \rightarrow K^{(n)},a \in K\}$.

Another term commonly used is "CW-complex".

Transformations of the spaces given by cell complexes are captured by cell-to-cell maps.

Given two cell complexes $K$ and $L$ and a function between them $$f:K \rightarrow L,$$ we assume that the dimensions of cells can't go up: $$a\in Q_m, f(a)\in Q_k \Rightarrow m \ge k,$$ and that the boundaries are preserved $$b\in \partial a \Rightarrow f(b) \in \partial f(a).$$ Then we call $f$ a cell map.

The last requirement is a discrete/combinatorial analogue of continuity.

Note: Recall that a continuous function $g$ is called a cell map if $$g(K^{(m)}) \subset L^{(m)}.$$

In order to be able to study what is going on in our spaces, we have to circumvent the lack any algebraic structure.

Recall $R$ is a ring.

Next, $k$-chains are formal linear combinations of $k$-cells with coefficients in $R$: $$C_k(K)=< Q_k(K) >=\left\{ \sum _i r_i a_i:r_i\in R,a_i\in Q_k(K) \right\}, k=0,1,....$$ It is a free module. It is given by its (commonly finite) basis, $Q_k(K)$.

The complete collection of chains is also a graded module, denoted by $$C(K)=\bigoplus _i C_i(K),$$ with basis $\cup Q_k(K)$. One can go back and forth between these two interpretations.

This module is equipped with boundary operators (denoted by the same letter $\partial$ as the boundary of a cell): $$\partial _k: C_k(K) \rightarrow C_{k-1}(K),k=0,1,....$$ One can think of it as a single, graded (of degree $-1$) operator: $$\partial =\bigoplus _k \partial _k: C(K) \rightarrow C(K).$$ One can go back and forth between these two interpretations.

When the chains come from a cell complex as above, then for every $k$-cell $a\in K$ any of its boundary $(k-1)$-cells $b\in \partial a$ is also in $K$. The sum of those is defined to be the boundary chain of this cell: $$\partial _k (a)=\sum _{b \in \partial a} b.$$

However, in general any sequence of linear operators that satisfy $$\partial _{k-1} \partial _k =0 : C_k(K) \rightarrow C_{k-2}(K)$$ can be used, below. Alternatively, we simply write $$\partial \partial =0.$$

The combination of these modules and linear operators $(C(K), \partial )$ is called the chain complex of $K$ over $R$.

Chain complexes may come from sources other than cell complexes. For example, all formal linear combinations of all singular cells in a topological space $X$: $$\sigma _k: {\bf B}^k \rightarrow X,$$ form one, the singular chain complex of $X$.

Note: The linear combinations can be taken over any ring $R$. However, the Universal Coefficient Theorem indicates that the homology over any ring can be derived from the one over the integers, but generally not vice versa. This suggests that the default choice should be $R={\bf Z}$.

Transformations of the spaces given by chain complexes are captured by linear operators.

If we extend a cell map $f:K\rightarrow L$ from the cells by linearity to the chains, the result is a chain operator, i.e., a linear map between chain complexes $$f \colon ( C(K), \partial ^K) \rightarrow (C(L), \partial ^L)$$ that preserves boundaries. In other words, it commutes with the boundary operator: $$f_{k-1} \partial_k^K = \partial_k^L f_k,$$ or simply: $$f \partial = \partial f .$$ This requirement is an algebraic analogue of continuity.

Consider the commutative diagram (the commutativity is given by this preservation of boundary condition): $$\newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\la}[1]{\!\!\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccccc} \da{\partial_3^K} & & \da{\partial_3^L} \\ C_2(K) & \ra{f_2} & C_2(L) \\ \da{\partial_2^K} & & \da{\partial_2^L} \\ C_{1}(K) & \ra{f_{1}} & C_{1}(L)\\ \da{\partial_1^K} & & \da{\partial_1^L} \\ C_{0}(K) & \ra{f_{0}} & C_{0}(L)\\ \da{\partial_0^K} & & \da{\partial_0^L} \\ 0& &0\\ \end{array}$$

Chain maps may come from sources other than cell maps. For example, a chain map $$g:Z\rightarrow Z$$ defined on the standard cubical complex $Z$ of the real line by $$g(\{0\})=\{0\},g(\{1\})=\{3\},$$ $$g([0,1])=[0,1]+[1,2]+[2,3],$$ may represent motion of an object from point $0$ to point $3$ over the period of time from $0$ to $1$. Further, any chain map $$g:Z\rightarrow C$$ to any chain complex $C$ is a parametric curve and $$g:Z\times Z \rightarrow C$$ is a parametric surface, etc.