Simplicial Complexes

From Graphs to Higher Dimensions

A plane graph has vertices, edges, and faces, which are objects of dimension 0, 1, and 2. In Planar Graphs & Euler's Formula, the interplay among these three types of objects produced Euler's formula \(V - E + F = 2\), a topological invariant that depends only on the surface of embedding. In Incidence Structure & Cycle/Cut Spaces, we encoded the relationship between vertices and edges algebraically through the oriented incidence matrix \(\boldsymbol{B}\), which coincides with the boundary operator \(\partial_1\) up to an overall sign.

We now generalize both ideas simultaneously. A \(k\)-simplex is the \(k\)-dimensional analogue of a vertex (\(k=0\)), an edge (\(k=1\)), or a filled triangle (\(k=2\)), and a simplicial complex is a space assembled from simplices of various dimensions, glued together along their faces.

Simplicial complexes are the gateway to algebraic topology. We replace continuous spaces with combinatorial skeletons built from simplices, and we then apply kernels, images, and quotients from linear algebra to extract topological information. The payoff will come in the sequel on Homology, where we measure "holes" of each dimension by computing \(H_k = \ker \partial_k / \operatorname{im} \partial_{k+1}\).

The \(k\)-Simplex

The coordinates \((\lambda_0, \lambda_1, \dots, \lambda_k)\) satisfying the constraints above are called barycentric coordinates. They give every point in the simplex as a weighted average of the vertices, with non-negative weights summing to one.

The low-dimensional cases are familiar:

• A 0-simplex is a single point (vertex).
• A 1-simplex is a line segment (edge).
• A 2-simplex is a filled triangle.
• A 3-simplex is a solid tetrahedron.

The affine-independence condition ensures that the simplex does not degenerate. A 2-simplex requires three non-collinear points, a 3-simplex requires four non-coplanar points, and so on. A \(k\)-simplex lives in an ambient space of dimension at least \(k\).

Faces

A \(k\)-simplex has exactly \(\binom{k+1}{j+1}\) faces of dimension \(j\), for \(0 \leq j \leq k\). In total, it has \(2^{k+1} - 1\) non-empty faces (every non-empty subset of the \(k+1\) vertices defines a face). For instance, a 2-simplex \([v_0, v_1, v_2]\) has three 0-faces (the vertices), three 1-faces (the edges \([v_0, v_1]\), \([v_0, v_2]\), \([v_1, v_2]\)), and itself as the unique 2-face, for seven faces in all.

Abstract Simplicial Complexes

Just as a graph can be studied as a purely combinatorial object \(G = (V, E)\) without reference to any embedding in \(\mathbb{R}^d\), simplicial complexes admit a purely combinatorial formulation.

The face condition (also called the downward closure or hereditary property) is the defining constraint. If a filled triangle \(\{a, b, c\}\) is in \(K\), then all three of its edges \(\{a,b\}\), \(\{a,c\}\), \(\{b,c\}\) and all three of its vertices must also be in \(K\). There is no "floating" high-dimensional simplex without its skeleton.

Graphs as 1-Dimensional Complexes

Every simple graph \(G = (V, E)\) is naturally an abstract simplicial complex \(K_G\) whose dimension is at most 1 (exactly 1 when \(E \neq \emptyset\)). The simplices of \(K_G\) are the singletons \(\{v\}\) for \(v \in V\) (the 0-simplices) and the edges \(\{u, v\}\) for \(\{u,v\} \in E\) (the 1-simplices). The face condition holds trivially, since every edge contains its two endpoints. From this viewpoint, the graph theory we have developed so far, from basic structure through trees, planarity, and incidence structure, is the theory of 1-dimensional simplicial complexes.

The passage from graphs to higher-dimensional complexes is the passage from recording only pairwise relationships (\(\{u,v\} \in E\)) to recording higher-order relationships. A 2-simplex \(\{a, b, c\}\) asserts that \(a\), \(b\), and \(c\) participate in a simultaneous three-way interaction, not merely three separate pairwise ones. This distinction is invisible to a graph but central to the topology of the complex.

Geometric Realization

An abstract complex can always be embedded geometrically.

The proof places the vertices on the moment curve \(t \mapsto (t, t^2, \dots, t^{2d+1})\) at distinct parameter values. The Vandermonde structure of this curve guarantees that any \(2d + 2\) or fewer points on it are in general position, so every \(d\)-simplex in \(K\) is non-degenerate. Moreover, since two simplices in \(K\) have total vertex count at most \(2d + 2\) and therefore sit in general position together, their convex hulls intersect exactly in the convex hull of their common vertices, that is, in their common face (and they are disjoint if they share no vertex). Hence the geometric realization is well-defined as a simplicial complex.

For our purposes, the theorem guarantees that no generality is lost in working abstractly. Every abstract complex has a concrete geometric manifestation, and all topological invariants (Euler characteristic, homology groups) can be computed from the combinatorics alone.

Constructing Complexes from Data

In combinatorics, simplicial complexes arise by declaring which higher-order interactions exist. In applications, particularly Topological Data Analysis (TDA), we start with raw data (a point cloud, a graph, a metric space) and construct a simplicial complex from it. The three constructions below are the workhorses of the field.

The Clique Complex (Flag Complex)

The clique complex is "maximally filled". It contains a \(k\)-simplex whenever all \(\binom{k+1}{2}\) pairwise edges are present. No independent judgment about higher-order interactions is needed, since they are inferred from pairwise data. This makes the clique complex the cheapest way to lift a graph into a simplicial complex, but also the most aggressive, because it creates high-dimensional simplices wherever complete subgraphs occur.

The Vietoris-Rips Complex

The Vietoris-Rips complex converts a point cloud into a simplicial complex using a single parameter \(\varepsilon\). We connect points that are close and then fill in all cliques. It is computationally convenient because membership in the complex is determined entirely by pairwise distances, so no higher-order geometric tests are needed.

The Čech Complex

The Čech complex has a deep topological justification via the Nerve Theorem of algebraic topology. Every ball \(B(x, \varepsilon/2)\) is convex, so every non-empty intersection of finitely many of them is convex and hence contractible (continuously deformable to a point). In other words, the balls form a good cover of their union. The Nerve Theorem asserts that the nerve of a good cover (the complex whose simplices are the collections of sets in the cover with a common point), which here is exactly \(\check{C}(X, \varepsilon)\), is homotopy equivalent to the union \(\bigcup_{x \in X} B(x, \varepsilon/2)\). Thus the Čech complex captures the "true" topology of the thickened point cloud. (We state this without proof. The result is foundational in computational topology.)

However, the intersection test is more expensive than the pairwise-distance test of the Rips complex, since checking whether \(k+1\) balls have a common point requires geometric computation beyond pairwise distances.

For a finite \(X \subset \mathbb{R}^d\) with the Euclidean distance and any \(\varepsilon \gt 0\), the Čech and Rips complexes satisfy the inclusions \[ \check{C}(X, \varepsilon) \subseteq \operatorname{VR}(X, \varepsilon) \subseteq \check{C}(X, 2\varepsilon), \] so the Rips complex sandwiches the Čech complex at comparable scales. The first inclusion follows from the triangle inequality. If \(\sigma \in \check{C}(X, \varepsilon)\), some point \(p\) lies within distance \(\varepsilon/2\) of every point of \(\sigma\), so any two points of \(\sigma\) lie within distance \(\varepsilon/2 + \varepsilon/2 = \varepsilon\) of each other. The second follows from observing that, for \(\sigma \in \operatorname{VR}(X, \varepsilon)\), any vertex of \(\sigma\) is itself a common point of the balls of radius \(\varepsilon\) centered at the other vertices. In practice, the Rips complex is preferred for computation, and the Čech complex provides the theoretical guarantee.

Filtrations and Persistence

For a fixed \(\varepsilon\), the Rips and Čech complexes produce a single snapshot. The central idea of TDA is to vary \(\varepsilon\) continuously and track how the topology changes.

As \(\varepsilon\) increases from 0, new edges and higher-dimensional simplices are born, connected components merge, loops form and are later filled in by 2-simplices. Persistent homology, which we take up once homology groups are available, tracks the "birth" and "death" of each topological feature across the filtration, recording the result in a persistence diagram. Features that persist over a long range of \(\varepsilon\) are considered genuine topological signal, while short-lived features are noise. This is the mathematical foundation of modern TDA pipelines.

The f-vector and Euler Characteristic

In Planar Graphs, we defined the Euler characteristic of a plane graph as \(\chi = V - E + F\), which equals 2 for every connected plane graph, counting objects of dimension 0 (vertices), 1 (edges), and 2 (faces) with alternating signs. Simplicial complexes have objects at every dimension, and the same alternating-sign pattern generalizes naturally.

The f-vector

For a graph \(G = (V, E)\) viewed as a 1-complex, the f-vector is simply \((|V|, |E|)\). For a triangulated surface, the f-vector is \((V, E, F)\), the counts that appear in Euler's formula.

The Euler Characteristic of a Complex

For the boundary of the tetrahedron: \(\chi = 4 - 6 + 4 = 2\). This agrees with Euler's formula for the sphere, as it must, because the boundary of a tetrahedron is homeomorphic to \(S^2\). For a graph (1-complex) with \(c\) connected components, \(\chi = V - E\). The dimension formula from Cycle/Cut Spaces gives \(\dim Z_1 = E - V + c\), so \[ \chi = V - E = c - \dim Z_1. \] When the graph is connected, \(\chi = 1 - \dim Z_1\). In this case the Euler characteristic detects the cycle rank.

The Euler characteristic is a topological invariant. If two complexes are homeomorphic (as topological spaces via their geometric realizations), they have the same \(\chi\). This statement has non-trivial content. Although \(\chi\) is computed from a simple counting formula, it encodes deep topological information. The full explanation requires homology. The Euler-Poincaré theorem on the next page will show that \(\chi(K) = \sum_{k} (-1)^k \beta_k\), where \(\beta_k = \dim H_k\) are the Betti numbers. Homology groups are themselves topological invariants (a deep theorem that we state without proof), so the alternating sum of the Betti numbers is a topological invariant as well.

Orientation and the Boundary Operator

In the previous page, we oriented edges and defined the incidence matrix \(\boldsymbol{B}\), which agrees up to sign with the boundary operator \(\partial_1\) from 1-chains (edge space) to 0-chains (vertex space). We now generalize. An oriented \(k\)-simplex carries a sign determined by the ordering of its vertices, and the boundary operator \(\partial_k\) maps \(k\)-chains to \((k-1)\)-chains by removing one vertex at a time, with alternating signs.

Oriented Simplices

In Combinatorics, we studied the sign (parity) of permutations. Even permutations preserve orientation, and odd permutations reverse it. For an edge (\(k=1\)), there are two orderings of the two vertices, and \([a, b] = -[b, a]\), since a transposition is an odd permutation. This is exactly the orientation convention we used for edges. Choosing \(a \to b\) versus \(b \to a\) differs by a sign.

For a 2-simplex (triangle), the six orderings of \(\{a, b, c\}\) split into two orientation classes: \[ \begin{align*} +[a,b,c] &= [b,c,a] = [c,a,b], \\\\ -[a,b,c] &= [b,a,c] = [a,c,b] = [c,b,a]. \end{align*} \] If \(a\), \(b\), \(c\) are placed counterclockwise in a plane embedding, the positive class corresponds to the counterclockwise traversal of the triangle and the negative class to the clockwise one. The choice is a convention. The essential point is that once we fix an orientation for each simplex, the boundary operator is well-defined.

The Boundary Operator

The formula is computed from one ordering of the vertices, so we must check that it respects the sign convention for oriented simplices. Swap two adjacent vertices \(v_j\) and \(v_{j+1}\). For \(i \neq j, j+1\), the face obtained by omitting \(v_i\) keeps its coefficient \((-1)^i\) but now lists \(v_j\) and \(v_{j+1}\) in the opposite order, so it changes sign. Omitting the vertex in position \(j\) of the swapped ordering removes \(v_{j+1}\) and produces the face that previously carried the coefficient \((-1)^{j+1}\), now with the coefficient \((-1)^j\). The same happens for position \(j+1\), so the two faces that omit \(v_j\) or \(v_{j+1}\) also change sign. Hence swapping two adjacent vertices negates \(\partial_k \sigma\). Since every permutation is a product of adjacent transpositions and the sign of a permutation is multiplicative, we obtain \[ \partial_k [v_{\pi(0)}, \dots, v_{\pi(k)}] = \operatorname{sgn}(\pi) \, \partial_k [v_0, \dots, v_k], \] so \(\partial_k\) is well defined on oriented simplices.

Let us verify that this generalizes what we already know.

Chain Groups

The boundary operator is a linear map. To make this precise, we introduce chain groups.

For \(k = 0\), the space \(C_0 = \mathbb{R}^{f_0}\) of formal combinations of vertices is the "vertex space" \(\mathbb{R}^V\) from the previous page. For \(k = 1\), the space \(C_1 = \mathbb{R}^{f_1}\) is the edge space \(\mathbb{R}^E\). For \(k \gt \dim K\) there are no \(k\)-simplices, so \(C_k = 0\). The boundary operator is then a linear map \(\partial_k : C_k \to C_{k-1}\), defined on basis elements by the alternating-sum formula above and extended by linearity.

We equip each \(C_k\) with the inner product that makes the chosen oriented basis orthonormal. Under this convention, the matrix transpose \(\partial_k^\top\) is exactly the adjoint of \(\partial_k\), and the Laplacians defined later in this section are symmetric positive semi-definite.

Classical algebraic topology typically works over \(\mathbb{Z}\), where the homology groups can detect torsion (for example, the twisted cycle in \(\mathbb{R}P^2\)). We use \(\mathbb{R}\) throughout, which erases torsion but gives us genuine vector spaces on which inner products, spectral decompositions, and Laplacians are defined. Topological Data Analysis likewise computes over a field (in practice often a finite field such as \(\mathbb{Z}/2\mathbb{Z}\)), and real coefficients are the natural setting for Simplicial Neural Networks, the applications toward which this page is oriented.

The Chain Complex

Assembling the chain groups and boundary maps, we obtain a sequence of vector spaces connected by linear maps: \[ \begin{align*} &\cdots \xrightarrow{\partial_{k+1}} C_k \xrightarrow{\partial_k} C_{k-1} \xrightarrow{\partial_{k-1}} \cdots \\\\ &\cdots \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 \xrightarrow{\partial_0} 0. \end{align*} \] This sequence is called the chain complex of \(K\). Its most important property is the subject of the next theorem.

The Fundamental Property: \(\partial^2 = 0\)

The theorem is the non-trivial sign-cancellation result previewed for graphs. For graphs (\(k = 1\)), the composition \(\partial_0 \circ \partial_1 = 0\) was trivially true because we set \(\partial_0 = 0\). For \(k \geq 2\), the cancellation is genuine. It is the alternating signs in the boundary formula, inherited from the parity of permutations, that make every pair of omitted vertices cancel. This cancellation is the algebraic reason that "the boundary of a boundary is empty."

We verified a concrete instance above. The chain \(\partial_2[a,b,c] = [a,b] + [b,c] + [c,a]\) is a closed loop, and \(\partial_1\) of a closed loop sums to zero at every vertex. The theorem guarantees this happens in every dimension.

Matrix Representation of \(\partial_k\)

Once we choose an ordering and orientation for the simplices, each boundary operator \(\partial_k\) is represented by a matrix \([\partial_k] \in \mathbb{R}^{f_{k-1} \times f_k}\) whose entries are \(0, +1,\) or \(-1\). The matrix \([\partial_1]\) is (up to a global sign) the oriented incidence matrix \(\boldsymbol{B}\) itself. Both are \(|V| \times |E|\) matrices mapping the edge space to the vertex space, as established in the example above. The matrix \([\partial_2]\) has one column per oriented 2-simplex and one row per oriented 1-simplex, with \(\pm 1\) entries recording the incidence.

Higher-Order Laplacians

Recall the Hodge Laplacian \[ \boldsymbol{L}_k = \partial_{k+1}\partial_{k+1}^\top + \partial_k^\top \partial_k. \] We can now see where this formula comes from. The first term, \(\partial_{k+1}\partial_{k+1}^\top\), measures how a \(k\)-chain is "enclosed" by \((k+1)\)-simplices (the upper Laplacian \(L_k^{\mathrm{up}}\)). The second term, \(\partial_k^\top \partial_k\), measures how a \(k\)-chain connects to \((k-1)\)-simplices via the coboundary \(\partial_k^\top\) (the lower Laplacian \(L_k^{\mathrm{down}}\)). Together, they capture the full adjacency structure at dimension \(k\).

For \(k = 0\), the convention \(\partial_0 = 0\) gives \(\boldsymbol{L}_0 = \partial_1 \partial_1^\top\), the graph Laplacian from Graph Laplacians. For \(k = 1\), the operator \(\boldsymbol{L}_1 = \partial_2 \partial_2^\top + \partial_1^\top \partial_1\) captures the adjacency of edges through shared vertices (\(\partial_1^\top \partial_1\)) and through co-bounding triangles (\(\partial_2 \partial_2^\top\)). For every \(k\), both terms of \(\boldsymbol{L}_k\) are positive semi-definite, and \[ \boldsymbol{x}^\top \boldsymbol{L}_k \boldsymbol{x} = \|\partial_{k+1}^\top \boldsymbol{x}\|^2 + \|\partial_k \boldsymbol{x}\|^2. \] Hence \(\boldsymbol{L}_k \boldsymbol{x} = 0\) exactly when \(\partial_k \boldsymbol{x} = 0\) and \(\partial_{k+1}^\top \boldsymbol{x} = 0\). The chains in this common kernel are the harmonic chains, which are simultaneously cycles and cocycles (chains annihilated by the coboundary \(\partial_{k+1}^\top\)). The condition \(\partial^2 = 0\) makes the two terms annihilate each other, \(L_k^{\mathrm{up}} L_k^{\mathrm{down}} = 0\), because \(\partial_{k+1}^\top \partial_k^\top = (\partial_k \partial_{k+1})^\top = 0\). By the discrete Hodge theorem, the harmonic space is isomorphic to the homology group \(H_k\), connecting spectral theory to topology.