## Computing homology of very large posets

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.

-
 I guess you know already that you don't have to check the recursive condition for a recursive atom ordering if the upper intervals $P_{\ge m}$ happen to be upper-semimodular lattices for all minimal elements $m$? – Someone Oct 21 2010 at 9:43

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.

-

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.

-

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.

-

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.

-
If the whole poset is a lattice, have you considered the homotopy complementation formula of Bj\"orner and Walker? – John Shareshian Oct 22 2010 at 3:01

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.

-
You cannot comment since you got yourself a second identity after you posted your question (probably you lost the cookie). Otherwise you had already 51 points and the power to comment (and you can anyway - also with only 1 point - comment on answers to your questions and on your own answers). You can contact an administrator to merge your accounts. – jp Oct 25 2010 at 8:36
No chance to calculate the homology of your poset without the atoms with Simplicial Homology for GAP? – jp Oct 25 2010 at 8:46