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 with elements V = 1:4, E = 1: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 with elements V = 1:4, E = 1:5, Tri = 1: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{StaticArrays.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.

source
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$.

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.

source
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!.

source
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.

source
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).

source