12
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – Someone
    Commented Oct 21, 2010 at 9:43
  • $\begingroup$ Many thanks for all the 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. $\endgroup$
    – user10249
    Commented Oct 22, 2010 at 2:47
  • 1
    $\begingroup$ If the whole poset is a lattice, have you considered the homotopy complementation formula of Bj\"orner and Walker? $\endgroup$
    – John Shareshian
    Commented Oct 22, 2010 at 3:01

5 Answers 5

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user10249
    Commented Oct 25, 2010 at 2:22
  • $\begingroup$ 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. $\endgroup$
    – j.p.
    Commented Oct 25, 2010 at 8:36
  • $\begingroup$ No chance to calculate the homology of your poset without the atoms with Simplicial Homology for GAP? $\endgroup$
    – j.p.
    Commented Oct 25, 2010 at 8:46
3
$\begingroup$

Short note for similar problems.

We solved the problem using RedHom software in 2012, 3 days of computations, ~400GB of RAM.

However, now we have better methods and we can check Cohen-Macaulay property of the huge complex in 30 minutes, 340GB of RAM, using 64-cores Intel [email protected] (assuming hdf5 input file format). It is so fast, because in parallel we can build a data structure for the complex and compute an optimal discrete Morse vector field.

Improve this answer
$\endgroup$
2
$\begingroup$

Although Justin already knows this, let me leave a note here.

There are people working on computer programs that aim to compute homology fast, like the group working on RedHom. They reduce the given complex (mostly using variants of discrete Morse theory) before the actual computations take place.

However, as far as I know no reduction methods suited to posets have been implemented in RedHom, so one has to turn the poset into a simplicial complex before performing the reductions. Perhaps the ideas of Barmak and Minian concerning finite topological spaces could be used for performing reductions on the poset level? (Just an idea.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .