Abstract simplicial complex

From Wikipedia, the free encyclopedia

In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets. In the context of matroids and greedoids, abstract simplicial complexes are also called independence systems.^[1]

Contents 1 Definition and example 2 Geometric realization 3 Examples 4 See also 5 References

[edit] Definition and example

Given a universal set S, and a family K of finite nonempty subsets of S (that is, K is a subset of the power set of S; a hypergraph), K is an abstract simplicial complex if the following is true:

∀ X ⊆ S, if X ∈ K, then ∀ Y ⊂ X it follows that Y ∈ K.

The elements of K are called faces or simplices of the complex. Furthermore, for X ∈ K, the dimension is defined to be dim(X) = |X| − 1, and consequently define dim(K) = max{dim(X), X ∈ K}. Note that the dimension of K might be infinite.

A subcomplex of K is a simplicial complex L such that every face of L is a face of K. A subcomplex that consists of all nonempty subsets of a face is often called a simplex of K (and many authors use the term "simplex" for both a face and a subcomplex).

An abstract simplicial complex is pure if every maximal face has the same dimension. In other words, dim(K) is finite and every face is contained in a face whose dimension equals dim('K).

One-dimensional simplicial complexes are (simple) graphs.

The subcomplex of K defined by

K^(d) = {X ∈ K, dim(X) ≤ d}

is the d-skeleton of K. In particular, the 1-skeleton is called the underlying graph. The union of all 0-dimensional simplices, ∪K⁰, is called the vertex set of K.

K is said to be a finite simplicial complex if K is a finite family of sets. This is easily seen to be equivalent to requiring that the underlying vertex set be finite.

A simplicial map f: K → L is a function between the underlying sets, ∪K⁰ → ∪L⁰, such that for any X ∈ K the image set f(X) is a face of L.

[edit] Geometric realization

We can associate to an abstract simplicial complex K a topological space |K|, called its geometric realization, which is a simplicial complex. The construction goes as follows.

First let denote the category whose objects are the simplices in K and whose morphisms are inclusions. Next choose a total order on the underlying vertex set of K and define a functor F from to the category of topological spaces as follows. For any simplex X ∈ K of dimension n, let F(X) = Δⁿ be the standard n-simplex. The partial order on the underlying vertex set of K then specifies a unique bijection between the elements of X and vertices of Δⁿ, ordered in the usual way e₀ < e₁ < ... < e_n. If Y ⊂ X is a subsimplex of dimension m < n, then this bijection specifies a unique m-dimensional face of Δⁿ. Define F(Y) → F(X) to be the unique affine linear embedding of Δ^m as that distinguished face of Δⁿ, such that the map on vertices is order preserving.

We can then define the geometric realization |K| as the colimit of the functor F. More specifically |K| is the quotient space of the disjoint union

by the equivalence relation which identifies a point y ∈ F(Y) with its image under the map F(Y) → F(X), for every inclusion Y ⊂ X.

If K is a finite simplicial complex, then we can describe |K| more simply. Choose an embedding of the underlying vertex set of K as an affinely independent subset of some Euclidean space R^N of sufficiently high dimension N. Then any abstract simplex X ∈ K can be identified with the geometric simplex in R^N spanned by the corresponding embedded vertices. Take |K| to be the union of all such simplices.

If K is the standard combinatorial n-simplex, then clearly |K| can be naturally identified with Δⁿ.

[edit] Examples

• As an example, let V be a finite subset of S of cardinality n+1 and let K be the power set of V. Then K is called a combinatorial n-simplex with vertex set V. If V = S = {0, 1, 2, ..., n}, K is called the standard combinatorial n-simplex.

• In the theory of partially ordered sets ("posets"), the order complex of a poset is the set of all finite chains. Its homology groups and other topological invariants contain important information about the poset. The order complex of a poset is pure if and only if the poset is graded.

• The Vietoris–Rips complex is defined from any metric space M and distance δ by forming a simplex for every finite subset of M with diameter at most δ. It has applications in homology theory, hyperbolic groups, image processing, and mobile ad-hoc networking.

[edit] See also

• Kruskal-Katona theorem

[edit] References