Abstract simplicial complex

In combinatorics, an abstract simplicial complex (ASC) is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles (sets of size 3), their edges (sets of size 2), and their vertices (sets of size 1).
In the context of matroids and greedoids, abstract simplicial complexes are also called independence systems.
An abstract simplex can be studied algebraically by forming its Stanley–Reisner ring; this sets up a powerful relation between combinatorics and commutative algebra.
Definitions.
A collection of non-empty finite subsets of a set "S" is called a set-family.
A set-family is called an abstract simplicial complex if, for every set in , and every non-empty subset , the set also belongs to .
The finite sets that belong to are called faces of the complex, and a face is said to belong to another face if , 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 , the union of all faces of . The elements of the vertex set are called the vertices of the complex. For every vertex "v" of , the set {"v"} is a face of the complex, and every face of the complex is a finite subset of the vertex set.
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 in is defined as : faces consisting of a single element are zero-dimensional, faces consisting of two elements are one-dimensional, etc. The dimension of the complex 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 is finite and every face is contained in a facet of dimension .
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 an abstract simplicial complex "L" such that every face of "L" belongs to ; that is, and "L" is an abstract 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 in , often denoted or , 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 of , the image is a face of . There is a category SCpx with abstract simplicial complexes as objects and simplicial maps as morphisms. This is equivalent to a suitable category defined using non-abstract simplicial complexes.
Moreover, the categorical point of view allows us to tighten the relation between the underlying set "S" of an abstract simplicial complex and the vertex set of : for the purposes of defining a category of abstract simplicial complexes, the elements of "S" not lying in are irrelevant. More precisely, SCpx is equivalent to the category where:
Geometric realization.
We can associate to an abstract simplicial complex "K" a topological space formula_2, called its geometric realization, which is the carrier of a simplicial complex. The construction goes as follows.
First, define formula_2 as a subset of formula_4 consisting of functions formula_5 satisfying the two conditions:
Now think of the set of elements of formula_4 with finite support as the direct limit of formula_9 where "A" ranges over finite subsets of "S", and give that direct limit the induced topology. Now give formula_2 the subspace topology.
Alternatively, let formula_11 denote the category whose objects are the faces of and whose morphisms are inclusions. Next choose a total order on the vertex set of and define a functor "F" from formula_11 to the category of topological spaces as follows. For any face "X" in "K" of dimension "n", let be the standard "n"-simplex. The order on the vertex set then specifies a unique bijection between the elements of and vertices of , ordered in the usual way . If is a face of dimension , then this bijection specifies a unique "m"-dimensional face of . Define to be the unique affine linear embedding of as that distinguished face of , such that the map on vertices is order-preserving.
We can then define the geometric realization formula_2 as the colimit of the functor "F". More specifically formula_2 is the quotient space of the disjoint union
by the equivalence relation that identifies a point with its image under the map , for every inclusion .
If "K" is finite, then we can describe formula_2 more simply. Choose an embedding of the vertex set of "K" as an affinely independent subset of some Euclidean space formula_17 of sufficiently high dimension "N". Then any face "X" in "K" can be identified with the geometric simplex in formula_17 spanned by the corresponding embedded vertices. Take formula_2 to be the union of all such simplices.
If "K" is the standard combinatorial "n"-simplex, then formula_2 can be naturally identified with .
Examples.
1. Let "V" be a finite set of cardinality . The combinatorial "n"-simplex with vertex-set "V" is an ASC whose faces are all subsets of "V" (i.e., it is the power set of "V"). If then this ASC is called the standard combinatorial "n"-simplex.
2. Let "G" be an undirected graph. The clique complex of "G is an ASC whose faces are all cliques (complete subgraphs) of "G". The independence complex of "G is an ASC whose faces are all independent sets of "G" (it is the clique complex of the complement graph of G). Clique complexes are the prototypical example of flag complexes. A flag complex is a complex "K" with the property that every set of elements that pairwise belong to faces of "K" is itself a face of "K".
3. Let "H" be a hypergraph. A matching in "H" is a set of edges of "H", in which every two edges are disjoint. The matching complex of "H" is an ASC whose faces are all matchings in "H". It is the independence complex of the line graph of "H".
4. Let "P" be a partially ordered set (poset). The order complex of "P" is an ASC whose faces are all finite chains in "P". Its homology groups and other topological invariants contain important information about the poset "P".
5. Let "M" be a metric space and "δ" a real number. The Vietoris–Rips complex is an ASC whose faces are the finite subsets of "M" with diameter at most "δ". It has applications in homology theory, hyperbolic groups, image processing, and mobile ad hoc networking. It is another example of a flag complex.
6. Let formula_21 be a square-free monomial ideal in a polynomial ring formula_22 (that is, an ideal generated by products of subsets of variables). Then the exponent vectors of those square-free monomials of formula_23 that are not in formula_21 determine an abstract simplicial complex via the map formula_25. In fact, there is a bijection between (non-empty) abstract simplicial complexes on vertices and square-free monomial ideals in . If formula_26 is the square-free ideal corresponding to the simplicial complex formula_27 then the quotient formula_28 is known as the Stanley–Reisner ring of formula_29.
7. For any open covering "C" of a topological space, the nerve complex of "C" is an abstract simplicial complex containing the sub-families of "C" with a non-empty intersection.
Enumeration.
The number of abstract simplicial complexes on up to "n" labeled elements (that is on a set "S" of size "n") is one less than the "n"th Dedekind number. These numbers grow very rapidly, and are known only for ; the Dedekind numbers are (starting with "n" = 0):
The number of abstract simplicial complexes whose vertices are exactly "n" labeled elements is given by the sequence "1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966" , starting at "n" = 1. This corresponds to the number of antichain covers of a labeled "n"-set; there is a clear bijection between antichain covers of an "n"-set and simplicial complexes on "n" elements described in terms of their maximal faces.
The number of abstract simplicial complexes on exactly "n" unlabeled elements is given by the sequence "1, 2, 5, 20, 180, 16143" , starting at "n" = 1.
Relation to other concepts.
An abstract simplicial complex with an additional property called the augmentation property or the exchange property yields a matroid. The following expression shows the relations between the terms:
HYPERGRAPHS = SET-FAMILIES ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.