Computing connectedness of simplicial complexes

Every programmer is familiar with the concept of a graph. A graph can be thought of a set of vertices -- 0-dimensional simplices, and edges -- 1-dimensional simplices. If we keep going, a 2-dimensional simplex is a triangle, a 3-dimensional simplex is a pyramid, and so on, and we obtain a generalization of a graph known as a simplicial set.

Here are some simplices represented as arrays in Factor:

{ 0 }
{ 1 2 }
{ 1 2 3 }

We can consider "simplicial chains modulo 2". These are sets of simplices, with an "addition" operation defined as the set symmetric difference.

S{ { 1 } { 2 } } S{ { 2 } { 3 } } symmetric-diff .
S{ { 1 } { 3 } }

Given a simplex, such as { 1 2 3 }, we can compute its boundary by forming a chain of simplices of one lower dimension, simply by removing successive vertices from our simplex. For example,

{ 1 2 3 } (boundary) .
S{ { 1 2 } { 2 3 } { 1 3 } }

The boundary of a simplex is a simplicial chain. We can compute the boundary of a chain simply by computing the boundary of each simplex it contains, and then taking the sum.

S{ { 1 2 } { 2 3 } } boundary .
S{ { 1 } { 3 } }

We note that the boundary of a boundary is always the zero chain:

S{ { 1 2 3 } } boundary boundary .
S{ }

We call a chain a "cycle" if its boundary is the zero chain. Thus the boundaries are a subset of the cycles. The cycles which are not boundaries correspond to enclosed regions in the simplicial set which are not "filled in", since no higher-dimensional simplex has this region as its boundary.

Here is a more involved example. Here is a simplicial set which can be visualized as a hollow pyramid:

{
    { { 1 } { 2 } { 3 } { 4 } }
    { { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 } }
    { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } }
}

This set consists of four points, six line segments, and four faces. There are no simplices of higher dimension.

Intuitively, the four faces "enclose" a missing section in the middle, so we would like to say this space has one two-dimensional hole. On the other hand, there are no 1-dimensional holes, since any 1-cycle -- that is, any set of line segments whose boundary is empty -- forms the boundary of one or more faces of the pyramid, and thus the 1-dimensional space there is "filled in".

The notion of a homology module (or homology group) formalizes this notion in mathematics. The example presented above is the special case of simplicial homology modulo 2. Given a simplicial complex, we can compute a series of homology modules, indexed by positive integers, where each module has a "dimension". The dimension of the nth homology module is the number of n-dimensional holes in the simplicial complex.

I wrote a Factor program for computing homology. The algorithm is very naive, and will blow up with more than a dozen points or so. Later on I will make it much more efficient.

Here is the output, which computes homology of some small spaces:

0-dimensional holes correspond to connected components.
A path connected space has exactly one component (0-dimensional hole).
A 1-connected space is path connected and has no holes of dimension 1.
A contractible space is path connected, and has no holes of dimension 1 and higher.


==== One-point space - contractable:
 --> { { { 1 } } }
0-dimensional holes: 1


==== Two-point space (0-sphere) - not path connected, so not contractible:
 --> { { { 1 } { 2 } } }
0-dimensional holes: 2


==== Unit interval (1-disc) - contractible:
 --> { { { 1 } { 2 } } { { 1 2 } } }
0-dimensional holes: 1
1-dimensional holes: 0


==== 1-sphere - not 1-connected, so not contractible:
 --> { { { 1 } { 2 } { 3 } } { { 1 2 } { 2 3 } { 1 3 } } }
0-dimensional holes: 1
1-dimensional holes: 1


==== 1-disc - contractible:
 --> { 
    { { 1 } { 2 } { 3 } } { { 1 2 } { 1 2 } { 1 3 } } { 
        { 1 2 3 }
    }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 0


==== 2-sphere - 1-connected but not contractible:
 --> { 
    { { 1 } { 2 } { 3 } { 4 } } { 
        { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 }
    } { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 1


==== 2-disc - contractible:
 --> { 
    { { 1 } { 2 } { 3 } { 4 } } { 
        { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 }
    } { { 1 2 3 } { 1 2 4 } { 2 3 4 } { 1 3 4 } } { { 1 2 3 4 } 
    }
}
0-dimensional holes: 1
1-dimensional holes: 0
2-dimensional holes: 0
3-dimensional holes: 0