Tutorial on GAP routines for handling the homology of simplicial complexes,
CW-complexes, and in general the nerves of categories.
December 14, 1999
Peter Webb
School of Mathematics
University of Minnesota
Minneapolis MN 55455
webb@math.umn.edu
http://www.math.umn.edu/~webb
The GAP code is available at: http://www.math.umn.edu/~webb/GAPfiles/categories
The routines run under version 4 of GAP.
The nerve of a category is the simplicial set in which the simplices in degree n
are the chains of morphisms a1,a2, ... , an in the category.
A simplex is said to be degenerate if one or more of the morphisms is the
identity. We may form the geometric realization of this simplicial set,
and it is a CW-complex whose cells biject with the non-degenerate simplices.
In case the category happens to be a partially-ordered set, we obtain exactly
the order complex of the poset. In this way, every simplicial complex is
obtained up to homeomorphism, since the barycentric subdivision of the
simplicial complex is order complex of the poset of simplices of the
simplicial complex. For example, a graph may be realized as the nerve of the
category whose objects are the vertices and the edges, and in which there is
a morphism from each edge to each of its end points, together
with the identity morphisms. (In the case of a loop
on a single vertex, there are two morphisms from the edge to the vertex.)
This formalism also encapsulates classifying spaces of groups. If we regard
a group G as a category with a single object, the nerve of this category is
the classifying space BG, whose homology is the group homology with trivial
coefficients.
The categories stored by GAP are concrete categories (i.e. each object
has the underlying structure of a set) in which each object is a set of
positive integers, disjoint from the integers which are the members of the
other objects. Each morphism in the category is represented as the list
of the values of the morphism on the elements of its domain object.
It's time for some examples:
gap> q8:=ConcreteCategory([[3,4,2,1,8,7,5,6],[5,6,7,8,2,1,4,3]]);
rec(
generators := [ [ 3, 4, 2, 1, 8, 7, 5, 6 ], [ 5, 6, 7, 8, 2, 1, 4, 3 ] ],
operations := rec(
) )
gap> circle:=ConcreteCategory([[2],[3],[,2,3]]);
rec(
generators := [ [ 2 ], [ 3 ], [ , 2, 3 ] ],
operations := rec(
) )
gap> sphere:=ConcreteCategory([[3],[4],[,3],[,4],[,,5],[,,6],[,,,5],[,,,6],
> [,,,,5],[,,,,,6]]);
rec(
generators := [ [ 3 ], [ 4 ], [ , 3 ], [ , 4 ], [ ,, 5 ], [ ,, 6 ],
[ ,,, 5 ], [ ,,, 6 ], [ ,,,, 5 ], [ ,,,,, 6 ] ],
operations := rec(
) )
The command
ConcreteCategory();
sets up a record for a the category generated by the list of morphisms in
. For each object in the category there must be at least one
generator morphism whose domain is that object (it can be the identity). At the
moment GAP has not computed anything about these categories.
gap> Objects(q8);
[ [ 1, 2, 3, 4, 5, 6, 7, 8 ] ]
gap> Objects(circle);
[ [ 1 ], [ 2, 3 ] ]
gap> Objects(sphere);
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ] ]
The first example is the quaternion group of order 8, regarded as a category
with a single object [ 1, 2, 3, 4, 5, 6, 7, 8 ]. The second example is
a category with two objects [ 1 ] and [ 2, 3 ] with two morphisms from the
first object to the second. The third example is a poset with 6 elements (the
objects of the category).
gap> Morphisms(q8);
[ [ [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], [ 2, 1, 4, 3, 6, 5, 8, 7 ],
[ 3, 4, 2, 1, 8, 7, 5, 6 ], [ 4, 3, 1, 2, 7, 8, 6, 5 ],
[ 5, 6, 7, 8, 2, 1, 4, 3 ], [ 6, 5, 8, 7, 1, 2, 3, 4 ],
[ 7, 8, 6, 5, 3, 4, 2, 1 ], [ 8, 7, 5, 6, 4, 3, 1, 2 ] ] ] ]
gap> Morphisms(circle);
[ [ [ [ 1 ] ], [ [ 2 ], [ 3 ] ] ], [ [ ], [ [ , 2, 3 ] ] ] ]
gap> Morphisms(sphere);
[ [ [ [ 1 ] ], [ ], [ [ 3 ] ], [ [ 4 ] ], [ [ 5 ] ], [ [ 6 ] ] ],
[ [ ], [ [ , 2 ] ], [ [ , 3 ] ], [ [ , 4 ] ], [ [ , 5 ] ], [ [ , 6 ] ] ],
[ [ ], [ ], [ [ ,, 3 ] ], [ ], [ [ ,, 5 ] ], [ [ ,, 6 ] ] ],
[ [ ], [ ], [ ], [ [ ,,, 4 ] ], [ [ ,,, 5 ] ], [ [ ,,, 6 ] ] ],
[ [ ], [ ], [ ], [ ], [ [ ,,,, 5 ] ], [ ] ],
[ [ ], [ ], [ ], [ ], [ ], [ [ ,,,,, 6 ] ] ] ]
The morphisms in the category are obtained as the set of all possible
composites of the generator morphisms, with the identity morphisms thrown in
as well. They are stored in an array
.morphisms in which the [i][j] entry is a list of all the morphisms
from object i to object j. Sometimes this list is empty.
gap> Homology(q8,0);Homology(q8,1);Homology(q8,2);
[ 0 ]
[ 2, 2 ]
[ ]
gap> Homology(circle,0);Homology(circle,1);Homology(circle,2);
[ 0 ]
[ 0 ]
[ ]
gap> Homology(sphere,0);Homology(sphere,1);Homology(sphere,2);
[ 0 ]
[ ]
[ 0 ]
Homology(,n) returns a list of the invariant factors of the dimension n
homology of the nerve of the category. The empty list [] means that the
homology is zero. Each entry 0 indicates an infinite cyclic factor.
The above calculation is done with the integral chain complex. We may also
work over the field with p elements.
gap> HomologyDimension(q8,0,2);HomologyDimension(q8,1,2);
1
2
gap> HomologyDimension(q8,2,2);
2
gap> HomologyDimension(q8,0,3);HomologyDimension(q8,1,3);
1
0
gap> HomologyDimension(circle,0,2);HomologyDimension(circle,1,2);
1
1
HomologyDimension(,n,p); returns the dimension of the homology
of the nerve of in dimension n over the field with p elements.
Another example (the dihedral group of order 8):
gap> d8:=ConcreteCategory([[2,3,4,1,8,5,6,7],[5,6,7,8,1,2,3,4]]);
rec(
generators := [ [ 2, 3, 4, 1, 8, 5, 6, 7 ], [ 5, 6, 7, 8, 1, 2, 3, 4 ] ],
operations := rec(
) )
gap> Homology(d8,0);Homology(d8,1);Homology(d8,2);
[ 0 ]
[ 2, 2 ]
[ 2 ]
gap> HomologyDimension(d8,0,2);HomologyDimension(d8,1,2);
1
2
gap> HomologyDimension(d8,2,2);
3
Yet another example (the real projective plane):
gap> projplane:=ConcreteCategory([[4],[6],[7],[9],[,4],[,5],[,8],[,9],
> [,,5],[,,6],[,,7],[,,8],[,,,11],[,,,13],[,,,,10],[,,,,13],
> [,,,,,12],[,,,,,13],[,,,,,,10],[,,,,,,11],[,,,,,,,11],[,,,,,,,12],
> [,,,,,,,,10],[,,,,,,,,12],
> [,,,,,,,,,10],[,,,,,,,,,,11],[,,,,,,,,,,,12],[,,,,,,,,,,,,13]]);
rec(
generators := [ [ 4 ], [ 6 ], [ 7 ], [ 9 ], [ , 4 ], [ , 5 ], [ , 8 ],
[ , 9 ], [ ,, 5 ], [ ,, 6 ], [ ,, 7 ], [ ,, 8 ], [ ,,, 11 ],
[ ,,, 13 ], [ ,,,, 10 ], [ ,,,, 13 ], [ ,,,,, 12 ], [ ,,,,, 13 ],
[ ,,,,,, 10 ], [ ,,,,,, 11 ], [ ,,,,,,, 11 ], [ ,,,,,,, 12 ],
[ ,,,,,,,, 10 ], [ ,,,,,,,, 12 ], [ ,,,,,,,,, 10 ], [ ,,,,,,,,,, 11 ],
[ ,,,,,,,,,,, 12 ], [ ,,,,,,,,,,,, 13 ] ],
operations := rec(
) )
gap> Homology(projplane,0);Homology(projplane,1);Homology(projplane,2);
[ 0 ]
[ 2 ]
[ ]
gap> HomologyDimension(projplane,0,2);HomologyDimension(projplane,1,2);
1
1
gap> HomologyDimension(projplane,2,2);
1
Limitations on the calculations:
With categories with non-identity endomorphisms of objects (e.g. non-identity
groups) the number of simplices in dimension n increases exponentially with
n, and this imposes a severe limitation on the homology groups which
can be computed. The package of routines includes an algorithm to take
advantage of the fact that the matrices of the boundary morphisms are
sparse, thus saving space and in principal, time. To find out about these
routines you have to look at the package, or ask me. The largest problem so far
on which this has been successfully used has a boundary morphism from
a space of rank about 125,000 to a space of rank about 4,000.
Please notify me of bugs!
Peter Webb
webb@math.umn.edu
December 14, 1999