Abstract simplicial complex


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"0, 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"0 → ∪"L"0, 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"0 < "e"1 < ... < "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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Simplicial complex — In mathematics, a simplicial complex is a topological space of a particular kind, constructed by gluing together points, line segments, triangles, and their n dimensional counterparts (see illustration). Simplicial complexes should not be… …   Wikipedia

  • Simplicial homology — In mathematics, in the area of algebraic topology, simplicial homology is a theory with a finitary definition, and is probably the most tangible variant of homology theory. Simplicial homology concerns topological spaces whose building blocks are …   Wikipedia

  • Clique complex — “Whitney complex” redirects here. For the Mississippi sports facility, see Davey Whitney Complex. Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that… …   Wikipedia

  • Vietoris–Rips complex — In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is an abstract simplicial complex that can be defined from any metric space M and distance delta; by forming a simplex for every finite set of points that… …   Wikipedia

  • Chain complex — Bicomplex redirects here. For the number, see Bicomplex number In mathematics, chain complex and cochain complex are constructs originally used in the field of algebraic topology. They are algebraic means of representing the relationships between …   Wikipedia

  • CW complex — In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still… …   Wikipedia

  • Orbifold — This terminology should not be blamed on me. It was obtained by a democratic process in my course of 1976 77. An orbifold is something with many folds; unfortunately, the word “manifold” already has a different definition. I tried “foldamani”,… …   Wikipedia

  • Simplex — For other uses, see Simplex (disambiguation). A regular 3 simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n… …   Wikipedia

  • Building (mathematics) — In mathematics, a building (also Tits building, Bruhat–Tits building) is a combinatorial and geometric structure which simultaneously generalizes certain aspects of flag manifolds, finite projective planes, and Riemannian symmetric spaces.… …   Wikipedia

  • Nerve of a covering — In mathematics, the nerve of an open covering is a construction in topology, of an abstract simplicial complex from an open covering of a topological space X. The notion of nerve was introduced by Pavel Alexandrov.[1] Given an index set I, and… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.