# tcs math – some mathematics of theoretical computer science

## December 19, 2008

### Lecture 8a. A primer on simplicial complexes and collapsibility

Filed under: CSE 599S, lecture, Math — Tags: , , — James Lee @ 3:17 am

Before we can apply more advanced fixed point theorems to the Evasiveness Conjecture, we need a little background on simplicial complexes, and everything starts with simplices.

### Simplices

It’s most intuitive to start with the geometric viewpoint, in which case an $n$-simplex is defined to be the convex hull of $n+1$ affinely independent points in $\mathbb R^n$.  These points are called the vertices of the simplex.  Here are examples for $n=0,1,2,3.$

A simplicial complex is then a collection of simplices glued together along lower-dimensional simplices.  More formally, if $S \subseteq \mathbb R^n$ is a (geometric) simplex, then a face of $S$ is a subset $F \subseteq S$ formed by taking the convex hull of a subset of the vertices of $S$.

Finally, a (geometric) simplicial complex is a collection $\mathcal K$ of simplices such that

1. If $S \in \mathcal K$ and $F$ is a face of $S$, then $F \in \mathcal K$, and
2. If $S,S' \in \mathcal K$ and $S \cap S' \neq \emptyset$, then $S \cap S'$ is a face of both $S$ and $S'$.

Property (1) gives us downward closure, and property (2) specifies how simplices can be glued together (only along faces).  For instance, the first picture depicts a simplicial complex.  The second does not.