Abstract simplicial complex

Last updated
A geometrical representation of an abstract simplicial complex that is not a valid simplicial complex. Simplicial complex nonexample.svg
A geometrical representation of an abstract simplicial complex that is not a valid 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. [1] 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).

Contents

In the context of matroids and greedoids, abstract simplicial complexes are also called independence systems . [2]

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 X in Δ, and every non-empty subset YX, the set Y also belongs to Δ.

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 YX, 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. 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 faceX 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 complexdim(Δ) 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 an abstract simplicial complex L such that every face of L belongs to Δ; that is, L ⊆ Δ 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 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  f that maps the vertices of Δ to the vertices of Γ and that has the property that for any face X of Δ, the image  f(X) 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 V(Δ) ⊆ S of Δ: for the purposes of defining a category of abstract simplicial complexes, the elements of S not lying in V(Δ) 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 , called its geometric realization, which is the carrier of a simplicial complex. The construction goes as follows.

First, define as a subset of consisting of functions satisfying the two conditions:

Now think of the set of elements of with finite support as the direct limit of where A ranges over finite subsets of S, and give that direct limit the induced topology. Now give the subspace topology.

Alternatively, let denote the category whose objects are the faces of K and whose morphisms are inclusions. Next choose a total order on the vertex set of K and define a functor F from to the category of topological spaces as follows. For any face X in K of dimension n, let F(X) = Δn be the standard n-simplex. The order on the vertex set then specifies a unique bijection between the elements of X and vertices of Δn, ordered in the usual way e0 < e1 < ... < en. If YX is a face 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 as the colimit of the functor F. More specifically is the quotient space of the disjoint union

by the equivalence relation that identifies a point yF(Y) with its image under the map F(Y) → F(X), for every inclusion YX.

If K is finite, then we can describe more simply. Choose an embedding of the vertex set of K as an affinely independent subset of some Euclidean space of sufficiently high dimension N. Then any face X in K can be identified with the geometric simplex in spanned by the corresponding embedded vertices. Take to be the union of all such simplices.

If K is the standard combinatorial n-simplex, then can be naturally identified with Δn.

Examples

1. Let V be a finite set of cardinality n + 1. 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 V = S = {0, 1, ..., n}, 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 be a square-free monomial ideal in a polynomial ring (that is, an ideal generated by products of subsets of variables). Then the exponent vectors of those square-free monomials of that are not in determine an abstract simplicial complex via the map . In fact, there is a bijection between (non-empty) abstract simplicial complexes on n vertices and square-free monomial ideals in S. If is the square-free ideal corresponding to the simplicial complex then the quotient is known as the Stanley–Reisner ring of .

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 nth Dedekind number. These numbers grow very rapidly, and are known only for n ≤ 8; the Dedekind numbers are (starting with n = 0):

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787 (sequence A014466 in the OEIS ). This corresponds to the number of non-empty antichains of subsets of an n 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" (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" (sequence A006602 in the OEIS ), 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.

See also

Related Research Articles

Simplex Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given space.

Simplicial complex

In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their n-dimensional counterparts. Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory. The purely combinatorial counterpart to a simplicial complex is an abstract simplicial complex.

In mathematics, a building is a combinatorial and geometric structure which simultaneously generalizes certain aspects of flag manifolds, finite projective planes, and Riemannian symmetric spaces. They were initially introduced by Jacques Tits as a means to understand the structure of exceptional groups of Lie type. The more specialized theory of Bruhat–Tits buildings plays a role in the study of p-adic Lie groups analogous to that of the theory of symmetric spaces in the theory of Lie groups.

In the mathematical disciplines of topology and geometry, an orbifold is a generalization of a manifold. Roughly speaking, an orbifold is a topological space which is locally a finite group quotient of an Euclidean space.

In algebraic topology, a branch of mathematics, singular homology refers to the study of a certain set of algebraic invariants of a topological space X, the so-called homology groups Intuitively, singular homology counts, for each dimension n, the n-dimensional holes of a space. Singular homology is a particular example of a homology theory, which has now grown to be a rather broad collection of theories. Of the various theories, it is perhaps one of the simpler ones to understand, being built on fairly concrete constructions.

In geometry, the barycentric subdivision is a standard way of dividing an arbitrary convex polygon into triangles, a convex polyhedron into tetrahedra, or, in general, a convex polytope into simplices with the same dimension, by connecting the barycenters of their faces in a specific way.

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 or a set-family or a set-system.

In mathematics, a simplicial set is an object made up 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 as a contravariant functor from the simplex category to the category of sets. Simplicial sets were introduced in 1950 by Samuel Eilenberg and J. A. Zilber.

In algebraic topology, simplicial homology is the sequence of homology groups of a simplicial complex. It formalizes the idea of the number of holes of a given dimension in the complex. This generalizes the number of connected components.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

Triangulation (topology)

In mathematics, topology generalizes the notion of triangulation in a natural way as follows:

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<i>n</i>-skeleton

In mathematics, particularly in algebraic topology, the n-skeleton of a topological space X presented as a simplicial complex refers to the subspace Xn that is the union of the simplices of X of dimensions mn. In other words, given an inductive definition of a complex, the n-skeleton is obtained by stopping at the n-th step.

In geometry, the link of a vertex of a 2-dimensional simplicial complex is a graph that encodes information about the local structure of the complex at the vertex.

In mathematics, Kan complexes and Kan fibrations are part of the theory of simplicial sets. Kan fibrations are the fibrations of the standard model category structure on simplicial sets and are therefore of fundamental importance. Kan complexes are the fibrant objects in this model category. The name is in honor of Daniel Kan.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

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.

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 ring construction is a basic tool within algebraic combinatorics and combinatorial commutative algebra. Its properties were investigated by Richard Stanley, Melvin Hochster, and Gerald Reisner in the early 1970s.

Discrete calculus or the calculus of discrete functions, is the mathematical study of incremental change, in the same way that geometry is the study of shape and algebra is the study of generalizations of arithmetic operations. The word calculus is a Latin word, meaning originally "small pebble"; as such pebbles were used for calculation, the meaning of the word has evolved and today usually means a method of computation. Meanwhile, calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the study of continuous change.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

References

  1. Lee, John M., Introduction to Topological Manifolds, Springer 2011, ISBN   1-4419-7939-5, p153
  2. Korte, Bernhard; Lovász, László; Schrader, Rainer (1991). Greedoids. Springer-Verlag. p. 9. ISBN   3-540-18190-3.