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.

simplices2

tetrahedron1

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.

scexample
scnonexample1

(more…)

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 73 other followers