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