Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to compute the homology of certain low dimensional CW complexes and I am hoping to take advantage of software that handles simplicial sets as input. Thus, I would like to convert a CW complex into a homologically equivalent simplicial set.

In the case where the CW complex is regular, everything is easy. I just build the order complex of the face partial order on the cells of $\mathcal{X}$. What should I do when confronted with a non-regular CW complex?

More precisely, consider a (not necessarily regular) finite CW complex $\mathcal{X}$ and define the following combinatorial structure $(X,a)$. $X$ is a graded set $X = \sqcup_k X_k$ where $X_k$ is the set of all $k$-cells of $\mathcal{X}$. The maps $a_k: X_k \times X_{k-1} \to \mathbb{Z}$ are defined as follows: $a(\xi,\eta)$ is the degree of the attaching map from the boundary of $\xi$ onto $\eta$.

Question:

Is there a standard method for taking $(X,a)$ as input and producing a simplicial set whose homology coincides with that of $\mathcal{X}$?

If not, can we come up with such a method?

Update In light of objections in the comments, I have tried to present the question with a more accurate title and also removed the unreasonable homotopy equivalence requirement.

share|improve this question
    
Where do your cw complexes come from? –  Igor Rivin Jul 2 '12 at 17:12
    
Igor, I am looking at presentation complexes of some small groups and of course the words in many relations contain exponents that are not $\pm 1$. I can add more detail if necessary, but I was trying to keep the question concise. –  Vidit Nanda Jul 2 '12 at 17:20
    
@Vel: I am asking because in many apsecial cases there are efficient algorithms for triangulation,which do not go through in general... –  Igor Rivin Jul 2 '12 at 17:25
    
Igor: in this case, efficiency is not very important because the input has small size, both in terms of cell count and also in terms of the degrees of attaching maps. –  Vidit Nanda Jul 2 '12 at 18:23
    
Vel, I've found the title misleading. Finding a homotopy equivalent (or just homology equivalent) simplicial set is not triangulating. –  Fernando Muro Jul 2 '12 at 19:24
show 5 more comments

3 Answers 3

up vote 1 down vote accepted

For a 2-dimensional complex, I think the following works, but I may not have checked carefully enough. Given a finite 2-dimensional CW complex, I'll describe a finite simplicial set with the same homology. (Note: this procedure uses the full attaching maps, not just their degrees.)

First, the 1 skeleton is a graph, maybe with multiple edges and loops, but in any case it's a simplicial set once you make choices of orientations on the edges. Let's assume that all the attaching maps for 2-cells are regular edge paths (i.e. ones that linearly traces out a sequence of n edges in equal time).

First, "double" every edge in the 1-skeleton by adding a new edge with the opposite orientation, and then add a "fake" 2-simplex whose faces are these paired edges along with (the degeneration of) one of their common vertices. (There's a choice involved in adding these 2-simplices, but I don't think it matters.)

Each 2-cell in your complex is attached along a regular edge-path of length n in the original graph. In some cases, it may traverse an edge in the wrong direction (according to the orientations chosen above) and in this case we'll use the double of that edge instead. (Note that the double still has the same endpoints just in the opposite order.)

To be precise: subdivide the disk into an n-gon, and attach it according to the given regular edge path, using the double edges as explained. This really amounts to attaching n 2-simplices which all have a common (new) vertex.

If you collapse the "fake" 2-simplices down to edges, you recover the original complex. I think this projection map should at least be a homology equivalence, if not a homotopy equivalence. Actually, if there are finitely many cells then the homology isomorphism follows immediately from the Vietoris-Begle mapping theorem, because the equivalence classes we're collapsing are either points or intervals: http://en.wikipedia.org/wiki/Vietoris%E2%80%93Begle_mapping_theorem

share|improve this answer
    
Dan, thanks. Regarding your projection map: you do have a homotopy equivalence because there is a homotopy version of the Vietoris-Begle theorem due to Smale (search: A Vietoris Mapping Theorem for homotopy). Essentially, if you require the fibers of your map to be contractible (instead of just acyclic), then you have a homotopy (instead of just homology) equivalence. –  Vidit Nanda Jul 6 '12 at 23:47
    
I thought something like that was true, but didn't take the time to track it down. Thanks for the reference. –  Dan Ramras Jul 7 '12 at 2:46
add comment

(the following is an expanded version of what was previously a comment)

I don't see why you think homotopy equivalence is an unreasonable requirement. Indeed, Theorem 2C.5 of Hatcher's Algebraic Topology says that every finite CW complex is homotopy equivalent to a finite simplicial complex.

His proof does give a standard `method' for turning a CW complex into a homotopy equivalent simplicial complex. It appears to me that it can be turned into an an actual algorithm.
The two main steps that you'd have to implement are: find a simplicial approximation of each attaching map, then find a simplicial subdivision of the mapping cone.

I'll remark that as far as simplicial analogues of mapping cones go, Jonathan Barmak has a nice technique for posets in this paper, where he essentially takes a subcomplex of the join of two posets. Perhaps his technique could be generalized to all simplicial complexes.

share|improve this answer
    
Russ, the requirement is only unreasonable if I restrict my knowledge of the CW complex to the degrees of the attaching maps as indicated in the original question. Thanks for the link to Barmak's paper. –  Vidit Nanda Jul 6 '12 at 23:33
add comment

If you only want to compute homology of a finite presentation complex $X$ of a group $G$ (as I understand from comments), you can do it by (integer) linear algebra only.

Let generators be $x_1,\dots,x_m$, with relations $r_1,\dots,r_n$.

Then $H_1(X)=G_{ab}$ is the cokernel of the $m\times n$ integer matrix $A$ of degrees $\deg_{x_i} r_j$ (view as morphism $\mathbb{Z}^n\to \mathbb{Z}^m$), and $H_2(X)$ is the kernel of $A$ (in $\mathbb{Z}^n$).

Note that the computation of $H_2$ of the group $G$ from a finite presentation is algorithmically infeasible in general, as shown by C. Gordon in the eighties (see this answer).

I like to see this problem as akin to that of deciding finite sets of tiles that tile the plane, as it asks for computing all tilings (or at least a "generating" set of tilings) of the 2-sphere by copies of topological disks boundary-decorated with relations (well, maybe introducing some non-reduced relator words). But I don't know if this idea leads to a proof (Gordon's proof is different). Recall that deciding finite sets of tiles that tile the plane is also algorithmically infeasible.

When possible, this computes $H_2(G)$ of the group as $H_2(X)/h(\pi_2(X))$, where $h$ is Hurewicz homomorphism.

share|improve this answer
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.