Abstract simplicial complex

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. [cite book
author = Korte, Bernard; Lovász, László; Schrader, Rainer
year = 1991
title = Greedoids
publisher = Springer-Verlag
id = ISBN 3-540-18190-3
pages = 19–43]

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" ∈ "K", ∀ "Y" ⊂ "X", "Y" ∈ "K"

The elements of "K" are called faces or simplices of the complex, so the line above states that any subset ("Y") of a simplex ("X") is itself a simplex of the complex ("K"). The dimension of a simplex "X" ∈ "K" is defined as dim("X") = |"X"| − 1. Consequently one can define dim("K") to be 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".

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 $mathcal\{K\}$ 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 $mathcal\{K\}$ to the category of topological spaces as follows. For any simplex "X" ∈ "K" of dimension "n", let "F"("X") = Δ^"n" 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 Δ^"n", 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 Δ^"n". Define "F"("Y") → "F"("X") to be the unique affine linear embedding of Δ^"m" as that distinguished face of Δ^"n", 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

:$coprod\_\{X\; in\; K\}\{F(X)\}$

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 Δ^"n".

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.

ee also

* Kruskal-Katona theorem

References