Abstract simplicial complex
   HOME

TheInfoList



OR:

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a
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, set fam ...
that is closed under taking
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s, 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 In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...
. Lee, John M., Introduction to Topological Manifolds, Springer 2011, , p153 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
matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s and
greedoid In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Hassler Whitney, Whitney in 1935 to study planar graphs and was later used by Jack Edmonds, Edmonds to characterize a ...
s, abstract simplicial complexes are also called
independence system In combinatorics, combinatorial mathematics, an independence system is a pair (V, \mathcal), where is a finite Set (mathematics), set and is a collection of subsets of (called the independent sets or feasible sets) with the following properties: ...
s. An abstract simplex can be studied algebraically by forming its
Stanley–Reisner ring In mathematics, a Stanley–Reisner ring, or face ring, is a quotient of a polynomial algebra over a field by a square-free monomial ideal. Such ideals are described more geometrically in terms of finite simplicial complexes. The Stanley–Reisner ...
; this sets up a powerful relation between
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
commutative algebra Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prominent ...
.


Definitions

A collection of non-empty finite subsets of a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''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 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 Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by Johnn ...
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
s: 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 In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...
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 : \Delta/Y := \. Note that the link of the empty set is itself.


Simplicial maps

Given two abstract simplicial complexes, and , a
simplicial map A simplicial map (also called simplicial mapping) is a function between two simplicial complexes, with the property that the images of the vertices of a simplex always span a simplex. Simplicial maps can be used to approximate continuous functions ...
is a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
that maps the vertices of to the vertices of and that has the property that for any face of , the
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
is a face of . There is a
category Category, plural categories, may refer to: Philosophy and general uses * Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) * ...
SCpx with abstract simplicial complexes as objects and simplicial maps as
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
s. This is equivalent to a suitable category defined using non-abstract
simplicial complexes In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial se ...
. 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: * an object is a set ''S'' equipped with a collection of non-empty finite subsets that contains all singletons and such that if is in and is non-empty, then also belongs to . * a morphism from to is a function such that the image of any element of is an element of .


Geometric realization

We can associate to any abstract simplicial complex (ASC) ''K'' a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
, K, , called its geometric realization. There are several ways to define , K, .


Geometric definition

Every
geometric simplicial complex In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial se ...
(GSC) determines an ASC:'', Section 4.3'' 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 , where the maximal faces are the triangle between and the lines between and . Then, the corresponding ASC contains the sets , , , 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.'''' Let N := , V(K), . Identify the vertices in V(K) with the vertices of an (''N-1'')-dimensional simplex in \R^N. Construct the GSC . 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 \R^, but might not have a geometric realization in \R^ '''' The special case ''d''=1 corresponds to the well-known fact, that any
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
can be plotted in \R^ where the edges are straight lines that do not intersect each other except in common vertices, but not any
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
can be plotted in \R^ in this way. If ''K'' is the standard combinatorial ''n''-simplex, then , K, can be naturally identified with . Every two geometric realizations of the same ASC, even in Euclidean spaces of different dimensions, are homeomorphic.'''' Therefore, given an ASC ''K,'' one can speak of ''the'' geometric realization of ''K''.


Topological definition

The construction goes as follows. First, define , K, as a subset of , 1S consisting of functions t\colon S\to , 1/math> satisfying the two conditions: :\\in K :\sum_t_s=1 Now think of the set of elements of , 1S with finite support as the
direct limit In mathematics, a direct limit is a way to construct a (typically large) object from many (typically smaller) objects that are put together in a specific way. These objects may be groups, rings, vector spaces or in general objects from any categor ...
of , 1A where ''A'' ranges over finite subsets of ''S'', and give that direct limit the
induced topology In topology and related areas of mathematics, a subspace of a topological space ''X'' is a subset ''S'' of ''X'' which is equipped with a topology induced from that of ''X'' called the subspace topology (or the relative topology, or the induced t ...
. Now give , K, the
subspace topology In topology and related areas of mathematics, a subspace of a topological space ''X'' is a subset ''S'' of ''X'' which is equipped with a topology induced from that of ''X'' called the subspace topology (or the relative topology, or the induced to ...
.


Categorical definition

Alternatively, let \mathcal denote the category whose objects are the faces of and whose morphisms are inclusions. Next choose a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
on the vertex set of and define a
functor In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
''F'' from \mathcal 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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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 Affine may describe any of various topics concerned with connections or affinities. It may refer to: * Affine, a relative by marriage in law and anthropology * Affine cipher, a special case of the more general substitution cipher * Affine comb ...
linear
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is gi ...
of 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 In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products, pullbacks and inverse limits. The dual notion of a colimit generalizes constructions such ...
of the functor ''F''. More specifically , K, is the quotient space of the
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
:\coprod_ by the
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation ...
that identifies a point with its image under the map , for every inclusion .


Examples

1. Let ''V'' be a finite set of
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
. 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 In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of ''V''). If then this ASC is called the standard combinatorial ''n''-simplex. 2. Let ''G'' be an undirected graph. The
clique complex Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques (complete subgraphs) of an undir ...
of ''G'' is an ASC whose faces are all
cliques A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
(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 In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
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 In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
. 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 The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph ''G'', denoted by I(''G''), is an abstract simplicial complex (that is, a family of ...
of the
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
of ''H''. 4. Let ''P'' be a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
(poset). The order complex of ''P'' is an ASC whose faces are all finite
chains A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
in ''P''. Its
homology Homology may refer to: Sciences Biology *Homology (biology), any characteristic of biological organisms that is derived from a common ancestor * Sequence homology, biological homology between DNA, RNA, or protein sequences *Homologous chrom ...
groups and other topological invariants contain important information about the poset ''P''. 5. Let ''M'' be a
metric space In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
and ''δ'' a real number. The
Vietoris–Rips complex In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is a way of forming a topological space from distances in a set of points. It is an abstract simplicial complex that can be defined from any metric space ...
is an ASC whose faces are the finite subsets of ''M'' with diameter at most ''δ''. It has applications in homology theory,
hyperbolic group In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a ''word hyperbolic group'' or ''Gromov hyperbolic group'', is a finitely generated group equipped with a word metric satisfying certain properties abstra ...
s,
image processing An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
, and
mobile ad hoc network A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points ...
ing. It is another example of a flag complex. 6. Let I be a square-free
monomial ideal In abstract algebra, a monomial ideal is an ideal generated by monomials in a multivariate polynomial ring over a field. A toric ideal is an ideal generated by differences of monomials (provided the ideal is a prime ideal). An affine or projectiv ...
in a
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
S = K _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 S that are not in I determine an abstract simplicial complex via the map \mathbf\in \^n \mapsto \. In fact, there is a bijection between (non-empty) abstract simplicial complexes on vertices and square-free monomial ideals in . If I_ is the square-free ideal corresponding to the simplicial complex \Delta then the
quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
S/I_ is known as the
Stanley–Reisner ring In mathematics, a Stanley–Reisner ring, or face ring, is a quotient of a polynomial algebra over a field by a square-free monomial ideal. Such ideals are described more geometrically in terms of finite simplicial complexes. The Stanley–Reisner ...
of . 7. For any
open covering In mathematics, and more particularly in set theory, a cover (or covering) of a set X is a collection of subsets of X whose union is all of X. More formally, if C = \lbrace U_\alpha : \alpha \in A \rbrace is an indexed family of subsets U_\alpha ...
''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 File:Monotone Boolean functions 0,1,2,3.svg, 400px, The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively (move mouse over right diagram to see description) circle 6 ...
. These numbers grow very rapidly, and are known only for ; the Dedekind numbers are (starting with ''n'' = 0): :1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787 . This corresponds to the number of non-empty
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
s of subsets of an 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" , 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.


Computational problems

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.


Relation to other concepts

An abstract simplicial complex with an additional property called the augmentation property or the exchange property yields a
matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
. The following expression shows the relations between the terms: HYPERGRAPHS = SET-FAMILIES ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.


See also

*
Kruskal–Katona theorem In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the ''f''-vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform ...
*
Simplicial set In mathematics, a simplicial set is an object composed of ''simplices'' in a specific way. Simplicial sets are higher-dimensional generalizations of directed graphs, partially ordered sets and categories. Formally, a simplicial set may be defined a ...


References

{{DEFAULTSORT:Abstract Simplicial Complex Algebraic topology Families of sets Simplicial sets