Fact-checked by Grok 2 weeks ago

Simplicial complex

A simplicial complex is a collection of simplices—geometric objects such as points (0-simplices), line segments (1-simplices), triangles (2-simplices), and higher-dimensional analogues—that is closed under the taking of faces and whose pairwise intersections are also faces, providing a combinatorial framework for representing topological spaces.^[1]^[2] A simplex itself is defined as the convex hull of a finite set of affinely independent points in Euclidean space, with an n-simplex formed by n+1 such points.^[2] There are two primary variants: abstract simplicial complexes, which are purely set-theoretic collections of finite subsets closed under subsets and containing all singletons, and geometric simplicial complexes, which embed these structures in Euclidean space via convex hulls to form a topological space known as the geometric realization.^[3]^[4] Simplicial complexes serve as foundational tools in algebraic topology, where they enable the computation of invariants like homology groups through chain complexes and boundary operators, distinguishing topological spaces based on connectivity and holes without regard to embedding or metric properties.^[1] In combinatorics, they model hypergraphs with closure properties, facilitating the study of extremal set theory, shellability, and Cohen-Macaulay rings via Stanley-Reisner ideals.^[5] Beyond pure mathematics, these structures appear in applied fields such as computer graphics for surface modeling via triangulations, network science for higher-order interactions among agents, and data analysis through persistent homology to detect features in point clouds.^[2]^[3] The Euler characteristic, computed as the alternating sum of the number of simplices in each dimension, exemplifies a key topological invariant preserved under simplicial homeomorphisms.^[2]

Formal Definitions

Abstract Simplicial Complexes

An abstract simplicial complex is a purely combinatorial object defined as follows: Let V be a set of vertices. An abstract simplicial complex on V is a collection K of non-empty finite subsets of V, called simplices, such that if \sigma \in K and \tau \subseteq \sigma with \tau \neq \emptyset, then \tau \in K. This closure property ensures that the structure is downward-closed under inclusion, capturing the hereditary nature of simplices and their faces.^[6] Formally, an abstract simplicial complex can be presented as a pair (K, \leq), where K is the set of all simplices partially ordered by inclusion, or equivalently as the collection K itself satisfying the above subset condition. The vertices V are the elements of V(K) = \bigcup_{\sigma \in K} \sigma, and every singleton \{v\} for v \in V(K) must belong to K. This definition emphasizes the set-theoretic foundation without reference to geometry, allowing for flexible combinatorial constructions.^[6] Basic examples illustrate the concept. The void complex is the empty collection K = \emptyset, with no vertices. A single point complex has V = \{v\} and K = \{\{v\}\}, representing a 0-dimensional object. The full n-simplex on n+1 vertices is the collection of all non-empty subsets of V with |V| = n+1, forming the maximal complex on those vertices. A discrete complex on V consists solely of the singletons \{\{v\} \mid v \in V\}, with no higher-dimensional simplices.^[6] Abstract simplicial complexes may be finite, meaning both V(K) and K are finite sets, or infinite otherwise; finite complexes are the primary focus in most applications due to their computational tractability. The dimension of a simplicial complex K is defined as \dim K = \max \{ |\sigma| - 1 \mid \sigma \in K \}, or -\infty if K is empty, measuring the highest-dimensional simplex present. These structures can be visualized via geometric realization, where simplices are mapped to standard Euclidean simplices, but the abstract definition remains independent of such embeddings.^[6]

Geometric Simplicial Complexes

A geometric simplicial complex is a finite collection of simplices embedded in Euclidean space \mathbb{R}^d, where each simplex is the convex hull of a finite set of affinely independent points, such that the collection is closed under the operation of taking faces and the intersection of any two simplices is either empty or a common face of both. This intersection property ensures that simplices are glued together only along shared faces, forming a topological space without interior overlaps or self-intersections. The underlying space of the complex is the union of all its simplices, equipped with the subspace topology from \mathbb{R}^d.^[6]^[7] A set of points v_0, v_1, \dots, v_k \in \mathbb{R}^d is affinely independent if the vectors v_1 - v_0, \dots, v_k - v_0 are linearly independent over \mathbb{R}; this condition guarantees that the convex hull forms a k-simplex of full dimension k without degeneracies. Any point x in such a k-simplex can be uniquely expressed using barycentric coordinates as x = \sum_{i=0}^k t_i v_i, where t_i \geq 0 for all i, \sum_{i=0}^k t_i = 1, and the coordinates (t_0, \dots, t_k) parameterize the position relative to the vertices. These coordinates provide a natural affine structure, allowing simplicial maps to be defined as affine transformations preserving the vertices.^[6]^[8] A classic example is the standard n-simplex \Delta^n, defined as the convex hull of the standard basis vectors e_0 = (1,0,\dots,0), e_1 = (0,1,0,\dots,0), \dots, e_n = (0,\dots,0,1) in \mathbb{R}^{n+1}, or equivalently the set \{ (t_0, \dots, t_n) \in \mathbb{R}^{n+1} \mid t_i \geq 0, \sum_{i=0}^n t_i = 1 \}. This simplex serves as the prototypical building block, with its faces being lower-dimensional standard simplices.^[6]^[9]

Basic Components and Constructions

Simplices and Faces

A k-simplex is defined as the convex hull of k + 1 affinely independent points in Euclidean space, often denoted as \sigma = [v_0, v_1, \dots, v_k], where the points v_i are the vertices and no k of them lie in a hyperplane of dimension less than k-1.^[6] This geometric realization provides an intuitive visualization of simplices as the simplest convex polytopes in their dimension.^[10] The lowest-dimensional cases illustrate the structure: a 0-simplex is a single vertex (point), a 1-simplex is an edge (line segment connecting two vertices), a 2-simplex is a triangle (filled disk bounded by three edges), and a 3-simplex is a tetrahedron (solid bounded by four triangles), with higher-dimensional simplices generalizing this pattern as k-dimensional analogues of these basic shapes.^[11] Affinely independent vertices ensure the simplex has full dimension k and is non-degenerate.^[12] Faces of a k-simplex \sigma are the simplices formed by the convex hulls of its nonempty subsets of vertices, including \sigma itself as an improper face; proper faces exclude \sigma and correspond to strict subsets.^[13] For instance, the proper faces of a 2-simplex [v_0, v_1, v_2] consist of its three 1-simplex edges [v_0, v_1], [v_1, v_2], [v_0, v_2] and three 0-simplex vertices [v_0], [v_1], [v_2].^[10] The collection of all faces of \sigma, ordered by inclusion, forms the face poset of \sigma, which is isomorphic to the Boolean lattice on k + 1 elements, reflecting the combinatorial structure of subsets.^[14] The boundary operator \partial on a single oriented k-simplex \sigma = [v_0, \dots, v_k] is defined as the alternating sum of its (k-1)-dimensional faces:

\partial \sigma = \sum_{i=0}^k (-1)^i [v_0, \dots, \hat{v}_i, \dots, v_k],

where \hat{v}_i denotes omission of the i-th vertex, assigning orientations to the faces based on their induced ordering from \sigma.^[6] This operator captures the combinatorial boundary by linearly combining the facets with signs determined by vertex position, ensuring \partial^2 \sigma = 0 as faces cancel in pairs.^[15] For example, on a 2-simplex [v_0, v_1, v_2], \partial [v_0, v_1, v_2] = [v_1, v_2] - [v_0, v_2] + [v_0, v_1].^[6]

Geometric Realization

The geometric realization of an abstract simplicial complex K, denoted |K|, is the topological space obtained by embedding each simplex of K as a standard geometric simplex and gluing them along shared faces. Specifically, for each n-simplex \sigma \in K, take a copy of the standard n-simplex \Delta^n = \{ (t_0, \dots, t_n) \in \mathbb{R}^{n+1} \mid t_i \geq 0, \sum t_i = 1 \}, and form the disjoint union over all such simplices. Points lying in corresponding faces are then identified via the affine maps induced by the face inclusions in K, yielding the quotient space |K| = \bigsqcup_{\sigma \in K} \Delta^{n(\sigma)} / \sim, where the equivalence relation \sim equates points (x, \sigma) and (x', \tau) whenever x and x' map to the same point under the inclusion of a common face.^[6]^[16] This construction ensures that the topology of |K| reflects the combinatorial structure of K: isomorphic simplicial complexes yield homeomorphic realizations, as a simplicial isomorphism induces a continuous bijection between the quotient spaces that respects the gluings.^[6]^[16] The resulting space |K| inherits a piecewise linear (PL) structure from the affine nature of the standard simplices, allowing linear parametrizations within each simplex while maintaining compatibility across faces.^[6] Moreover, |K| is a CW-complex, with the open n-simplex \mathring{\Delta}^n serving as the n-cell attached along the boundary of the (n-1)-skeleton via the face maps.^[6] A concrete example illustrates this realization: the simplicial complex consisting of a single 2-simplex and its faces realizes as the closed 2-disk D^2, with the interior corresponding to the open simplex and the boundary to the 1-skeleton.^[6] In contrast, the boundary complex of a 3-simplex—which includes four 2-simplices glued along their shared edges and vertices—realizes as the 2-sphere S^2, forming a closed surface without boundary.^[6]

Local and Neighborhood Structures

Closure, Interior, and Boundary

In a simplicial complex K, the closure of a simplex \sigma \in K, denoted \mathrm{cl}(\sigma), is the smallest subcomplex of K containing \sigma; this consists of \sigma together with all of its faces, formally \mathrm{cl}(\sigma) = \{\tau \in K \mid \tau \leq \sigma\}, where \tau \leq \sigma indicates that \tau is a face of \sigma. This operator generates a closed subcomplex that captures the full downward closure under the face relation in the poset of simplices. The interior of a simplex \sigma, denoted \mathrm{int}(\sigma), is defined in the geometric realization as the points of \sigma excluding those on its boundary faces. For example, the interior of a 2-simplex (triangle) includes its open area but excludes the edges and vertices. The boundary of a simplex \sigma, denoted \partial \sigma, is the subcomplex formed by the union of all proper faces of \sigma, i.e., all \tau \leq \sigma with \dim \tau < \dim \sigma. For the entire complex K, the boundary \partial K is defined as the union of the boundaries \partial \sigma over all maximal simplices \sigma in K, yielding a subcomplex that identifies the "surface" elements not filled by higher-dimensional simplices. These operators underpin local structures, relating briefly to neighborhood concepts like the star and link of a simplex.

Star and Link Operators

In simplicial complexes, the star operator provides a way to capture the local neighborhood around a given simplex by considering all higher-dimensional simplices that contain it. For a simplex σ in a simplicial complex K, the star st(σ) is defined as the subcomplex consisting of all simplices τ in K such that σ is a face of τ, i.e., σ ≤ τ. This collection includes σ itself and forms an open subcomplex in the geometric realization, but its definition relies solely on the face relation and is thus independent of any specific embedding. The link operator complements the star by focusing on the "boundary" structure adjacent to σ, excluding the simplex itself. Specifically, the link lk(σ) is the subcomplex of all simplices τ in the closure of st(σ) such that τ ∩ σ = ∅. Equivalently, lk(σ) consists of those τ where σ ∪ τ is a simplex in K but τ shares no vertices with σ. Like the star, the link is a pure combinatorial construct, forming its own simplicial complex that encodes the connectivity around σ without overlapping it. A key property relating the star and link is that the closed star cl(st(σ))—the smallest subcomplex containing st(σ)—is combinatorially equivalent to the join of σ and lk(σ), often described as a cone with apex σ over the base lk(σ). In the geometric realization, this manifests as |cl(st(σ))| being homeomorphic to the product of the cone on |lk(σ)| with the standard simplex |σ|. Both operators are invariant under simplicial isomorphisms and do not depend on the choice of geometric realization, making them fundamental tools for studying local topology in abstract simplicial complexes. For an illustrative example, consider a triangulated 2-dimensional surface, such as a simplicial complex homeomorphic to a sphere or torus. The link of an interior vertex σ (a 0-simplex) consists of the edges and vertices forming a cycle graph around it, realizing a 1-sphere that bounds the local disk-like neighborhood. In contrast, for a boundary vertex, the link would form a path rather than a closed cycle, reflecting the manifold's edge.

Support and Carrier

In a simplicial complex K with vertex set V, the induced subcomplex on the vertex set \operatorname{vert}(\sigma) of a simplex \sigma \in K consists of all simplices in K whose vertices lie entirely within \operatorname{vert}(\sigma). This subcomplex includes \sigma itself along with all other simplices in K that can be formed using subsets of \operatorname{vert}(\sigma), providing a combinatorial restriction of K to the local structure determined by \sigma's vertices. For instance, if \sigma is a 2-simplex with vertices \{v_0, v_1, v_2\} and K contains an additional edge between v_0 and v_1, then the induced subcomplex on \{v_0, v_1, v_2\} encompasses \sigma, its three faces, and that edge. The induced subcomplex on a subset U \subseteq V is formed by all simplices in K with vertices contained in U. This construction captures the full substructure of K restricted to U, often used to study restrictions or filtrations within the complex. Both are instances of induced subcomplexes, which are themselves simplicial complexes satisfying the closure properties of K. Deletion of vertices corresponds to forming the induced subcomplex on the complementary set; specifically, removing a subset W \subseteq V yields the induced subcomplex on V \setminus W, which excludes all simplices intersecting W. For a single vertex v, this deletion removes the closed star \mathrm{St}(v) of all simplices containing v, potentially altering global properties such as connectivity—for example, in a path-like complex where v links two components, deletion disconnects the induced subcomplex on V \setminus \{v\} into separate subcomplexes.

Topological Applications

Simplicial Homology

Simplicial homology provides an algebraic framework to capture the topological features of a simplicial complex K by associating to it a sequence of abelian groups that detect "holes" in various dimensions. This theory, developed in the early 20th century, computes invariants of the geometric realization of K, a topological space formed by embedding the simplices in Euclidean space. The core construction involves the simplicial chain complex, a graded chain complex whose homology groups encode these invariants.^[6] To define the chain complex, one first equips each simplex in K with an orientation, which is a choice of ordering of its vertices up to even permutations. An oriented k-simplex \sigma = [v_0, v_1, \dots, v_k] determines the orientation of its faces by the induced ordering on the omitted vertex. The simplicial chain group C_k(K) is the free abelian group generated by the oriented k-simplices of K, with elements called k-chains that are finite integer linear combinations \sum n_\sigma \sigma, where n_\sigma \in \mathbb{Z}. The full simplicial chain complex is then C_*(K) = \bigoplus_{k \geq 0} C_k(K), a sequence of abelian groups connected by boundary homomorphisms.^[6]^[6] The boundary map \partial_k: C_k(K) \to C_{k-1}(K) is defined on basis elements by

\partial_k(\sigma) = \sum_{i=0}^k (-1)^i [v_0, \dots, \hat{v}_i, \dots, v_k],

where \hat{v}_i denotes the omission of the i-th vertex, and it extends linearly to all k-chains. This map satisfies the key property \partial_k \circ \partial_{k+1} = 0 for all k, as the boundary of a boundary cancels out due to telescoping sums and sign alternations in face inclusions.^[6]^[6] The k-th homology group is H_k(K) = \ker(\partial_k) / \operatorname{im}(\partial_{k+1}), where \ker(\partial_k) is the subgroup Z_k(K) of k-cycles (chains with zero boundary) and \operatorname{im}(\partial_{k+1}) is the subgroup B_k(K) of k-boundaries (chains that are boundaries of (k+1)-chains). Thus, H_k(K) classifies cycles up to boundaries, measuring the number of independent k-dimensional holes in K. The rank of the free part of H_k(K), known as the k-th Betti number \beta_k(K), quantifies these holes for finite complexes.^[6]^[6]^[6] A fundamental relation links the homology of K to its combinatorial structure via the Euler characteristic \chi(K) = \sum_{k \geq 0} (-1)^k f_k, where f_k is the number of k-simplices in K. By the properties of chain complexes, this equals \sum_{k \geq 0} (-1)^k \beta_k(K), providing a topological invariant computable from either the face counts or the Betti numbers.^[6]^[6]

Triangulation of Topological Spaces

A triangulation of a topological space X is a pair consisting of a simplicial complex K and a homeomorphism h: |K| \to X, where |K| denotes the geometric realization of K.^[17] This construction allows general topological spaces to be approximated or exactly represented by simplicial complexes, provided X is triangulable, meaning such a pair exists. Not all topological spaces admit triangulations; for instance, certain pathological spaces constructed via the Axiom of Choice fail to be triangulable. While polyhedra are triangulable by definition, not all compact manifolds admit triangulations; counterexamples exist in dimensions ≥4.^[17]^[18] Simplicial manifolds arise as triangulations of topological manifolds, where the simplicial complex is pure, meaning all maximal simplices (facets) have the same dimension d-1, and the link of every nonempty face is homeomorphic to either a simplex or the boundary of a simplex of the appropriate dimension.^[19] This ensures the geometric realization is a piecewise linear (PL) manifold, with constant dimension throughout. Such structures are fundamental for studying manifold topology via combinatorial methods, as the purity condition guarantees a uniform dimensionality that aligns with the manifold's intrinsic dimension.^[20] The Hauptvermutung, formulated by Steinitz and Tietze in 1908, conjectured that any two triangulations of a polyhedron or compact PL manifold are combinatorially equivalent, meaning they admit a common subdivision via simplicial isomorphism, or equivalently, that homeomorphic simplicial complexes are PL homeomorphic.^[17] This uniqueness holds in low dimensions: for dimensions at most 3, every topological manifold admits a unique PL structure up to isomorphism, and triangulations are unique up to simplicial equivalence.^[21] However, the conjecture was resolved negatively in higher dimensions; for manifolds of dimension 5 and above, Kirby and Siebenmann showed in 1969 that topological manifolds may not admit PL triangulations at all, and when they do, the triangulation is not unique due to obstructions like the Kirby-Siebenmann invariant in H^4(M; \mathbb{Z}_2).^[17] Milnor's 1961 counterexamples for polyhedra further demonstrated non-uniqueness using Whitehead torsion.^[21] A classic example is the 2-sphere S^2, which admits a minimal triangulation as the boundary complex of a 3-simplex, consisting of 4 vertices, 6 edges, and 4 triangular faces.^[2] This simplicial complex is pure of dimension 2, with links of vertices being circles (1-spheres) and the entire realization homeomorphic to S^2. Another illustrative case is the dunce hat, a contractible 2-dimensional simplicial complex that is not collapsible—meaning it cannot be reduced to a point via elementary collapses—despite being homotopy equivalent to a point; a minimal such triangulation has 8 vertices, 24 edges, and 17 faces.^[22] Triangulations like these preserve key topological invariants, such as simplicial homology groups, allowing algebraic tools to distinguish non-homeomorphic spaces.^[2]

Combinatorial Properties

Enumeration and Polytopes

The enumeration of simplices in a simplicial complex K is captured by the f-polynomial f_K(t) = \sum_k f_k t^{k+1}, where f_k denotes the number of k-simplices in K.^[23] This generating function encodes the face counts of the complex, providing a compact way to analyze its combinatorial structure; for instance, the coefficient of t^{k+1} directly gives the number of k-simplices.^[24] In practice, evaluating f_K(t) reveals patterns in the distribution of faces, such as in flag complexes where higher-dimensional simplices are determined by clique counts in the underlying graph.^[25] Simplicial polytopes arise as geometric realizations of abstract simplicial complexes, defined as the convex hull of a finite set of points in \mathbb{R}^d such that every face is a simplex.^[26] These polytopes are characterized by having all facets as (d-1)-simplices, ensuring a triangulation-like boundary structure without additional vertices on edges or faces.^[27] Notably, simplicial polytopes are dual to simple polytopes, where the dual interchanges vertices and facets while preserving combinatorial type; for example, the dual of a simplex is itself, highlighting self-duality in such cases.^[28] This duality facilitates enumerative studies, as the f-vector of a simplicial polytope corresponds to the vertex-face incidences of its simple dual.^[29] For simplicial spheres—combinatorially equivalent to the boundary of a d-simplex—the Dehn-Sommerville relations impose linear constraints on the h-vector (h_0, h_1, \dots, h_d), derived from the f-vector via h_i = \sum_{j=0}^i (-1)^{i-j} \binom{d-j}{i-j} f_{j-1}.^[30] A key relation is the symmetry h_i = h_{d-i} for $0 \leq i \leq d, reflecting the Euler characteristic and topological invariance of the sphere.^[31] These equations, first established for polytopal spheres, extend to general simplicial spheres and ensure that the face numbers satisfy the topology of S^{d-1}.^[32] They provide essential bounds in enumerative combinatorics, linking basic counting to deeper structural properties like those in f- and h-vectors. Enumerative examples illustrate these concepts vividly. For n points in general position in the plane (no three collinear), the number of triangulations—maximal simplicial complexes on those vertices—grows exponentially, with upper bounds of O(43^n) derived from probabilistic methods.^[33] In the special case of n points in convex position, forming an n-gon, the exact count is the (n-2)-th Catalan number C_{n-2} = \frac{1}{n-1} \binom{2n-4}{n-2}, which enumerates all possible triangulations by non-crossing diagonals.^[34] For small n, such as n=4 (a quadrilateral), there is C_2 = 2 triangulations, scaling to C_5 = 42 for n=7, underscoring the rapid growth central to Catalan number applications in simplicial enumeration.^[35]

f-Vectors and h-Vectors

The f-vector of a simplicial complex K of dimension at most d is the sequence (f_0(K), f_1(K), \dots, f_d(K)), where f_i(K) denotes the number of i-dimensional faces (simplices) in K.^[36] This vector provides a fundamental combinatorial invariant that encodes the distribution of faces across dimensions, with f_0(K) counting the vertices and f_d(K) the maximal faces if K is pure.^[36] Associated to the f-vector is the h-vector h(K) = (h_0(K), h_1(K), \dots, h_d(K)), obtained via

h_i(K) = \sum_{j=0}^i (-1)^{i-j} \binom{d-j}{i-j} f_{j-1}(K),

with the convention f_{-1}(K) = 1 for the empty face.^[37] This transformation linearizes certain combinatorial relations and facilitates the study of algebraic properties, such as those arising from the Stanley-Reisner ring of K.^[38] The Upper Bound Theorem characterizes the maximal possible entries of the f-vector for simplicial spheres. For a (d-1)-dimensional simplicial sphere with v vertices, the number of k-faces satisfies f_k \leq f_k(\partial C(v, d)) for $0 \leq k \leq d-1, where \partial C(v, d) denotes the boundary complex of the cyclic d-polytope with v vertices, which achieves the maximum.^[39] This bound, originally conjectured by McMullen and Walkup for polytopes and extended to spheres, was proved by Stanley using the Cohen-Macaulay property of the associated face ring, implying that the h-vector entries h_i for i \leq \lfloor d/2 \rfloor match those of the cyclic polytope.^[39] The theorem highlights the extremal role of cyclic polytopes in face enumeration among sphere-like complexes. A key structural condition implying strong properties of the h-vector is shellability. A pure d-dimensional simplicial complex K is shellable if its maximal faces (facets) admit an ordering F_1, F_2, \dots, F_m such that for each j \geq 2, the intersection F_j \cap (\bigcup_{i=1}^{j-1} F_i) is a (d-1)-dimensional face of F_j.^[38] Shellable complexes are Cohen-Macaulay over any field, which ensures that the h-vector is positive (all h_i > 0) and unimodal, meaning h_0 \leq h_1 \leq \dots \leq h_{\lfloor d/2 \rfloor} \geq \dots \geq h_d.^[38] This unimodality reflects symmetry and growth patterns in the face counts, with shellability providing a combinatorial certificate for these algebraic traits; for example, the boundary of a simplicial polytope is always shellable.^[38]

Computational Aspects

Algorithms for Construction

Simplicial complexes can be represented using various data structures tailored to efficient storage and manipulation of their simplices and incidences. Incidence-based structures, such as the incidence graph, encode all simplices along with their boundary relations, enabling optimal retrieval of immediate faces and cofaces for computing chains and boundaries.^[40] Adjacency-based structures, like the indexed data structure with adjacencies, store top-dimensional simplices with vertex and adjacency relations, which is compact for manifold-like complexes and supports quick navigation between adjacent faces.^[40] For algebraic computations involving chains, boundary matrices represent the boundary operator as a matrix where columns correspond to oriented simplices and rows to their faces, with entries indicating incidence signs; this facilitates linear algebra operations over the chain complex. Constructing simplicial complexes from geometric data often relies on triangulation algorithms for point sets in Euclidean space. The Delaunay triangulation of a finite point set in \mathbb{R}^d produces a simplicial complex where each simplex's circumsphere contains no other points, maximizing the minimum angle and ensuring a well-shaped mesh; it can be computed in expected O(n \log n) time in fixed dimensions using randomized incremental algorithms, though worst-case time can be higher (e.g., O(n^2) in 3D).^[41] For metric spaces, alpha complexes form a subcomplex of the Delaunay triangulation filtered by a parameter \alpha > 0, including those simplices whose filtration value (squared circumradius if the circumsphere is empty, or the minimum filtration value of its codimension-1 cofaces otherwise) is at most \alpha; this construction yields shapes that approximate the topology of the point cloud's underlying space.^[42] Combinatorial methods allow building new simplicial complexes from existing ones without geometric input. The cone over a simplicial complex K with apex vertex v not in K adds all simplices of the form \{v\} \cup \sigma for \sigma \in K, resulting in a contractible complex whose boundary is K; this operation increases the dimension by one and preserves homotopy type up to suspension. The join of two simplicial complexes K and L on disjoint vertex sets combines them by including all simplices \sigma \cup \tau where \sigma \in K and \tau \in L, yielding a complex whose geometric realization is the topological join, which is homotopy equivalent to the suspension of the smash product of the realizations. A practical application of these constructions arises in persistent homology, where the Vietoris-Rips complex of a point set is built incrementally by adding simplices as the filtration parameter increases, connecting vertices within distance $2r; efficient algorithms exploit ordered edge insertions to update the complex in near-linear time per step, enabling analysis of evolving topology in streaming data. Practical implementations of these algorithms are available in libraries such as GUDHI (as of 2025) for persistent homology and alpha complexes, and CGAL for Delaunay triangulations.^[43]

Complexity of Isomorphism and Embedding

The problem of determining whether two abstract simplicial complexes are isomorphic—meaning there exists a bijection between their vertex sets that preserves the face structure—is graph isomorphism-complete in general. This hardness follows from the equivalence between graph isomorphism and the isomorphism problem for flag complexes, which are simplicial complexes whose faces correspond exactly to the cliques of an underlying graph; since flag complexes form a subclass of all simplicial complexes, the general case inherits the computational difficulty. ^[44] Hypergraph isomorphism, to which simplicial complex isomorphism reduces in polynomial time (by treating all faces as hyperedges), is likewise graph isomorphism-complete, confirming the result. ^[45] For simplicial complexes of fixed dimension d, the problem remains graph isomorphism-hard, as even the case d=1 (graphs) is complete for this class, though practical algorithms like the Weisfeiler–Leman method can solve instances quasi-polynomially in the number of vertices. The embeddability problem, which asks whether a given simplicial complex admits a piecewise linear embedding into Euclidean space \mathbb{R}^d without self-intersections, is NP-hard for d \geq 3. Specifically, deciding embeddability of 2- or 3-dimensional complexes into \mathbb{R}^3 is NP-hard, with the proof relying on reductions from 3-SAT via constructions that encode satisfiability constraints into linking conditions of cycles. ^[46] More broadly, the problem is NP-hard for every pair of dimensions (k, d) where a k-dimensional complex is embedded into \mathbb{R}^d with d \leq 3k/2 - 1, highlighting the intrinsic geometric constraints. ^[47] This hardness has implications for manifold learning algorithms, where simplicial complexes approximate data manifolds, and deciding low-distortion embeddings relates to dimensionality reduction tasks like Isomap, but exact embeddability remains computationally intractable even for sparse complexes. ^[48] Testing whether two simplicial complexes are homeomorphic—their geometric realizations are topologically equivalent—is undecidable in high dimensions. For d \geq 4, the homeomorphism problem for d-dimensional simplicial complexes is algorithmically undecidable, as shown by reductions from the word problem in finitely presented groups via constructions of complexes whose fundamental groups encode the undecidable halting problem. ^[47] In contrast, for low dimensions (d \leq 3), the problem is decidable; in dimension 2, it reduces to classifying surfaces via Euler characteristic and homology, computable in polynomial time relative to the input size (number of simplices). ^[49] Homology groups provide a polynomial-time invariant for initial screening in low dimensions, as they can be computed via matrix reduction over finite fields in time polynomial in the number of simplices for fixed d, though full homeomorphism requires additional invariants like Reidemeister torsion. ^[50] As an example of related decision problems, recognizing whether a given simplicial complex is collapsible—meaning it can be reduced to a point via a sequence of elementary collapses removing free faces—is NP-complete, even restricted to 3-dimensional complexes. Membership in NP follows from guessing and verifying a collapse sequence in polynomial time, while hardness arises from reductions from 3-SAT, encoding clauses into non-collapsible obstructions like unremovable cycles. ^[51] This contrasts with 2-dimensional complexes, where collapsibility is recognizable in linear time via greedy algorithms that always succeed if possible. ^[52]

References

[1]
[PDF] Introduction to simplicial complexes - UCI Mathematics
Definition 2.1 (simplicial complex). A simplicial complex K is a collection of simplices such that. (1) If K contains a simplex σ, then K also contains every ...Missing: scholarly sources
[2]
[PDF] 3 Simplicial Complexes - Stanford Computer Graphics Laboratory
With simplicial complexes, we separate the topology of a space from its geometry, much like the separation of syntax and semantics in logic. Given the finite ...
[3]
[PDF] arXiv:2104.02131v3 [physics.soc-ph] 6 Dec 2021
Dec 6, 2021 · The simple definition – a simplicial complex is a collection of nonempty subsets of a finite set containing all the singletons (vertices) and ...Missing: scholarly sources
[4]
Co-occurrence simplicial complexes in mathematics: identifying the ...
Aug 28, 2018 · A simplicial complex is a collection K of simplices such that if σ∈K and τ⊂σ then τ∈K, so for every simplex in K all its faces are also in K.
[5]
[PDF] Algebraic Topology - Cornell Mathematics
This book was written to be a readable introduction to algebraic topology with rather broad coverage of the subject. The viewpoint is quite classical in ...
[6]
[PDF] Applied Algebraic Topology Notes - Zvi Rosen
D. Definition 4.17. A (geometric) simplicial complex is a collection K = {Sa} of simplices, such that (1) If T ≤ S, S ∈ K ⇒ T ∈ K. (2) If S1,S2 ∈ K then S1 ∩ S ...
[7]
[PDF] Notes For Algebraic Methods in Combinatorics
To define geometric simplicial complexes, we first need to recall the definition of a geometric simplex. Definition 1.3. A geometric k-simplex ∆k is the ...
[8]
The Geometric Realization of a Semi-Simplicial Complex - jstor
Let K(7r, n) denote the Eilenberg MacLane semi-simplicial complex (see. [1]). Since K(r, n) is an abelian group complex we have: COROLLARY. If ir is a countable ...
[9]
[PDF] 15 Cell Complexes: Definitions - Jeff Erickson
3 The simplices in ∆ are called its cells. For example, the set of faces of any simplex define a simplicial complex. 1A pure abstract simplicial complex M is a ...
[10]
[PDF] 6 Simplicial complexes
Figure 6.1: A 0-simplex is a point or vertex, a 1-simplex is an edge, a 2-simplex is a triangle, and a 3-simplex is a tetrahedron. Simplicial complexes. We ...
[11]
[PDF] pdf - Introduction to Computational Topology Notes
We now relate this abstract set-theoretic definition to the geometric one by extracting the combinatorial structure of a (geometric) simplicial complex.
[12]
[PDF] III.1 Simplicial Complexes - Duke Computer Science
An abstract simplicial complex is a finite collection of sets A such that α ∈ A and β ⊆ α implies β ∈ A. The sets in A are its simplices. The dimension of a ...<|control11|><|separator|>
[13]
[PDF] Poset Topology: Tools and Applications - University of Miami
To every simplicial complex ∆, one can associate a poset P(∆) called the face poset of ∆, which is defined to be the poset of nonempty faces ordered by ...
[14]
[PDF] CS 7301.003.20F Lecture 22—November 2, 2020
The boundary partial sigma of an oriented k-simplex sigma is a (k - 1)-chain, defined as a weighted sum of facets of sigma: partial[x_0, x_1, …, x_k] := sum ...
[15]
[PDF] Foundations of Algebraic Topology
The Topology of Fibre Bundles. By NORlIlAN S'fHNROD. 16. Foundations of Algebraic Topology. By SAMUEL ElLENBERG and NORMAN STEEN-. ROD.
[16]
[PDF] Simplicial Complexes - People @EECS
Feb 4, 1999 · Equivalently, it is the intersection of all half- spaces that contain S. A simplex is the convex hull of a set of a. i. points. If S Rd is a ...
[17]
[PDF] Simplicial Complexes - Inria
Simplicial Complexes. 28 / 1. Page 39. Stars and links. Let K be a simplicial complex with vertex set P. The star of p ∈ P is the set of simplices of K that ...
[18]
None
### Summary of Definitions and Properties from Lecture 01 Complexes
[19]
[PDF] COMPUTATIONAL ALGEBRAIC TOPOLOGY - People
we are given a universal finite set V of vertices, and we may select any ...
[20]
[PDF] Simplicial Complexes: Theory and Implementation - DTU
Aug 25, 2011 · Carrier. Definition. The carrier kKk of a simplicial complex K (also called the polyhedron kKk) is a subset of En defined by the union, as ...
[21]
[PDF] Math 535, Homework 1, due Oct 1
(1) If ∆ is a finite simplicial complex on vertex set V , and S ⊆ V , then the induced subcomplex on S (denoted ∆[S]) is the simpli- cial complex with ...
[22]
[PDF] 10. Simplicial Complexes
Because barycentric coordinates are unique, every point in ∆n[S] is contained in the interior of a unique subsimplex,. ∆m[{vi0 ,...,vim }] ⊂ ∆n[S]. The ...
[23]
[PDF] The Hauptvermutung Book - The University of Edinburgh
The Hauptvermutung is the conjecture that any two triangulations of a poly- hedron are combinatorially equivalent. The conjecture was formulated at the turn.
[24]
[PDF] Face enumeration on simplicial complexes - UW Math Department
A simplicial manifold ∆ is a piecewise linear (PL) manifold if the link of each nonempty face of ∆ is PL-homeomorphic to a simplex or to the boundary of a ...
[25]
[PDF] LVMB manifolds and simplicial spheres - Annales de l'institut Fourier
If a complex K is pure-dimensional (or simply pure), the simplices of maximal dimension d are named facets and the faces of dimension 0 (resp. d−1) are the ...
[26]
[PDF] On the Hauptvermutung
A simplicial complex K is finite if and only if the polyhedron |K| is compact. The Hauptvermutung is only considered here for compact polyhedra. However, the.
[27]
[PDF] The dunce hat in a minimal non-extendably collapsible 3-ball - arXiv
Jan 28, 2013 · Non-evasive complexes are collapsible [21]; hence the 8-vertex dunce hat D is evasive. It is proven in [21] that a simplicial complex is evasive ...
[28]
[PDF] 1. f-polynomials and h-polynomials - Raco.cat
Given a finite simplicial complex L as above, denote by S(L) the set of simplices in L together with the empty set ∅. Let v1,v2,...,vn be the vertices of L and ...
[29]
[PDF] arXiv:math/0501046v1 [math.CO] 4 Jan 2005
Jan 4, 2005 · There is a classical problem: what can be said in general about the f-polynomials of (a certain class of) simplicial complexes?
[30]
[PDF] Independence Complexes of Certain Families of Graphs - KTH
f-polynomial and Euler Characteristic. The ˜f-polynomial of a simplicial complex tells us how many faces of each dimension the complex consists of. In this ...
[31]
[PDF] CONVEX POLYTOPES
A dual of a simplicial polytope is called simple. A simplex is an example of a self-dual polytope; many other such polytopes are known. A dual of a d-cube ...
[32]
[PDF] Polytopes Course Notes - Mathematics
Simplicial polytopes are dual to simple polytopes, and (a0,...,ad−1) is the f-vector of some simplicial d-polytope if and only if (ad−1,...,a0) is the f ...
[33]
[PDF] polytopes.pdf
The faces of a given polytope pn form a partially ordered set(poset) with respect to inclusion, called face poset of p". Note: The one skeleton of pr. 45 a.
[34]
[PDF] The merging operation and (d − i)-simplicial i-simple d-polytopes
May 10, 2024 · A d-polytope P is called i-simplicial if all of its i-faces are simplices, and it is i-simple if its dual P∗ is i-simplicial (equivalently, if ...
[35]
Generalized Dehn-Sommerville relations for polytopes, spheres and ...
Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets. Published: February 1985. Volume 79, pages 143–157, (1985) ...
[36]
[PDF] revisiting generalizations of the dehn–sommerville relations
In their simpler form, for instance for simplicial polytopes or simplicial spheres, the. Dehn–Sommerville relations can be stated as: fk−1 = d. C i=k. (−1) d ...
[37]
[PDF] Generalized Dehn-Sommerville Relations for Polytopes, Spheres ...
This paper generalizes the Dehn-Sommerville equations for simplicial spheres to related classes of objects. The underlying motivation is to understand the ...
[38]
[PDF] The Number of Triangulations on Planar Point Sets - Ethz
We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such ...
[39]
[PDF] Math 4707 The Catalan Nunbers
Theorem 2. The number of triangulations of a polygon with n + 2 sides into n triangles is Cn. Proof. We prove this be showing that triagulations satisfy the ...
[40]
[PDF] Catalan Numbers - Cornell Mathematics
Triangulations. An n-sided polygon, or n-gon for short, is obtained by connecting n distinct points (again called vertices) on a circle ...
[41]
[PDF] 17 FACE NUMBERS OF POLYTOPES AND COMPLEXES - CSUN
The convex hull of any set of j + 1 affinely independent points in Rn is called a j-simplex. See Chapter 15 for more about this definition, and for the notions.
[42]
https://gudhi.inria.fr/doc/3.7.0/group__alpha__complex.html
[43]
[PDF] Algebraic h-vectors of simplicial complexes through local ... - arXiv
Jul 29, 2019 · Associated to every finite simplicial complex ∆ is the notion of its h-vector, which is one way of encoding the number of faces that ∆ has in ...
[44]
[PDF] The Upper Bound Conjecture and Cohen-Macaulay rings
The special case of Klee's conjecture when |A| is a sphere is known as the UBC for spheres (sometimes called the “UBC for simplicial spheres” or the “UBC for ...
[45]
[PDF] Data structures for simplicial complexes: an analysis and a ...
The domain, or carrier, of a Euclidean simplicial d-complex Σ ... All four data structure are able to support the retrieval of all topological relations.
[46]
[PDF] Two-dimensional Delaunay triangulations - People @EECS
Oct 25, 2012 · A triangulation of S is a simplicial complex T such that S is the set of vertices in T, and the union of all the simplices in T is the convex ...
[47]
Homeomorphism of 2-Complexes is Graph Isomorphism Complete
Homeomorphism of 2-complexes is graph isomorphism complete. Proof. We must show that homeomorphism of 2-complexes is equivalent to graph iso- morphism ...
[48]
[PDF] Colored Hypergraph Isomorphism is Fixed Parameter Tractable
X0. Graph. Isomorphism (GI) is obviously polynomial-time reducible to HI. Conversely, HI is also known to be polynomial-time reducible to GI: Given a pair ...
[49]
Embeddability in R3 is NP-hard | Journal of the ACM
Jun 4, 2020 · Abstract. We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R3 is NP-hard.
[50]
[PDF] Hardness of embedding simplicial complexes in Rd - arXiv
Apr 22, 2009 · Our NP-hardness results are probably not the final word on the computational complexity of the corresponding embeddability problems; for example ...
[51]
Hierarchical simplicial manifold learning | PNAS Nexus
In this article, we propose a hierarchical simplicial manifold learning algorithm, constituted by nested clustering and topological reduction, for constructing ...
[52]
[PDF] Undecidability everywhere - MIT Mathematics
Mar 28, 2008 · In fact, the homeomorphism problem is known to be decidable in dimensions ≤ 3, and undecidable in dimensions ≥ 4. Page 17. Undecidability.
[53]
Complexity of simplicial homology and independence complexes of ...
The computational complexity of the problem depends on the input type T which determines how the simplicial complex K is represented. We will now discuss ...
[54]
Recognition of collapsible complexes is NP-complete - arXiv
Nov 27, 2012 · Abstract:We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible.Missing: recognizing coNP-
[55]
[PDF] How to collapse a simplicial complex - Giovanni Paolini
Dec 1, 2020 · Collapsibility of a 2-dimensional simplicial complex is solvable in linear time. Collapse greedily. If you get stuck, the complex is not ...<|control11|><|separator|>