Simplicial sets

As a core feature, this package provides data structures and algorithms for a flavor of simplicial sets known as semi-simplicial sets or delta sets. The first section explains how delta sets relate to simplicial complexes and other structures. Readers not interested in these distinctions may proceed directly to the next section, on delta sets.

Varieties of simplicial stuff

A wide, possibly bewildering variety of concepts fall under the heading of "simplicial stuff," including:

  • simplicial complexes
  • abstract simplicial complexes
  • simplicial sets
  • semi-simplicial sets, aka delta sets
  • augmented simplicial sets
  • symmetric (simplicial) sets

The most familiar of these are simplicial complexes: coherent collections of $n$-simplices of different dimensions $n$ embedded in an ambient Euclidean space. A simplicial complex may include points $(n=0)$, line segments $(n=1)$, triangles $(n=2)$, tetrahedra $(n=3)$, and higher-dimensional simplices. Of the structures listed here, only simplicial complexes are geometrical objects. All of the others can be seen as combinatorial abstractions of simplicial complexes.

Abstract simplicial complexes are the oldest and most obvious abstraction of simplicial complexes, but nowadays mathematicians tend to prefer simplicial sets, which enjoy excellent algebraic properties. A simplicial set $X$ consists of sets $X_n$, for $n \geq 0$, of abstract $n$-simplices whose $n+1$ different faces are ordered and hence can be numerically indexed, via the face maps.

In this package, we implement a variant of simplicial sets called semi-simplicial sets, or delta sets for short. The difference is that delta sets contain only the face maps, whereas simplicial sets also contain degeneracy maps. The main effect of the degeneracy maps is to enlarge the space of simplicial morphisms by allowing simplices to be "collapsed" onto lower-dimensional ones. Degeneracy maps have their pros and cons, and in the future we will likely provide simplicial sets as well as semi-simplicial ones. For more details, the paper by Greg Friedman is an excellent illustrated introduction to semi-simplicial and simplicial sets.

Simplicial sets generalize graphs from one dimension to higher dimensions. The following table gives the precise correspondence between different flavors of simplicial stuff and graphs.

1-dimensional$n$-dimensional
straight-line embedded graphsimplicial complex
simple graphabstract simplicial complex
graphsemi-simplicial set
reflexive graphsimplicial set
symmetric graphsymmetric semi-simplicial set
symmetric reflexive graphsymmetric simplicial set
Note

In this table, as in this package and the rest of the AlgebraicJulia ecosystem, a graph without qualification is always a category theorist's graph (a directed multigraph), not a simple graph (an undirected graph with no self-loops or multiple edges).

Ordered faces in geometric applications

That the faces of each simplex in a simplicial set are ordered is convenient for many purposes but may seem problematic for geometric applications, where the faces usually regarded as unordered.

One solution to this problem would be to use symmetric simplicial sets, which are simplicial sets $X$ equipped with an action of the symmetric group $S_{n+1}$ on the $n$-simplices $X_n$, for every $n$. This is computationally inconvenient because every "unordered $n$-simplex" is then really an equivalence class of $(n+1)!$ different $n$-simplices, a number that grows rapidly with $n$. At this time, symmetric simplicial sets of dimension greater than 1 are not implemented in this package.

To simulate unordered simplicial sets, we instead adopt the convention of a choosing the representative of the equivalence class that orders the vertices of the simplex according to the integer IDs of the vertices. The simplicial set then "presents" a symmetric simplicial set in a canonical way. Indeed, the standard method of converting an abstract simplicial complex to a simplicial set is to pick a total ordering of its vertices. When following this convention, use the functions add_sorted_edge! and glue_sorted_triangle!, which automatically sort their inputs to ensure that the ordering condition is satisfied, rather than the functions add_edge! and glue_triangle!.

Delta sets

A delta set $X$ is a family of sets $X_n$ for $n = 0,1,2,\dots$, called the $n$-simplices, together with functions

\[X(\partial_n^i): X_n \to X_{n-1}, \qquad n \geq 1, \quad i=0,1,\dots,n,\]

called the face maps, which must satisfy the semi-simplicial identities

\[X(\partial_{n+1}^i) \cdot X(\partial_n^j) = X(\partial_{n+1}^{j+1}) \cdot X(\partial_n^i): X_{n+1} \to X_{n-1}, \qquad 0 \leq i \leq j \leq n.\]

The function $X(\partial_n^i): X_n \to X_{n-1}$ gives the face of an $n$-simplex that is opposite its $i$-th vertex. The semi-simplicial identities then ensure that the faces of each $n$-simplex fit together properly, for example, that the edges of a 2-simplex actually form a triangle.

In our implementation, the generic function supplies all the face maps of a delta set. Specifically, the function call ∂(i, n, x, k) gives the i-th face of the n-simplex in the delta set x with index k, and the call ∂(i, n, x) gives the i-faces of all n-simplices in the delta set x, which is a vector of integers.

A finite delta set—the only kind supported here—has no simplices above a certain dimension. For any fixed $N$, an $N$-dimensional delta set is a delta set $X$ such that $X_n = \emptyset$ for $n > N$. CombinatorialSpaces provides dedicated data structures for delta sets of a given dimension.

1D delta sets

Since a one-dimensional delta set is the same thing as a graph, the type DeltaSet1D has the same methods as the type Graph in Catlab.Graphs, which should be consulted for further documentation.

dset = DeltaSet1D()
add_vertices!(dset, 4)
add_edges!(dset, [1,2,2], [2,3,4])
dset
DeltaSet1D {V:4, E:3}
E ∂v0 ∂v1
1 2 1
2 3 2
3 4 2

One potentially confusing point is that the face map $\partial_1^0$ gives the target vertex (the vertex of an edge opposite vertex 0), while the face map $\partial_1^1$ gives the source vertex (the vertex of an edge opposite vertex 1).

@assert ∂(1,0,dset) == tgt(dset)
@assert ∂(1,1,dset) == src(dset)

2D delta sets

Two-dimensional delta sets, comprised of vertices, edges, and triangles, are supplied by the type DeltaSet2D. There are two ways to add triangles to a delta set. If appropriately arranged edges have already been added, a triangle having those edges as boundary can be added using the add_triangle! function. However, it often more convenient to use the glue_triangle! function, which takes vertices rather than edges as arguments, creating any boundary edges that do not already exist.

For example, the following 2D delta set has the shape of a triangulated commutative square.

dset = DeltaSet2D()
add_vertices!(dset, 4)
glue_triangle!(dset, 1, 2, 3)
glue_triangle!(dset, 1, 4, 3)
dset
DeltaSet2D {V:4, E:5, Tri:2}
E ∂v0 ∂v1
1 2 1
2 3 2
3 3 1
4 4 1
5 3 4
Tri ∂e0 ∂e1 ∂e2
1 2 3 1
2 5 3 4

As the table above illustrates, only the edges of each triangle are explicitly stored. The vertices of a triangle can be accessed using the function triangle_vertices. The correctness of this function depends on the semi-simplicial identities.

map(triangles(dset)) do t
  triangle_vertices(dset, t)
end
2-element Vector{StaticArraysCore.SVector{3, Int64}}:
 [1, 2, 3]
 [1, 4, 3]

API docs

CombinatorialSpaces.SimplicialSetsModule

Simplicial sets in one, two, and three dimensions.

For the time being, this module provides data structures only for delta sets, also known as semi-simplicial sets. These include the face maps but not the degeneracy maps of a simplicial set. In the future we may add support for simplicial sets. The analogy to keep in mind is that graphs are to semi-simpicial sets as reflexive graphs are to simplicial sets.

Also provided are the fundamental operators on simplicial sets used in nearly all geometric applications, namely the boundary and coboundary (discrete exterior derivative) operators. For additional operators, see the DiscreteExteriorCalculus module.

CombinatorialSpaces.SimplicialSets.DeltaSet1DType

A one-dimensional delta set, aka semi-simplicial set.

Delta sets in 1D are isomorphic to graphs (in the category theorist's sense). The source and target of an edge can be accessed using the face maps (simplicial terminology) or src and tgt maps (graph-theoretic terminology). More generally, this type implements the graphs interface in Catlab.Graphs.

CombinatorialSpaces.SimplicialSets.DeltaSet2DType

A 2D delta set, aka semi-simplicial set.

The triangles in a semi-simpicial set can be interpreted in several ways. Geometrically, they are triangles (2-simplices) whose three edges are directed according to a specific pattern, determined by the ordering of the vertices or equivalently by the simplicial identities. This geometric perspective is present through the subpart names ∂e0, ∂e1, and ∂e2 and through the boundary map . Alternatively, the triangle can be interpreted as a higher-dimensional link or morphism, going from two edges in sequence (which might be called src2_first and src2_last) to a transitive edge (say tgt2). This is the shape of the binary composition operation in a category.

CombinatorialSpaces.SimplicialSets.add_tetrahedron!Method

Add a tetrahedron (3-simplex) to a simplicial set, given its boundary triangles.

Warning

This low-level function does not check the simplicial identities. It is your responsibility to ensure they are satisfied. By contrast, tetrahedra added using the function glue_tetrahedron! always satisfy the simplicial identities, by construction. Thus it is often easier to use this function.

CombinatorialSpaces.SimplicialSets.add_triangle!Method

Add a triangle (2-simplex) to a simplicial set, given its boundary edges.

In the arguments to this function, the boundary edges have the order $0 → 1$, $1 → 2$, $0 → 2$. i.e. (∂e₂, ∂e₀, ∂e₁).

Warning

This low-level function does not check the simplicial identities. It is your responsibility to ensure they are satisfied. By contrast, triangles added using the function glue_triangle! always satisfy the simplicial identities, by construction. Thus it is often easier to use this function.

CombinatorialSpaces.SimplicialSets.closed_starMethod

Closed star of a vertex in a delta set.

Munkres §2 ≈ "The union of all simplices of s having v as a vertex."

Return a vector of simplices of dimensions 0 to n.

Note that we do not return polytopes, but rather the simplices which together form such polytopes, in no particular order.

This is not the Hodge star .

See also star, link.

CombinatorialSpaces.SimplicialSets.glue_sorted_tet_cube!Method

Glue a tetrahedralized cube onto a simplicial set, respecting the order of the vertices.

After sorting, the faces of the cube are: 1 5-4 0, 1 2-6 5, 1 2-3 0, 7 4-0 3, 7 3-2 6, 7 6-5 4, For each face, the diagonal edge is between those vertices connected by a dash. The internal diagonal is between vertices 1 and 7.

CombinatorialSpaces.SimplicialSets.glue_tetrahedron!Method

Glue a tetrahedron onto a simplicial set, given its boundary vertices.

If a needed triangle between two vertices exists, it is reused (hence the "gluing"); otherwise, it is created. Necessary 1-simplices are likewise glued.

CombinatorialSpaces.SimplicialSets.glue_triangle!Method

Glue a triangle onto a simplicial set, given its boundary vertices.

If a needed edge between two vertices exists, it is reused (hence the "gluing"); otherwise, it is created.

Note this function does not check whether a triangle [v₀,v₁,v₂] already exists.

Note that this function does not rearrange v₀, v₁, v₂ in the way that minimizes the number of edges added. For example, if s is the DeltaSet with a single triangle [1,2,3] and edges [1,2], [2,3], [1,3], then gluing triangle [3,1,4] will add edges [3,1], [1,4], [3,4] so as to respect the simplicial identities. Note that the edges [1,3] and [3,1] are distinct! However, if the DeltaSet that one is creating is meant to be manifold-like, then adding triangles using only the command glue_sorted_triangle! guarantees that the minimal number of new edges are created.

TODO: Reference a proof of the above claim.

CombinatorialSpaces.SimplicialSets.is_manifold_likeMethod

Test whether a given simplicial complex is manifold-like.

According to Hirani, "all simplices of dimension $k$ with $0 ≤ k ≤ n - 1$ must be the face of some simplex of dimension $n$ in the complex." This function does not test that simplices do not overlap. Nor does it test that e.g. two triangles that share 2 vertices share an edge. Nor does it test that e.g. there is at most one triangle that connects 3 vertices. Nor does it test that the delta set consists of a single component.

CombinatorialSpaces.SimplicialSets.linkMethod

Link of a vertex in a delta set.

Munkres §2 ≈ "The set St̄(v) - St(v)."

Return a vector of simplices of dimensions 0 to n.

These are the simplices which are in the closed star of v, but not in the star of v.

See also star, closed_star.

CombinatorialSpaces.SimplicialSets.nonboundariesMethod

Find the simplices which are not a face of another.

For an n-D oriented delta set, return a vector of 0 through n-1 chains consisting of the simplices that are not the face of another. Note that since n-simplices in an n-D oriented delta set are never the face of an (n+1)-simplex, these are excluded.

We choose the term "nonboundaries" so as not to be confused with the term "nonface", defined as those faces that are not in a simplical complex, whose corresponding monomials are the basis of the Stanley-Reisner ideal.

CombinatorialSpaces.SimplicialSets.orient!Method

Consistently orient simplices in a simplicial set, if possible.

Two simplices with a common face are consistently oriented if they induce opposite orientations on the shared face. This function attempts to consistently orient all simplices of a given dimension and returns whether this has been achieved. Each connected component is oriently independently using the helper function orient_component!.

CombinatorialSpaces.SimplicialSets.orient_component!Method

Consistently orient simplices in the same connected component, if possible.

Given an $n$-simplex and a choice of orientation for it, this function attempts to consistently orient all $n$-simplices that may be reached from it by traversing $(n-1)$-faces. The traversal is depth-first. If a consistent orientation is possible, the function returns true and the orientations are assigned; otherwise, it returns false and no orientations are changed.

If the simplicial set is not connected, the function orient! may be more convenient.

CombinatorialSpaces.SimplicialSets.starMethod

Star of a vertex in a delta set.

Munkres §2 ≈ "The union of the interiors of those simplices of s that have v as a vertex."

Return a vector of simplices of dimensions 0 to n.

Recall that interior(σ) = σ - boundary(σ), Munkres §1.

Note that we are returning interiors alone. This means, e.g. a triangle may be returned without one or more of its edges. Consequentially, the output of this function may not be storable in an ACSet.

This is not the Hodge star .

See also closed_star, link.

CombinatorialSpaces.SimplicialSets.∂Method

Face map and boundary operator on simplicial sets.

Given numbers n and 0 <= i <= n and a simplicial set of dimension at least n, the ith face map is implemented by the call

∂(n, i, s, ...)

The boundary operator on n-faces and n-chains is implemented by the call

∂(n, s, ...)

Note that the face map returns simplices, while the boundary operator returns chains (vectors in the free vector space spanned by oriented simplices).