Is there a “spanning simplex” method to calculate homology of low dimensional simplicial complexes?

I had not noticed until recently a fairly easy method to compute the homology of a $1$ dimensional simplicial complex:

• If $Δ$ is a $1$-dimensional simplicial complex, then find a spanning forest using standard algorithms. The roots of the trees form a basis of $H_0(Δ)$, and the edges not in the tree form a basis of $H_1(Δ)$. Spanning forest algorithms are basically linear (in both time and memory) in the number of faces of the complex.

I need to let a group act on the homology, so I need an explicit basis of cycles and boundaries. However, almost all of my current examples are dimension $3$ or lower.

Is there a similar trick for dimension $2$ and/or $3$? Is there some sort of spanning simplex?

Basically, I have some "sparse" simplicial complexes, and trying to use matrices for the calculations over the integers is somewhat time and memory consuming. It would be nice to have a combinatorial trick to just get a basis of the cycle space and the boundaries.

I consider a simplicial complex to be a collection of subsets of $\{ 1, 2, \ldots, n\}$ closed under subset, and generally specified by $n$ and a "generating set" of subsets (so take the subsets of all the elements of the generating set). A graph is specified by its edges, and the dim $2$ guys are specified by their maximal triangles and any isolated edges or vertices.

Thanks to Giacomo d'Antonio, Ben Braun, and Carl Lee, I think I am now quite sure that shellable complexes are exactly what I am looking for.

Simplicial complexes

A simplicial complex on n is a collection of subsets, called faces, of { 1, 2, …, n } such that every subset of a face is a face. A facet of a simplicial complex is a maximal face, a face not contained in any other face. The simplicial complex Δ generated by a collection X of subsets of { 1, 2, …, n } is the collection of all subsets of elements of X, Δ = { A : A ⊆ B, for some B in X }. A simplicial complex is generated by its facets in so far as the simplicial complex is the collection of all subsets of its facets. A face is said to be a k-face if it has size k+1.

Simplicial complexes generalize graphs. A simple graph is a simplicial complex generated by its edges (which are subsets of size 2, the two vertices, and so are 1-faces) and its isolated vertices (which are subsets of size 1, so 0-faces).

Shellable simplicial complexes

A simplicial complex is pure if all of its facets have the same size. A simplicial complex is (non-pure) shellable if there is an ordering (a “shelling” or “shelling ordering”) of its facets so that each new facet (which is a k-face) intersects the complex generated by the previous facets in a union of (k−1)-faces and such that the complex generated by the previous facets is pure. Especially in the pure case, define the h-vector by h_i to be the number of facets adjoined along exactly i faces (or more technically, adjoining a new facet will introduce new faces; to be a shelling there must be a unique minimal new face, and if it is an i face, then the new facet contributes to h_i). One always has h₀ equal to the number of connected components, and magically h_n is the dimension of the top homology, assuming the complex is shellable. Pascal's triangle can be used to convert the h-vector to the f-vector, where f_i is defined to be the number of i-faces of the complex.

A graph is shellable: choose any vertex as the root of a tree, and adjoin edges to exactly one leaf at a time until one cannot. If there are vertices left, choose one as a new root and begin again. Continue this until all vertices are used. The result is a spanning forest. The shelling begins with the sequence of edges added to the trees (and in a degenerate case of a single isolated point, just that vertex as the "root" of the edgeless tree). The h-vector has h₀ equal to the number of roots (connected components), h₁ is the number of edges in the forest (so n−1 if the graph is connected on n vertices), and then h₂ is the number of edges left, which is exactly the dimension of the top homology.

Shellings and homology

In general a shelling of a complex can be reordered so that all facets which are k-faces contributing to h_k come last. A basis of the (reduced) homology H_k(Δ) is in (computable) bijection with the facets that are k-faces contributing to h_k. These are exactly the facets that "fill holes", since their entire boundary is glued into the complex. This is explicitly mentioned as Theorem 3.1.3 in the expository article by Wachs (2007).

In the graph case, one creates the spanning tree first, and then each remaining edge closes a cycle, and so contributes one to the dimension of the first homology. Similarly isolated vertices and roots (beyond the first) contribute to (reduced) zeroth homology.

Generalizations and bibliography

It is possible to generalize these ideas a bit further to simplicial spanning trees, as in Duval–Klivans–Martin (2009). Here one gets broadly similar results that do not require the complex to be shellable (Cohen-Macaulay suffices); I believe taking these ideas even more generally (to all complexes) is similar to what wckronholm's answer describes. A nice description of this sort of combinatorics, especially shellability and its relation to group actions on posets, is in Wachs (2007). An implementation of the implicit algorithms described by shellability is available for Macaulay 2 thanks to Cook (2010).

Cook, David II. "Simplicial decomposability." The Journal of Software for Algebra and Geometry 2 (2010), 20-23. URL:http://www.j-sag.org/Volume2/

Duval, Art M.; Klivans, Caroline J.; Martin, Jeremy L. "Simplicial matrix-tree theorems." Trans. Amer. Math. Soc. 361 (2009), no. 11, 6073–6114. MR2529925 DOI:10.1090/S0002-9947-09-04898-3.

Wachs, Michelle L. "Poset topology: tools and applications." Geometric combinatorics, 497–615, IAS/Park City Math. Ser., 13, Amer. Math. Soc., Providence, RI, 2007. MR2383123

A lot of work has been, and is being, done in finding effective methods of computing homology groups for cubical and simplicial complexes.

A good one to read is the paper Homology Algorithm Based on Acyclic Subspace by M. Mrozek, P. Pilarczyk, and N. Żelazna. The particular algorithm presented in the linked to paper addresses cubical complexes. Browse through Mrozek's preprint page here to see some related results for simplicial and CW-complexes.