All posts by Justin

Speeding up Homology via Duality?

In the last post I constructed for any (locally finite) simplicial complex K a dual complex. Today, I thought of using this to gain a potential speed-up in computational homology.

Note that simplicial homology of K is the same as Cech homology of the cover given by open stars of the vertices of K. This is because the nerve of this cover is precisely K and Cech homology is not-so-secretly the simplicial homology of the nerve.

However, we know that the dual complex has the same homotopy type as K, but the number of vertices in the dual complex is equal to the number of maximal simplices. Simplicial homology of this dual complex is the same as Cech homology of the cover given by the closed top dimensional cells in K.

Here is a case where this observation results in a most dramatic speed-up. The standard n-simplex \Delta^n has 2^{n+1} simplices and naively simplicial homology requires storing all of these. However, the dual complex is a single point and Cech homology here reveals that. Thus we have gone from a chain complex with n+1 chain groups, each of which are dimension \binom{n+1}{j} to a chain complex concentrated in a single degree, all by using this duality.

Of course, the case of graphs shows where this duality fails miserably. The dual complex creates simplices whose dimension corresponds to the degree of vertices in the original graph, so we can go from a two-term chain complex with a single boundary matrix, to arbitrarily large chain complexes.

This presents a question of possible interest: For what simplicial complexes does the dual complex and the original complex have the same number of simplices? Triangulated manifolds clearly do, but what about other simplicial complexes? Can we say something about the expected discrepancy of these numbers?

Dual Simplicial Complexes

In the process of designing homework problems for Applied Algebraic Topology (ESE 680-003) last night, I stumbled upon a most beautiful application of the nerve theorem as well as a construction of a dual simplicial complex that is defined for any (locally finite) simplicial complex K. This dual complex has the property that it is always homotopic to the original simplicial complex.

Let K be a simplicial complex with vertex set V. The open star U_v of a vertex v is defined to be the set of simplices \sigma containing v.  Visibly, the nerve of the cover \mathcal{U}=\{U_v | v\in V\} is the same as the simplicial complex K.

On the other hand, one can consider a different cover by closed sets, or dually Alexandrov opens when one reverses the partial order. Define a simplex to be maximal if it is not the face of any other simplex. Define the closure \overline{\sigma} of a simplex \sigma to be the set of faces of \sigma, written \tau\leq\sigma, so that \sigma\leq\sigma, i.e. \sigma is a face of itself.

Now define the dual simplicial complex of K to be the nerve of the cover \mathcal{V}=\{\overline{\sigma} | \sigma \,\mathrm{maximal}\,\}.

The nerve theorem works for convex closed sets or open sets with contractible intersections, so we know this dual simplicial complex has to be homotopy equivalent to the simplicial complex K.

If we use Graeme Segal’s construction of the classifying space of the cover category X_U (sometimes called the Mayer-Vietoris blowup complex) in the paper “Classifying Spaces and Spectral Sequences” then we should be able to construct a similar dual space for cell complexes by looking at the open stars of vertices and the closures of maximal cells respectively.