This section is concerned with problems on finite abstract simplicial complexes. Some of the problems listed are direct generalizations of problems on polytopes. Most of the basic notions relevant in our context can be looked up in ; for topological concepts like homology we refer to Munkres' book .
A finite abstract simplicial complex D is a non-empty set of subsets (the simplices or faces) of a finite set of vertices such that F Î D and G Ì F imply G Î D. The dimension of a simplex F Î D is | F |-1. The dimension dim(D) of D is the largest dimension of any of the simplices in D. If all its maximal simplices with respect to inclusion (i.e., its facets) have the same cardinality, then D is pure. A pure d-dimensional finite abstract simplicial complex whose dual graph (defined on the facets, where two facets are adjacent if they share a common (d-1)-face) is connected is a pseudo-manifold if every (d-1)-dimensional simplex is contained in at most two facets. The boundary of a simplicial (d+1)-dimensional polytope induces a d-dimensional pseudo-manifold.
Throughout this section a finite abstract simplicial complex D is given by its list of facets or by the complete list of all simplices. In the first case, the input size can be measured by n and m, the numbers of vertices and facets.