Go backward to 6 RealizabilityGo up to Main PageGo forward to References |
XHTML 1.0 |

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 [66]; for topological concepts
like *homology* we refer to Munkres' book [48].

A *finite abstract simplicial complex* *Δ* is a non-empty
set of subsets (the *simplices* or *faces*) of a finite set
of *vertices* such that *F ∈ Δ* and *G ⊂ F* imply
*G ∈ Δ*. The *dimension* of a simplex *F ∈ Δ* is
*| F |-1*. The *dimension* *dim(Δ)* of *Δ* is the
largest dimension of any of the simplices in *Δ*. If all its
maximal simplices with respect to inclusion (i.e., its *facets*)
have the same cardinality, then *Δ* 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 *Δ*
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.

- 32 Euler Characteristic
- 33
*f*-Vector of Simplicial Complexes - 34 Homology
- 35 Shellability
- 36 Partitionability

Why are some symbols not displayed correctly? |