Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
it is not quite (or at all) what you want, but if $\Delta'\subset\Delta$ is a contractible subcomplex then you can throw away the simplexes of $\Delta'$ (that is, the relative homology $H_\bullet(\Delta,\Delta')$ is isomorphic to the reduced homology of $\Delta$). [tree=contractible subcomplex of a graph] –  user8268 Jun 1 '11 at 14:04
    
@user8268: that sounds like a good direction. Is there always a contractible subcomplex where the "quotient" is a wedge of spheres? Is there any algorithm to find it, like for spanning forests? The first question says "once we find Δ′, we have a trivially easy basis to write down," and the second says "we can find such an amazing Δ′". –  Jack Schmidt Jun 1 '11 at 14:12
    
@Jack: that wedge of spheres condition is too much to ask for; wouldn't it imply that the fundamental group of a $2$-dimensional complex is always free? –  Qiaochu Yuan Jun 1 '11 at 15:08
    
@Qiaochu: Is it too much to ask that the "leftover" k-faces are in (computable) bijection with a basis of the k-th homology? I think my complexes are always homotopic to wedges of spheres, but I'm not very sure of that. Maybe someone can show that this idea is broken for the Klein bottle? I don't even know what it would mean to have an order 2 element of the 1st-homology. I'm also a little worried that a dimension 2 guy has trivial top homology and non-trivial middle homology. In my examples, the top is usually free abelian, and the middle is 0. –  Jack Schmidt Jun 1 '11 at 15:19
1  
What are you looking for is called "shellability" (or "shellable complexes"). It's an extensively studied topic. You should be able to find many informations on google scholar. –  Giacomo d'Antonio Jun 1 '11 at 15:25
show 3 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks! This and its references are looking very nice so far. –  Jack Schmidt Jun 1 '11 at 15:52
add comment

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 : AB, 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 hi 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 hi). One always has h0 equal to the number of connected components, and magically hn 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 fi 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 h0 equal to the number of roots (connected components), h1 is the number of edges in the forest (so n−1 if the graph is connected on n vertices), and then h2 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 hk come last. A basis of the (reduced) homology Hk(Δ) is in (computable) bijection with the facets that are k-faces contributing to hk. 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

share|improve this answer
    
Suppose I have a (single component) connected graph and perform the quotient of contracting a spanning tree to a vertex. I'm left with a wedge sum of circles. Does there exist a similar quotient for an arbitrary simplex? That is, is there a "spanning subsimplex" which when contracted leaves a bouquet of spheres? Is shellability the right condition needed here? –  user02138 Jun 1 '11 at 20:37
1  
@user02138: An arbitrary shellable complex has such a subcomplex (take any shelling; remove all facets that added a "cycle", as in, a k-simplex joined along all k edges; the result is a "spanning subcomplex" and the remaining facets are a basis of the homology. Woo!). However, "many" other complexes have such complexes. "Cohen-Macaulay" may be a decent condition to require that is more general. However, I think my complexes are shellable. –  Jack Schmidt Jun 1 '11 at 20:45
1  
@user02138: As Qiaochu Yuan points out: some condition is necessary, since not all spaces are homotopic to a wedge of spheres! However, WCKronholm's (or Mrozek's, et al.) idea works without any hypothesis. Instead of having a wedge of spheres at the end, you have a pretty general complex, but one with a lot fewer faces. –  Jack Schmidt Jun 1 '11 at 20:47
    
Neat! @All: Thanks for such a great Q&A! –  user02138 Jun 1 '11 at 20:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.