In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex

Simplicial complex

In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...

, consisting of a family of finite sets closed under the operation of taking subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s. In the context of matroid

Matroid

In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....

s and greedoid

Greedoid

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms...

s, abstract simplicial complexes are also called independence systems.

Definitions

A nonempty family

Family of sets

In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets...

 Δ of finite subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of a universal set

Universal set

In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, the conception of a set of all sets leads to a paradox...

 S is an abstract simplicial complex if, for every set X in Δ, and every subset Y ⊂ X, Y also belongs to Δ. Equivalently, it is an abstract simplicial complex if and only if there do not exist two sets Y ⊂ X such that X belongs to Δ but Y does not.

Note that the empty set

Empty set

In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

 belongs to every non-empty abstract simplicial complex, because it is a subset of every other set X in the complex. 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

Simplicial complex

In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...

 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
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

We can associate to an abstract simplicial complex K a topological space |K|, called its geometric realization, which is a simplicial complex

Simplicial complex

In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...

. 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:
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

Final topology

In general topology and related areas of mathematics, the final topology on a set X, with respect to a family of functions into X, is the finest topology on X which makes those functions continuous.- Definition :Given a set X and a family of topological spaces Y_i with functionsf_i: Y_i \to Xthe...

. Now give |K| the subspace topology.

Alternatively, let denote the category

Category (mathematics)

In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...

 whose objects are the faces of K and whose morphism

Morphism

In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...

s are inclusions. Next choose a total order

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

 on the vertex set of K and define a functor F from to the category of topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

s as follows. For any face X ∈ K of dimension n, let F(X) = Δⁿ be the standard n-simplex. The order on the vertex set 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 face 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

Affine transformation

In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...

 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

Quotient space

In topology and related areas of mathematics, a quotient space is, intuitively speaking, the result of identifying or "gluing together" certain points of a given space. The points to be identified are specified by an equivalence relation...

 of the disjoint union

Disjoint union

In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a 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 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 R^N of sufficiently high dimension N. Then any face 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 Δⁿ.

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.

• The clique complex
  Clique complex
  Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.-Clique complex:...
  
   of an undirected graph has a simplex for each clique
  Clique
  A clique is an exclusive group of people who share common interests, views, purposes, patterns of behavior, or ethnicity. A clique as a reference group can be either normative or comparative. Membership in a clique is typically exclusive, and qualifications for membership may be social or...
  
   (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 set
  Partially ordered set
  In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
  
  s ("posets"), the order complex of a poset is the set of all finite chains. Its homology
  Homology (mathematics)
  In mathematics , homology is a certain general procedure to associate a sequence of abelian groups or modules with a given mathematical object such as a topological space or a group...
  
   groups and other topological invariants contain important information about the poset. The order complex of a poset is pure if and only if
  If and only if
  In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
  
   the poset is graded
  Graded poset
  In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...
  
  . The order complex is an example of a flag complex.

• The Vietoris–Rips complex
  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 δ by forming a simplex for every finite set of points that has diameter at most δ...
  
   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
  Homology theory
  In mathematics, homology theory is the axiomatic study of the intuitive geometric idea of homology of cycles on topological spaces. It can be broadly defined as the study of homology theories on topological spaces.-The general idea:...
  
  , hyperbolic group
  Hyperbolic group
  In group theory, a hyperbolic group, also known as a word hyperbolic group, Gromov hyperbolic group, negatively curved group is a finitely generated group equipped with a word metric satisfying certain properties characteristic of hyperbolic geometry. The notion of a hyperbolic group was introduced...
  
  s, image processing
  Image processing
  In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
  
  , and mobile ad-hoc networking. It is another example of a flag complex.

Enumeration

The number of abstract simplicial complexes on n elements is the nth Dedekind number

Dedekind number

Image:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right| The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively...

. These numbers grow very rapidly, and are known only for n ≤ 8; they are

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 .