Computing homology of very large posets - MathOverflow

Computing homology of very large posets

2010-10-21T02:25:22Z

I'm studying the homology of a couple of very large posets (one has over 4 million vertices, though the dimension is only 3). I want to show the posets are spherical (homology vanishes except in top dimension) or better Cohen-Macaulay. Because of the size, a direct computation of homology seems impossible, even with a clever program like Simplicial Homology for GAP.

Does anyone know of an algorithm for this sort of thing which could make life easier? I have tried to find an explicit recursive atom ordering already, but haven't found one.

Answer by Jim Conant for Computing homology of very large posets

2010-10-21T11:00:20Z

I've found that discrete Morse theory is very helpful in this context. Here's a link to a nice article by Forman. If you can define a good discrete vector field, it's often possible to drastically reduce the size of the chain complex. The art of course is in coming up with the right vector field.

Answer by Priyavrat Deshpande for Computing homology of very large posets

2010-10-21T15:49:21Z

I agree with Jim Conant, discrete Morse theory should help. Acyclic matching of (the Hasse diagram of) the poset is a good candidate for a discrete vector field (see D. Kozlov's book Combinatorial Algebraic Topology, chapter 11).

However, it does not guarantee that one will get a minimal complex (all the cells are homology cells). If your posets are not "nice" enough then finding a (perfect) acyclic matching will be as hard as finding a recursive (co)atom ordering.

Answer by Justin Koonin for Computing homology of very large posets

2010-10-22T02:47:30Z

Many thanks for those responses. I borrowed Kozlov's book to read the chapter on spectral sequences, but somehow didn't look at the section on discrete Morse theory. I'll have to go back to the library!

Also regarding the comment on recursive atom orderings, yes the upper intervals are in fact geometric lattices, so there is no problem with the recursive condition. It's the other one which is problematic.

Answer by jp for Computing homology of very large posets

2010-10-22T21:13:55Z

You wrote that upper intervals are very nice (i.e., shellable, hence spherical) in your poset, you can try to apply this slightly stronger version of Quillen's Fiber Lemma (compare [Q78, Proposition 7.6] and [AS92, (4.3)]):

Let $f: X \to Y$ be a (monotone) map of posets such that the fibers $|\{f \le y\}|$ are $n$-connected for all $y \in Y$. Then $f$ is $(n+1)$-connected, i.e., for all $x \in X$ the induced maps

$$f_{x, i}: \pi_i(|X|, x) \to \pi_i(|Y|, f(x))$$

of homotopy groups are isomorphisms for $i \le n$ and epimorphisms for $i = n+1$.

For $Y$ you take the dual of your poset and for $X$ the dual of the poset without the atoms. If you understand the homology of $|X|$ very well, maybe you are able to show that $f$ is null-homotopic, which implies that $|X|$ is $n$-connected and $|Y|$ is $(n+1)$-connected.

[AS92] M. Aschbacher, Y. Segev: Locally connected simplicial maps, Israel Journal of Mathematics 77 (1992), 283-303.

[Q78] D. Quillen: Homotopy properties of the poset of nontrivial p-subgroups of a group, Advances in Mathematics 28 (1978), 102-28.

Answer by Justin Koonin for Computing homology of very large posets

2010-10-25T02:22:27Z

Hmm... seems I can't comment yet, so I'll post my response here.

To jp, thanks for a good idea. I have actually looked at something very similar using the paper "Extensions of G-posets and Quillen's Complex" by Segev and Webb (which refers to AS92). The poset X and Y in your poset don't seem to have homology which is easy to recognise, but there is an extension of Y which works much better. Still, I'm keen to understand Y as well.