


1. Simplicial Complexes 

A
finite
simplicial
complex
can
be
created in HAP by specifying its
maximal simplices. For instance, the following commmands construct the
simplicial projective plane and then calculate its integral homologies from the associated cellular chain complex. 

gap>
L:=[[1,2,6],[2,6,9],[2,3,9],[3,8,9],[3,4,8],[4,5,8], > [5,6,9],[5,9,10],[8,9,10],[7,8,10],[5,7,8],[5,6,7], > [4,5,10],[3,4,10],[3,7,10],[2,3,7],[2,6,7],[1,2,6]];; gap> P:=MaximalSimplicesToSimplicialComplex(L); Simplicial complex of dimension 2. gap> C:=ChainComplex(P); Chain complex of length 2 in characteristic 0 . gap> Homology(C,0); [ 0 ] gap> Homology(C,1); [ 2 ] gap> Homology(C,2); [ ] 

The
following commands compute the lowdimensional integral homologies of a
10dimensional simplicial sphere. 

gap>
n:=10;; gap> S:=MaximalSimplicesToSimplicialComplex(Combinations([0..n+1],n+1)); Simplicial complex of dimension 10. gap> C:=ChainComplex(S); Chain complex of length 10 in characteristic 0 . gap> List([0..n],m>Homology(C,m)); [ [ 0 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ 0 ], [ ] ] 

The
simplicial complex arising as the order complex of the poset of
nontrivial elementary abelian psubgroups of a finite group G has been
studied by D. Quillen and others. The following commands contruct this
simplicial complex for the Sylow 2subgroup of the Mathieu group M_{12}
(with p=2), and then verify that in this case the simplicial complex is
contractible. 

gap>
Q:=QuillenComplex(SylowSubgroup(MathieuGroup(12),2),2); Simplicial complex of dimension 2. gap> C:=ChainComplex(Q); Chain complex of length 2 in characteristic 0 . gap> Homology(C,0); [ 0 ] gap> Homology(C,1); [ ] gap> Homology(C,2); [ ] 

2.
Pure
Cubical
Complexes


In
HAP we us the term pure cubical
complex to mean a subspace of
ddimensional Euclidian space arising as a union of finitely many
ddimensional unit cubes whose vertices have integral coordinates. A
pure cubical complex can be created by specifying a ddimensional array
of 0s and 1s. For instance, the following commands construct a
3dimensional cubical 2sphere and determine its homology in low
dimensions. 

gap>
a:=[[1,1,1],[1,1,1],[1,1,1]];; gap> b:=[[1,1,1],[1,0,1],[1,1,1]];; gap> c:=[[1,1,1],[1,1,1],[1,1,1]];; gap> array:=[a,b,c];; gap> S2:=PureCubicalComplex(array); Pure cubical complex of dimension 3. gap> C:=ChainComplex(S2); Chain complex of length 3 in characteristic 0 . gap> Homology(C,0); [ 0 ] gap> Homology(C,1); [ ] gap> Homology(C,2); [ 0 ] gap> Homology(C,3); [ ] 

There
is
a
functor N:
(Pure
Cubical
Complexes)
>
(Simplicial
Complexes)
that sends a pure cubical complex X to a simplicial complex NX of the same homotopy type. If X is ddimensional then we refer to the ddimensional cells in X as facets. The vertices of NX are the facets of X, and the dimensional simplices of NX are the subsets of this vertex set having a nontrivial common intersection. We refer to NX as the Cech complex of X. The following commands compute the Cech complex of the above cubical 2sphere and (again) determine the low dimensional homology of the 2sphere. 

gap>
NS2:=CechComplexOfPureCubicalComplex(S2); Simplicial complex of dimension 3. gap> C:=ChainComplex(NS2); Chain complex of length 3 in characteristic 0 . gap> Homology(C,0); [ 0 ] gap> Homology(C,1); [ ] gap> Homology(C,2); [ 0 ] gap> Homology(C,3); [ ] 

The
above cubical 2sphere S2 has twentysix 3cells. The following
commands
compute a homotopy retract with just six 3cells. 

gap>
R:=ContractedComplex(S2); Pure cubical complex of dimension 3. gap> C:=ChainComplex(S2);; gap> D:=ChainComplex(R);; gap> C!.dimension(3); 26 gap> D!.dimension(3); 6 

The
twosphere S2 and its homotopy retract R can be visualized using the
following commands. These commands invoke the Asymptote vector graphics
package. 

gap>
ViewPureCubicalComplex(S2); gap> ViewPureCubicalComplex(R); 

The
following command shows that the Cech complex of this smaller
3dimensional 2sphere is actually a 2dimensional simplicial complex. 

gap>
S:=CechComplexOfPureCubicalComplex(R); Simplicial complex of dimension 2. 

A
digital photograph can be represented as a 2dimensional pure cubical
complex. This is done by choosing an integer threshold and including a
2cell in the pure cubical complex for each pixel where the sum of the
three RGB values iis less than the threshold. The following commands use a threshold of 400 to represent the image as a pure cubical complex. The complex has 40949 2dimensional cells. 

gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); Pure cubical complex of dimension 2. gap> C:=ChainComplex(image); Chain complex of length 2 in characteristic 0 . gap> C!.dimension(0); 45664 gap> C!.dimension(1); 86630 gap> C!.dimension(2); 40949 

The
number of cells in the above cubical complex makes it difficult to
compute the homology of the associated cellular chain complex. One way
around the difficulty is to:


gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); Pure cubical complex of dimension 2. gap> R:=ContractedComplex(image); Pure cubical complex of dimension 2. gap> S:=ContractibleSubcomplexOfPureCubicalComplex(R); Pure cubical complex of dimension 2. gap> C:=ChainComplexOfPair(R,S); Chain complex of length 2 in characteristic 0 . gap> Homology(C,0); [ 0, 0 ] gap> Homology(C,1); [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 

3. Cubical Complexes 

We
us the term cubcial complex
to mean any cellular subcomplex of a pure cubcial complex. This
slightly more general notion allows us to work with smaller homotopy
retracts when making homology computations. The following commands produce a pure cubical homotopy retract R, and then a cubcial retract K, of the above black and white image. Considered as CWcomplexes, R involves a total of 16975 cells while K involves a total of 7005 cells 

gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); Pure cubical complex of dimension 2. gap> R:=ContractedComplex(image); Pure cubical complex of dimension 2. gap> K:=PureCubicalComplexToCubicalComplex(R); Cubical complex of dimension 2. gap> Size(K); 16975 gap> ContractCubicalComplex(K); gap> Size(K); 7005 

By
working with arbitrary (nonregular) CWcomplexes we can further reduce
the number of cells in the cubical complex K. The following
commands use an algorithm, based on the notion of a discrete vector
field, to find a CWcomplex L of the homotopy type of K but
involving a total of just 25 cells. (Since H_{0}(K) = Z^{3}
and H^{1}(K) = Z^{20} this is close to the minimum
possible number of cells in any CWcomplex having the homotopy type of
K.) 

gap>
L:=DVFReducedCubicalComplex(K); Nonregular cubical complex of dimension 2 with discrete vector field. gap> Size(L); 25 gap> C:=ChainComplex(L); Chain complex of length 2 in characteristic 0 . gap> Homology(C,0); [ 0, 0, 0 ] gap> Homology(C,1); [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 

4. Permutahedral Complexes 

Euclidean
nspace
can
be
tessellated
by
regular ndimensional permutahedra. By a pure permutahedral complex we mean
a union of finitely many of the permutahedra in this tessellation.
Using the HAPPermutahedral package written by Fintan Hegarty we can
represent the above black an white image as a pure permutahedral
complex P. Although we are not guaranteed that the homotopy type of the
pure permutahedral complex P is identical to that of the above pure
cubcial complex representing the image, though we would hope that the
homotopy types of the two complexes are not too dissimilar. The following commands construct a homotopy retract of P, and then construct the Cech complex NP (which is defined as in the case of pure cubical complexes). An advantage of pure permutahedral complexes over pure cubical complexes is that a pure permutahedral complex of dimension n has Cech complex of the same dimension. 

gap>
P:=PurePermutahedralComplex(image!.binaryArray); Pure Permutahedral Complex of dimension 2. gap> ContractPurePermutahedralComplex(P); gap> NP:=PureComplexToSimplicialComplex(P,5); Simplicial complex of dimension 2. gap> Homology(D,0); [ 0, 0, 0 ] gap> Homology(NP,1); [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 

By
contrast, the Cech complex of the pure cubical representation of the
black and white image is a simplicial complex of dimension
3. 

5. Regular CWcomplexes 

Simplicial,
cubical
and
permutahedral
complexes
are
all examples of regular
CWspaces. Since some homotopical algorithms are best implemented in
the general setting of regular CWspaces the HAP package proides a data
type for this general setting. The following example creates a 4dimensional pure cubical complex T representing a standard torus. It then computes the Cech complex NT which is a 15dimensional simplicial complex. It then converts the data type of NT into that of a regular CWsomplex. This CWcomplex Y involves a total of 1172776 cells. 

gap>
Circle:=PureCubicalComplex([[1,1,1,1,1],[1,1,0,1,1],[1,1,1,1,1]]); Pure cubical complex of dimension 2. gap> T:=DirectProductOfPureCubicalComplexes(Circle,Circle); Pure cubical complex of dimension 4. gap> NT:=CechComplexOfPureCubicalComplex(T); Simplicial complex of dimension 15. gap> Y:=SimplicialComplexToRegularCWSpace(NT); Regular CWspace of dimension 15 gap> Size(Y); 1172776 

The
15dimensional CWspace Y has 1172776 cells. However, we know from its
construction that it has the homotopy type of a torus. The following
commands compute a set of "critical cells" for Y which can be used to
build a smaller nonregular CWcomplex of the same homotopy type. The
computation shows that there is a CWcomplex of the same homotopy type
involving just one 0cell, two 1cells and one 2cell. 

gap>
CriticalCellsOfRegularCWSpace(Y); [ [ 2, 5872 ], [ 1, 1116 ], [ 1, 2017 ], [ 0, 196 ] ] 

The
following command computes the chain complex of the space whose cells
correspond to the critical cells of Y. 

gap>
C:=ChainComplex(Y);; gap> List([0..15],C!.dimension); [ 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 

6. Homotopy Equivalent Pure Cubical
Complexes 

It
often happens that, for a given pure cubical complex X, any pure
cubical homotopy retract R of X is necessarily quite large. Smaller
homotopy equivalent pure cubical complexes ZR can often be obtained by
allowing zigzag sequences of homotopy retracts. X > Y1 < Y2
> Y3 < Y4 > ... < ZR
To illustrate the benefit of this approach we consisder the suspension S of the above black and white image. The pure complex S has 182727 facets. Our algorithm for finding a homotopy retract of S produces a homotopy retract R with 29809 facets. Our algorithm for finding a zigzag homotopy equivalent complex produces a homotopy equivalent pure cubcial complex ZR with just 304 facets. Finally, we produce the cellular chain complex of a nonregular CWcomplex V of the homotopy type of S. The CWcomplex V has one 0cell, two 1cells and twenty 2cells. This is the minimum possible number of cells for any CWcomplex of the homotopy type of S. 

gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); gap> X:=SuspensionOfPureCubicalComplex(image); Pure cubical complex of dimension 3. gap> Size(X); 182727 gap> R:=ContractedComplex(X); Pure cubical complex of dimension 3. gap> Size(R); 29809 gap> ZR:=ZigZagContractedPureCubicalComplex(S); Pure cubical complex of dimension 3. gap> Size(ZR); 304 gap> V:=DVFReducedCubicalComplex(PureCubicalComplexToCubicalComplex(ZR)); Nonregular cubical complex of dimension 3 with discrete vector field. gap> C:=ChainComplex(V); Chain complex of length 3 in characteristic 0 . gap> C!.dimension(0); 1 gap> C!.dimension(1); 2 gap> C!.dimension(2); 20 gap> C!.dimension(3); 0 

