In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, 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.<ref name=Lee>Lee, John M., Introduction to Topological Manifolds, Springer 2011, Template:ISBN, p153</ref> 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.<ref>Template:Cite book</ref>
An abstract simplex can be studied algebraically by forming its Stanley–Reisner ring; this sets up a powerful relation between combinatorics and commutative algebra.
DefinitionsEdit
A collection Template:Math of non-empty finite subsets of a set S is called a set-family.
A set-family Template:Math is called an abstract simplicial complex if, for every set Template:Mvar in Template:Math, and every non-empty subset Template:Math, the set Template:Mvar also belongs to Template:Math.
The finite sets that belong to Template:Math are called faces of the complex, and a face Template:Mvar is said to belong to another face Template:Mvar if Template:Math, so the definition of an abstract simplicial complex can be restated as saying that every face of a face of a complex Template:Math is itself a face of Template:Math. The vertex set of Template:Math is defined as Template:Math, the union of all faces of Template:Math. The elements of the vertex set are called the vertices of the complex. For every vertex v of Template:Math, 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 Template:Math (i.e., faces that are not subsets of any other faces) are called facets of the complex. The dimension of a face Template:Mvar in Template:Math is defined as Template:Math: faces consisting of a single element are zero-dimensional, faces consisting of two elements are one-dimensional, etc. The dimension of the complex Template:Math 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 Template:Math is said to be finite if it has finitely many faces, or equivalently if its vertex set is finite. Also, Template:Math is said to be pure if it is finite-dimensional (but not necessarily finite) and every facet has the same dimension. In other words, Template:Math is pure if Template:Math is finite and every face is contained in a facet of dimension Template:Math.
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 Template:Math is an abstract simplicial complex L such that every face of L belongs to Template:Math; that is, Template:Math and L is an abstract simplicial complex. A subcomplex that consists of all of the subsets of a single face of Template:Math is often called a simplex of Template:Math. (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 Template:Math is the subcomplex of Template:Math consisting of all of the faces of Template:Math that have dimension at most d. In particular, the 1-skeleton is called the underlying graph of Template:Math. The 0-skeleton of Template:Math 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 Template:Mvar in Template:Math, often denoted Template:Math or Template:Math, is the subcomplex of Template:Math defined by
- <math> \Delta/Y := \{ X\in \Delta \mid X\cap Y = \varnothing,\, X\cup Y \in \Delta \}. </math>
Note that the link of the empty set is Template:Math itself.
Simplicial mapsEdit
{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Given two abstract simplicial complexes, Template:Math and Template:Math, a simplicial map is a function Template:Math that maps the vertices of Template:Math to the vertices of Template:Math and that has the property that for any face Template:Mvar of Template:Math, the image Template:Math is a face of Template:Math. 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 Template:Math and the vertex set Template:Math of Template:Math: for the purposes of defining a category of abstract simplicial complexes, the elements of S not lying in Template:Math are irrelevant. More precisely, SCpx is equivalent to the category where:
- an object is a set S equipped with a collection of non-empty finite subsets Template:Math that contains all singletons and such that if Template:Mvar is in Template:Math and Template:Math is non-empty, then Template:Mvar also belongs to Template:Math.
- a morphism from Template:Math to Template:Math is a function Template:Math such that the image of any element of Template:Math is an element of Template:Math.
Geometric realizationEdit
We can associate to any abstract simplicial complex (ASC) K a topological space <math>|K|</math>, called its geometric realization. There are several ways to define <math>|K|</math>.
Geometric definitionEdit
Every geometric simplicial complex (GSC) determines an ASC:<ref name=":0">Template:Cite Matousek 2007, Section 4.3</ref>Template:Rp the vertices of the ASC are the vertices of the GSC, and the faces of the ASC are the vertex-sets of the faces of the GSC. For example, consider a GSC with 4 vertices {1,2,3,4}, where the maximal faces are the triangle between {1,2,3} and the lines between {2,4} and {3,4}. Then, the corresponding ASC contains the sets {1,2,3}, {2,4}, {3,4}, and all their subsets. We say that the GSC is the geometric realization of the ASC.
Every ASC has a geometric realization. This is easy to see for a finite ASC.<ref name=":0" />Template:Rp Let <math>N := |V(K)|</math>. Identify the vertices in <math>V(K)</math> with the vertices of an (N-1)-dimensional simplex in <math>\R^N</math>. Construct the GSC {conv(F): F is a face in K}. Clearly, the ASC associated with this GSC is identical to K, so we have indeed constructed a geometric realization of K. In fact, an ASC can be realized using much fewer dimensions. If an ASC is d-dimensional (that is, the maximum cardinality of a simplex in it is d+1), then it has a geometric realization in <math>\R^{2d+1}</math>, but might not have a geometric realization in <math>\R^{2d}</math> <ref name=":0" />Template:Rp The special case d=1 corresponds to the well-known fact, that any graph can be plotted in <math>\R^{3}</math> where the edges are straight lines that do not intersect each other except in common vertices, but not any graph can be plotted in <math>\R^{2}</math> in this way.
If K is the standard combinatorial n-simplex, then <math>|K|</math> can be naturally identified with Template:Math.
Every two geometric realizations of the same ASC, even in Euclidean spaces of different dimensions, are homeomorphic.<ref name=":0" />Template:Rp Therefore, given an ASC K, one can speak of the geometric realization of K.
Topological definitionEdit
The construction goes as follows. First, define <math>|K|</math> as a subset of <math>[0, 1]^S</math> consisting of functions <math>t\colon S\to [0, 1]</math> satisfying the two conditions:
- <math>\{s\in S:t_s>0\}\in K</math>
- <math>\sum_{s\in S}t_s=1</math>
Now think of the set of elements of <math>[0, 1]^S</math> with finite support as the direct limit of <math>[0, 1]^A</math> where A ranges over finite subsets of S, and give that direct limit the induced topology. Now give <math>|K|</math> the subspace topology.
Categorical definitionEdit
Alternatively, let <math>\mathcal{K}</math> denote the category whose objects are the faces of Template:Mvar and whose morphisms are inclusions. Next choose a total order on the vertex set of Template:Mvar and define a functor F from <math>\mathcal{K}</math> to the category of topological spaces as follows. For any face X in K of dimension n, let Template:Math be the standard n-simplex. The order on the vertex set then specifies a unique bijection between the elements of Template:Mvar and vertices of Template:Math, ordered in the usual way Template:Math. If Template:Math is a face of dimension Template:Math, then this bijection specifies a unique m-dimensional face of Template:Math. Define Template:Math to be the unique affine linear embedding of Template:Math as that distinguished face of Template:Math, such that the map on vertices is order-preserving.
We can then define the geometric realization <math>|K|</math> as the colimit of the functor F. More specifically <math>|K|</math> is the quotient space of the disjoint union
- <math>\coprod_{X \in K}{F(X)}</math>
by the equivalence relation that identifies a point Template:Math with its image under the map Template:Math, for every inclusion Template:Math.
ExamplesEdit
1. Let V be a finite set of cardinality Template:Math. The combinatorial n-simplex with vertex-set V is an ASC whose faces are all nonempty subsets of V (i.e., it is the power set of V). If Template:Math 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, all of whose 2-element subsets are 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 <math>I</math> be a square-free monomial ideal in a polynomial ring <math>S = K[x_1, \dots, x_n]</math> (that is, an ideal generated by products of subsets of variables). Then the exponent vectors of those square-free monomials of <math>S</math> that are not in <math>I</math> determine an abstract simplicial complex via the map <math>\mathbf{a}\in \{0,1\}^n \mapsto \{i \in [n] : a_i = 1\}</math>. In fact, there is a bijection between (non-empty) abstract simplicial complexes on Template:Math vertices and square-free monomial ideals in Template:Math. If <math>I_{\Delta}</math> is the square-free ideal corresponding to the simplicial complex <math>\Delta</math> then the quotient <math>S/I_{\Delta}</math> is known as the Stanley–Reisner ring of <math>{\Delta}</math>.
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.
EnumerationEdit
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 nth Dedekind number. These numbers grow very rapidly, and are known only for Template:Math; the Dedekind numbers are (starting with n = 0):
- 1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787, 286386577668298411128469151667598498812365 (sequence A014466 in the OEIS). This corresponds to the number of non-empty antichains of subsets of an Template:Math set.
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, 286386577668298410623295216696338374471993" (sequence A006126 in the OEIS), 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, 489996795, 1392195548399980210" (sequence A006602 in the OEIS), starting at n = 1.
Computational problemsEdit
{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The simplicial complex recognition problem is: given a finite ASC, decide whether its geometric realization is homeomorphic to a given geometric object. This problem is undecidable for any d-dimensional manifolds for d ≥ 5.<ref>Template:Citation.</ref>
Relation to other conceptsEdit
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.