# 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 graph | simplicial complex |

simple graph | abstract simplicial complex |

graph | semi-simplicial set |

reflexive graph | simplicial set |

symmetric graph | symmetric semi-simplicial set |

symmetric reflexive graph | symmetric simplicial set |

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
```

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
```

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.SimplicialSets`

— ModuleSimplicial 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.AbstractDeltaSet1D`

— TypeAbstract type for one-dimensional delta sets, aka semi-simplicial sets.

`CombinatorialSpaces.SimplicialSets.AbstractDeltaSet2D`

— TypeAbstract type for 2D delta sets.

`CombinatorialSpaces.SimplicialSets.AbstractDeltaSet3D`

— TypeAbstract type for 3D delta sets.

`CombinatorialSpaces.SimplicialSets.DeltaSet1D`

— TypeA 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.DeltaSet2D`

— TypeA 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.DeltaSet3D`

— TypeA 3D delta set, aka semi-simplicial set.

`CombinatorialSpaces.SimplicialSets.E`

— TypeEdge in simplicial set: alias for `Simplex{1}`

.

`CombinatorialSpaces.SimplicialSets.EmbeddedDeltaSet1D`

— TypeA one-dimensional, embedded, oriented delta set.

`CombinatorialSpaces.SimplicialSets.EmbeddedDeltaSet2D`

— TypeA two-dimensional, embedded, oriented delta set.

`CombinatorialSpaces.SimplicialSets.EmbeddedDeltaSet3D`

— TypeA three-dimensional, embedded, oriented delta set.

`CombinatorialSpaces.SimplicialSets.HasDeltaSet`

— TypeAbstract type for C-sets that contain a delta set of some dimension.

This dimension could be zero, in which case the delta set consists only of vertices (0-simplices).

`CombinatorialSpaces.SimplicialSets.HasDeltaSet1D`

— TypeAbstract type for C-sets that contain a one-dimensional delta set.

`CombinatorialSpaces.SimplicialSets.HasDeltaSet2D`

— TypeAbstract type for C-sets containing a 2D delta set.

`CombinatorialSpaces.SimplicialSets.HasDeltaSet3D`

— TypeAbstract type for C-sets containing a 3D delta set.

`CombinatorialSpaces.SimplicialSets.OrientedDeltaSet1D`

— TypeA one-dimensional oriented delta set.

Edges are oriented from source to target when `edge_orientation`

is true/positive and from target to source when it is false/negative.

`CombinatorialSpaces.SimplicialSets.OrientedDeltaSet2D`

— TypeA two-dimensional oriented delta set.

Triangles are ordered in the cyclic order $(0,1,2)$ when `tri_orientation`

is true/positive and in the reverse order when it is false/negative.

`CombinatorialSpaces.SimplicialSets.OrientedDeltaSet3D`

— TypeA three-dimensional oriented delta set.

`CombinatorialSpaces.SimplicialSets.Simplex`

— Type`CombinatorialSpaces.SimplicialSets.SimplexChain`

— TypeWrapper for chain of oriented simplices of dimension `n`

.

`CombinatorialSpaces.SimplicialSets.SimplexForm`

— TypeWrapper for discrete form, aka cochain, in simplicial set.

`CombinatorialSpaces.SimplicialSets.Tet`

— TypeTetrahedron in simplicial set: alias for `Simplex{3}`

.

`CombinatorialSpaces.SimplicialSets.Tri`

— TypeTriangle in simplicial set: alias for `Simplex{2}`

.

`CombinatorialSpaces.SimplicialSets.V`

— TypeVertex in simplicial set: alias for `Simplex{0}`

.

`CombinatorialSpaces.SimplicialSets.Lk`

— FunctionAlias for the link operator `link`

.

`CombinatorialSpaces.SimplicialSets.St`

— FunctionAlias for the star operator `star`

, not the Hodge star.

`CombinatorialSpaces.SimplicialSets.St̄`

— FunctionAlias for the closed star operator `closed_star`

, not the Hodge star.

`CombinatorialSpaces.SimplicialSets.add_sorted_edge!`

— MethodAdd edge to simplicial set, respecting the order of the vertex IDs.

`CombinatorialSpaces.SimplicialSets.add_sorted_edges!`

— MethodAdd edges to simplicial set, respecting the order of the vertex IDs.

`CombinatorialSpaces.SimplicialSets.add_tetrahedron!`

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

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!`

— MethodAdd 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₁).

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.boundary`

— FunctionAlias for the face map and boundary operator `∂`

.

`CombinatorialSpaces.SimplicialSets.closed_star`

— MethodClosed 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 simplex chains 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 `⋆`

.

`CombinatorialSpaces.SimplicialSets.coboundary`

— FunctionAlias for the coboundary operator `d`

.

`CombinatorialSpaces.SimplicialSets.d`

— MethodThe discrete exterior derivative, aka the coboundary operator.

`CombinatorialSpaces.SimplicialSets.edge_vertices`

— MethodBoundary vertices of an edge.

`CombinatorialSpaces.SimplicialSets.exterior_derivative`

— FunctionAlias for the discrete exterior derivative `d`

.

`CombinatorialSpaces.SimplicialSets.glue_sorted_tet_cube!`

— MethodGlue 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_sorted_tetrahedron!`

— MethodGlue a tetrahedron onto a simplicial set, respecting the order of the vertices.

`CombinatorialSpaces.SimplicialSets.glue_sorted_triangle!`

— MethodGlue a triangle onto a simplicial set, respecting the order of the vertices.

`CombinatorialSpaces.SimplicialSets.glue_tetrahedron!`

— MethodGlue 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!`

— MethodGlue 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_like`

— MethodTest 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.link`

— MethodLink of a vertex in a delta set.

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

Return a vector of simplex chains 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.nonboundaries`

— MethodFind 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.nsimplices`

— MethodNumber of simplices of given dimension in a simplicial set.

`CombinatorialSpaces.SimplicialSets.orient!`

— MethodConsistently 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!`

— MethodConsistently 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.orientation`

— MethodOrientation of simplex.

`CombinatorialSpaces.SimplicialSets.point`

— MethodPoint associated with vertex of complex.

`CombinatorialSpaces.SimplicialSets.set_orientation!`

— MethodSet orientation of simplex.

`CombinatorialSpaces.SimplicialSets.simplices`

— MethodSimplices of given dimension in a simplicial set.

`CombinatorialSpaces.SimplicialSets.star`

— MethodStar 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 simplex chains 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.tetrahedron_edges`

— MethodBoundary edges of a tetrahedron.

This accessor assumes that the simplicial identities hold.

`CombinatorialSpaces.SimplicialSets.tetrahedron_triangles`

— MethodBoundary triangles of a tetrahedron.

`CombinatorialSpaces.SimplicialSets.tetrahedron_vertices`

— MethodBoundary vertices of a tetrahedron.

This accessor assumes that the simplicial identities hold.

`CombinatorialSpaces.SimplicialSets.triangle_edges`

— MethodBoundary edges of a triangle.

`CombinatorialSpaces.SimplicialSets.triangle_vertices`

— MethodBoundary vertices of a triangle.

This accessor assumes that the simplicial identities hold.

`CombinatorialSpaces.SimplicialSets.volume`

— Method$n$-dimensional volume of $n$-simplex spanned by given $n+1$ points.

`CombinatorialSpaces.SimplicialSets.volume`

— Method$n$-dimensional volume of $n$-simplex in an embedded simplicial set.

`CombinatorialSpaces.SimplicialSets.∂`

— MethodFace map and boundary operator on simplicial sets.

Given numbers `n`

and `0 <= i <= n`

and a simplicial set of dimension at least `n`

, the `i`

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