Abstract simplicial complex

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A geometrical representation of an abstract simplicial complex that is not a valid 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 non-empty finite sets closed under the operation of taking non-empty subsets.[1] In the context of matroids and greedoids, abstract simplicial complexes are also called independence systems.[2]

Definitions[edit]

A family Δ of non-empty finite subsets of a universal set S is an abstract simplicial complex if, for every set X in Δ, and every non-empty subset Y ⊂ X, Y also belongs to Δ. Equivalently, it is an abstract simplicial complex if and only if there do not exist two non-empty finite sets Y ⊂ X such that X belongs to Δ but Y does not.

The finite sets that belong to Δ are called faces of the complex, and a face Y is said to belong to another face X if Y ⊂ X, so the definition of an abstract simplicial complex can be restated as saying that every face of a face of a complex Δ is itself a face of Δ. The vertex set of Δ is defined as V(Δ) = ∪Δ, the union of all faces of Δ. The elements of the vertex set are called the vertices of the complex. So for every vertex v of Δ, the set {v} is a face of the complex. The maximal faces of Δ (i.e., faces that are not subsets of any other faces) are called facets of the complex. The dimension of a face X in Δ is defined as dim(X) = |X| - 1: faces consisting of a single element are zero-dimensional, faces consisting of two elements are one-dimensional, etc. The dimension of the complex dim(Δ) is defined as the largest dimension of any of its faces, or infinity if there is no finite bound on the dimension of the faces.

The complex Δ is said to be finite if it has finitely many faces, or equivalently if its vertex set is finite. Also, Δ is said to be pure if it is finite-dimensional (but not necessarily finite) and every facet has the same dimension. In other words, Δ is pure if dim(Δ) is finite and every face is contained in a facet of dimension dim(Δ).

One-dimensional abstract simplicial complexes are mathematically equivalent to simple undirected graphs: the vertex set of the complex can be viewed as the vertex set of a graph, and the two-element facets of the complex correspond to undirected edges of a graph. In this view, one-element facets of a complex correspond to isolated vertices that do not have any incident edges.

A subcomplex of Δ is a simplicial complex L such that every face of L belongs to Δ; that is, L ⊂ Δ and L is a simplicial complex. A subcomplex that consists of all of the subsets of a single face of Δ is often called a simplex of Δ. (However, some authors use the term "simplex" for a face or, rather ambiguously, for both a face and the subcomplex associated with a face, by analogy with the non-abstract (geometric) simplicial complex terminology. To avoid ambiguity, we do not use in this article the term "simplex" for a face in the context of abstract complexes.)

The d-skeleton of Δ is the subcomplex of Δ consisting of all of the faces of Δ that have dimension at most d. In particular, the 1-skeleton is called the underlying graph of Δ. The 0-skeleton of Δ can be identified with its vertex set, although formally it is not quite the same thing (the vertex set is a single set of all of the vertices, while the 0-skeleton is a family of single-element sets).

The link of a face Y in Δ, often denoted Δ/Y or lkΔ(Y), is the subcomplex of Δ defined by

 \Delta/Y := \{ X\in \Delta \mid X\cap Y = \varnothing,\, X\cup Y \in \Delta \}.

Note that the link of the empty set is Δ itself.

Given two abstract simplicial complexes, Δ and Γ, a simplicial map is a function ƒ that maps the vertices of Δ to the vertices of Γ and that has the property that for any face X of Δ, the image set ƒ(X) is a face of Γ.

Geometric realization[edit]

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, define |K| as a subset of [0,1]^S consisting of functions t:S → [0,1] satisfying the two conditions:

\sum_{s\in S}t_s=1
\{s\in S:t_s>0\}\in\Delta

Now think of [0,1]^S as the direct limit of [0,1]^A where A ranges over finite subsets of S, and give [0,1]^S the induced topology. Now give |K| the subspace topology.

Alternatively, let \mathcal{K} denote the category whose objects are the faces of K and whose morphisms are inclusions. Next choose a total order on the vertex set of K and define a functor F from \mathcal{K} to the category of topological spaces as follows. For any face XK of dimension n, let F(X) = Δn be the standard n-simplex. The order on the vertex set then specifies a unique bijection between the elements of X and vertices of Δn, ordered in the usual way e0 < e1 < ... < en. If YX is a face 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 yF(Y) with its image under the map F(Y) → F(X), for every inclusion YX.

If K is finite, then we can describe |K| more simply. Choose an embedding of the vertex set of K as an affinely independent subset of some Euclidean space RN of sufficiently high dimension N. Then any face XK can be identified with the geometric simplex in RN 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[edit]

  • 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.
  • The clique complex of an undirected graph has a simplex for each clique (complete subgraph) of the given graph. Clique complexes form the prototypical example of flag complexes, complexes with the property that every set of elements that pairwise belong to simplexes of the complex is itself a 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.

Enumeration[edit]

The number of abstract simplicial complexes on n elements is one less than the nth Dedekind number. These numbers grow very rapidly, and are known only for n ≤ 8; they are (starting with n = 0):

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787 (sequence A014466 in OEIS).

See also[edit]

References[edit]

  1. ^ Lee, JM, Introduction to Topological Manifolds, Springer 2011, ISBN 1-4419-7939-5, p153
  2. ^ Korte, Bernhard; Lovász, László; Schrader, Rainer (1991). Greedoids. Springer-Verlag. p. 9. ISBN 3-540-18190-3.