Editing Simplicial complex

{{Short description|Mathematical set composed of points, line segments, triangles and higher-dimensional simplices}}

[[File:Simplicial complex example.svg|thumb|200px|A simplicial 3-complex.]]

In [[mathematics]], a '''simplicial complex''' is a structured [[Set (mathematics)|set]] composed of [[Point (geometry)|point]]s, [[line segment]]s, [[triangle]]s, and their ''n''-dimensional counterparts, called [[Simplex|simplices]], such that all the faces and intersections of the elements are also included in the set (see illustration). Simplicial complexes should not be confused with the more abstract notion of a [[simplicial set]] appearing in modern simplicial [[homotopy theory]]. The purely [[Combinatorics|combinatorial]] counterpart to a simplicial complex is an [[abstract simplicial complex]]. To distinguish a simplicial complex from an abstract simplicial complex, the former is often called a '''geometric simplicial complex'''.<ref name=":0">{{cite Matousek 2007}}, Section 4.3</ref>{{rp|page=7}}

== Definitions ==
A '''simplicial complex''' <math>\mathcal{K}</math> is a set of [[Simplex|simplices]] that satisfies the following conditions:
# Every [[Simplex#Elements|face]] of a simplex from <math>\mathcal{K}</math> is also in <math>\mathcal{K}</math>.
# The non-empty [[Set intersection|intersection]] of any two simplices <math>\sigma_1, \sigma_2 \in \mathcal{K}</math> is a face of both <math>\sigma_1</math> and <math>\sigma_2</math>.

See also the definition of an [[abstract simplicial complex]], which loosely speaking is a simplicial complex without an associated geometry.

A '''simplicial ''k''-complex''' <math>\mathcal{K}</math> is a simplicial complex where the largest dimension of any simplex in <math>\mathcal{K}</math> equals ''k''. For instance, a simplicial 2-complex must contain at least one triangle, and must not contain any [[tetrahedra]] or higher-dimensional simplices.

A '''pure''' or '''homogeneous''' simplicial ''k''-complex <math>\mathcal{K}</math> is a simplicial complex where every simplex of dimension less than ''k'' is a face of some simplex <math>\sigma \in \mathcal{K}</math> of dimension exactly ''k''. Informally, a pure 1-complex "looks" like it's made of a bunch of lines, a 2-complex "looks" like it's made of a bunch of triangles, etc. An example of a ''non''-homogeneous complex is a triangle with a line segment attached to one of its vertices. Pure simplicial complexes can be thought of as [[Triangulation (topology)|triangulations]] and provide a definition of [[polytope]]s.

A '''facet''' is a maximal simplex, i.e., any simplex in a complex that is ''not'' a face of any larger simplex.<ref>{{citation |title=Triangulations: Structures for Algorithms and Applications |volume=25 |series=Algorithms and Computation in Mathematics |first1=Jesús A. |last1=De Loera |author1-link=Jesús A. De Loera |first2=Jörg |last2=Rambau |first3=Francisco |last3=Santos |author3-link=Francisco Santos Leal |publisher=Springer |year=2010 |isbn=9783642129711 |page=493 |url=https://books.google.com/books?id=SxY1Xrr12DwC&pg=PA493 }}</ref> (Note the difference from a [[Face of a simplex|"face" of a simplex]]). A pure simplicial complex can be thought of as a complex where all facets have the same dimension. For (boundary complexes of) [[simplicial polytope]]s this coincides with the meaning from polyhedral combinatorics.

Sometimes the term ''face'' is used to refer to a simplex of a complex, not to be confused with a face of a simplex.

For a simplicial complex [[Embedding|embedded]] in a ''k''-dimensional space, the ''k''-faces are sometimes referred to as its '''cells'''. The term ''cell'' is sometimes used in a broader sense to denote a set [[Homeomorphism|homeomorphic]] to a simplex, leading to the definition of [[cell complex]].

The '''underlying space''', sometimes called the '''carrier''' of a simplicial complex, is the [[union (set theory)|union]] of its simplices. It is usually denoted by <math>|\mathcal{K}|</math> or <math>\|\mathcal{K}\|</math>.

== Support ==
The [[relative interior]]s of all simplices in <math>\mathcal{K}</math> form a partition of its underlying space <math>|\mathcal{K}|</math>: for each point <math>x\in |\mathcal{K}|</math>, there is exactly one simplex in <math>\mathcal{K}</math> containing <math>x</math> in its relative interior. This simplex is called the '''support''' of ''x'' and denoted <math>\operatorname{supp}(x)</math>.<ref name=":02">{{cite Matousek 2007}}, Section 4.3</ref>{{rp|page=9|location=}}

== Closure, star, and link ==
<gallery class="center" widths="350" heights="112">
File:Simplicial complex closure.svg|Two {{color|#fc3|simplices}} and their {{color|#093|'''closure'''}}.
File:Simplicial complex star.svg|A {{color|#fc3|vertex}} and its {{color|#093|'''star'''}}.
File:Simplicial complex link.svg|A {{color|#fc3|vertex}} and its {{color|#093|'''link'''}}.
</gallery>

Let ''K'' be a simplicial complex and let ''S'' be a collection of simplices in ''K''.

The '''closure''' of ''S'' (denoted <math>\mathrm{Cl}\ S</math>) is the smallest simplicial subcomplex of ''K'' that contains each simplex in ''S''. <math>\mathrm{Cl}\ S</math> is obtained by repeatedly adding to ''S'' each face of every simplex in ''S''.

The '''[[Star (simplicial complex)|star]]''' of ''S'' (denoted <math>\mathrm{st}\ S</math>) is the union of the stars of each simplex in ''S''. For a single simplex ''s'', the star of ''s'' is the set of simplices in ''K'' that have ''s'' as a face. The star of ''S'' is generally not a simplicial complex itself, so some authors define the '''closed star''' of S (denoted <math>\mathrm{St}\ S</math>) as <math>\mathrm{Cl}\ \mathrm{st}\ S</math> the closure of the star of S.

The '''[[Link (geometry)|link]]''' of ''S'' (denoted <math>\mathrm{Lk}\ S</math>) equals <math>\mathrm{Cl}\big(\mathrm{st}(S)\big) \setminus \mathrm{st}\big(\mathrm{Cl}(S)\big)</math>. It is the closed star of ''S'' minus the stars of all faces of ''S''.

== Algebraic topology ==
{{Main|Simplicial homology}}
In [[algebraic topology]], simplicial complexes are often useful for concrete calculations. For the definition of [[homology group]]s of a simplicial complex, one can read the corresponding [[chain complex]] directly, provided that consistent orientations are made of all simplices. The requirements of [[homotopy theory]] lead to the use of more general spaces, the [[CW complex]]es. Infinite complexes are a technical tool basic in algebraic topology. See also the discussion at [[Polytope]] of simplicial complexes as subspaces of [[Euclidean space]] made up of subsets, each of which is a [[simplex]]. That somewhat more concrete concept is there attributed to [[Pavel Sergeevich Alexandrov|Alexandrov]]. Any finite simplicial complex in the sense talked about here can be embedded as a polytope in that sense, in some large number of dimensions. In algebraic topology, a [[Compact space|compact]] [[topological space]] which is homeomorphic to the geometric realization of a finite simplicial complex is usually called a [[polyhedron]] (see {{harvnb|Spanier|1966}}, {{harvnb|Maunder|1996}}, {{harvnb|Hilton|Wylie|1967}}).

== Combinatorics ==
[[Combinatorics|Combinatorialists]] often study the '''''f''-vector''' of a simplicial d-complex Δ, which is the [[integer]] sequence <math>(f_0, f_1, f_2, \ldots, f_{d+1})</math>, where ''f''<sub>''i''</sub> is the number of (''i''−1)-dimensional faces of Δ (by convention, ''f''<sub>0</sub>&nbsp;=&nbsp;1 unless Δ is the empty complex). For instance, if Δ is the boundary of the [[octahedron]], then its ''f''-vector is (1, 6, 12, 8), and if Δ is the first simplicial complex pictured above, its ''f''-vector is (1, 18, 23, 8, 1). A complete characterization of the possible ''f''-vectors of simplicial complexes is given by the [[Kruskal–Katona theorem]].

By using the ''f''-vector of a simplicial ''d''-complex Δ as coefficients of a [[polynomial]] (written in decreasing order of exponents), we obtain the '''f-polynomial''' of Δ. In our two examples above, the ''f''-polynomials would be <math>x^3+6x^2+12x+8</math> and <math>x^4+18x^3+23x^2+8x+1</math>, respectively.

Combinatorists are often quite interested in the '''h-vector''' of a simplicial complex Δ, which is the sequence of coefficients of the polynomial that results from plugging ''x''&nbsp;−&nbsp;1 into the ''f''-polynomial of Δ. Formally, if we write ''F''<sub>Δ</sub>(''x'') to mean the ''f''-polynomial of Δ, then the '''h-polynomial''' of Δ is
: <math>F_\Delta(x-1)=h_0x^{d+1}+h_1x^d+h_2x^{d-1}+\cdots+h_dx+h_{d+1}</math>
and the ''h''-vector of Δ is
: <math>(h_0,  h_1,  h_2, \cdots,  h_{d+1}).</math>

We calculate the h-vector of the octahedron boundary (our first example) as follows:
: <math>F(x-1)=(x-1)^3+6(x-1)^2+12(x-1)+8=x^3+3x^2+3x+1.</math>

So the ''h''-vector of the boundary of the octahedron is (1, 3, 3, 1). It is not an accident this ''h''-vector is symmetric. In fact, this happens whenever Δ is the boundary of a simplicial [[polytope]] (these are the [[Dehn–Sommerville equations]]). In general, however, the ''h''-vector of a simplicial complex is not even necessarily positive. For instance, if we take Δ to be the 2-complex given by two triangles intersecting only at a common vertex, the resulting ''h''-vector is (1, 3, −2).

A complete characterization of all simplicial polytope ''h''-vectors is given by the celebrated [[g-theorem]] of [[Richard P. Stanley|Stanley]], Billera, and Lee.

Simplicial complexes can be seen to have the same geometric structure as the [[contact graph]] of a [[sphere packing]] (a graph where vertices are the centers of spheres and edges exist if the corresponding packing elements touch each other) and as such can be used to determine the combinatorics of sphere packings, such as the number of touching pairs (1-simplices), touching triplets (2-simplices), and touching quadruples (3-simplices) in a sphere packing.

== Triangulation == 
{{Main|Triangulation (topology)}}

A triangulation of a [[topological space]] <math>X</math> is a [[homeomorphism]] <math>t: |\mathcal{T}|\rightarrow X</math> where <math>\mathcal{T}</math> is a simplicial complex.

Topological spaces do not necessarily admit a triangulation and if they do, it is never unique. [[Topological manifold]]s of dimension <math>d \leq 3</math> are always triangulable,<ref>{{citation |surname1=Edwin Moise |title=Geometric Topology in Dimensions 2 and 3 |publisher=Springer Verlag |publication-place=New York |date=1977 }}</ref><ref>{{cite web |title=Über den Begriff der Riemannschen Fläche |periodical= |publisher= |url=https://www.maths.ed.ac.uk/~v1ranick/papers/rado.pdf |first=Tibor |last=Rado |language=German }}</ref><ref>{{citation |surname1=John M. Lee |title=Introduction to Topological manifolds |publisher=Springer Verlag |publication-place=New York/Berlin/Heidelberg |at=p.&nbsp;92 |isbn=0-387-98759-2 |date=2000 }}</ref> but not necessarily for <math>d > 3</math>.<ref>{{citation |author1=R. C. Kirby |author2=L. C. Siebenmann |periodical=Foundational Essays on Topological Manifolds, Smoothings, and Triangulations. (AM-88) |title=Annex B. On The Triangulation of Manifolds and the Hauptvermutung |publisher=Princeton University Press |at=pp.&nbsp;299–306 |date=1977-12-31 }}</ref><ref>{{cite book |last1=Akbulut |first1=Selman |last2=McCarthy |first2=John D. |title=Casson's Invariant for Oriented Homology Three-Spheres {{!}} Princeton University Press |date=19 April 2016 |chapter=Chapter IV: Casson's Invariant for Oriented Homology 3-spheres |publisher=Princeton University Press |isbn=9780691636085 |language=en }}</ref>

[[Differentiable manifold]]s of any dimension <math>d\ge 1</math> admit triangulations.<ref>{{citation |surname1=J. H. C. Whitehead |periodical=Annals of Mathematics |title=On C1-Complexes |volume=41 |issue=4 |at=pp.&nbsp;809–824 |issn=0003-486X |date=1940 |doi=10.2307/1968861 |jstor=1968861 }}</ref>

== Computational problems ==
{{Main|Simplicial complex recognition problem}}
The [[simplicial complex recognition problem]] is: given a finite simplicial complex, decide whether it is homeomorphic to a given geometric object. This problem is [[Undecidable problem|undecidable]] for any ''d''-dimensional manifolds for <math>d \ge 5</math>.<ref>{{citation |last=Stillwell |first=John |title=Classical Topology and Combinatorial Group Theory |url=https://books.google.com/books?id=265lbM42REMC&pg=PA247 |volume=72 |page=247 |year=1993 |series=Graduate Texts in Mathematics |publisher=Springer |isbn=9780387979700 |authorlink=John Stillwell}}.</ref><ref>{{cite arXiv |last=Poonen |first=Bjorn |date=2014-10-25 |title=Undecidable problems: a sampler |class=math.LO |eprint=1204.0299 }}</ref>{{rp|pages=9–11}}

== See also ==
* [[Abstract simplicial complex]]
* [[Barycentric subdivision]]
* [[Causal dynamical triangulation]]
* [[Delta set]]
* [[Loop quantum gravity]]
* [[Polygonal chain]]{{spaced ndash}} 1 dimensional simplicial complex
* [[Tucker's lemma]]
* [[Simplex tree]]

== References ==
{{reflist}}
* {{citation|last=Spanier|first=Edwin H.|author-link=Edwin Spanier|title=Algebraic Topology|year=1966|publisher=Springer|isbn=0-387-94426-5}}
* {{citation|last=Maunder|first=Charles R.F.|title=Algebraic Topology|edition= Reprint of the 1980| year=1996|publisher=Dover|location=Mineola, NY|isbn=0-486-69131-4|mr=1402473}}
* {{citation|last1=Hilton|first1=Peter J.|author-link1=Peter Hilton 
| last2=Wylie|first2=Shaun|author-link2=Shaun Wylie|title=Homology Theory|year=1967|publisher=[[Cambridge University Press]]|location=New York|isbn=0-521-09422-4|mr=0115161}}

== External links ==
* {{MathWorld |urlname=SimplicialComplex |title=Simplicial complex}}

{{Topology}}

{{Authority control}}

[[Category:Topological spaces]]
[[Category:Algebraic topology]]
[[Category:Simplicial sets]]
[[Category:Triangulation (geometry)]]