Computing homology of very large posets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:06:14Z http://mathoverflow.net/feeds/question/42986 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets Computing homology of very large posets Justin Koonin 2010-10-21T02:25:22Z 2010-10-25T02:22:27Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets/43035#43035 Answer by Jim Conant for Computing homology of very large posets Jim Conant 2010-10-21T11:00:20Z 2010-10-21T11:00:20Z <p>I've found that discrete Morse theory is very helpful in this context. Here's a <a href="http://math.rice.edu/~forman/user.ps" rel="nofollow">link</a> 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.</p> http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets/43060#43060 Answer by Priyavrat Deshpande for Computing homology of very large posets Priyavrat Deshpande 2010-10-21T15:49:21Z 2010-10-21T15:49:21Z <p>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). </p> <p>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.</p> http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets/43119#43119 Answer by Justin Koonin for Computing homology of very large posets Justin Koonin 2010-10-22T02:47:30Z 2010-10-22T02:47:30Z <p>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!</p> <p>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.</p> http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets/43235#43235 Answer by jp for Computing homology of very large posets jp 2010-10-22T21:13:55Z 2010-10-22T21:13:55Z <p>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 <em>Quillen's Fiber Lemma</em> (compare [Q78, Proposition 7.6] and [AS92, (4.3)]):</p> <p>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</p> <p>$$f_{x, i}: \pi_i(|X|, x) \to \pi_i(|Y|, f(x))$$</p> <p>of homotopy groups are isomorphisms for $i \le n$ and epimorphisms for $i = n+1$.</p> <p>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.</p> <p>[AS92] M. Aschbacher, Y. Segev: Locally connected simplicial maps, Israel Journal of Mathematics 77 (1992), 283-303.</p> <p>[Q78] D. Quillen: Homotopy properties of the poset of nontrivial p-subgroups of a group, Advances in Mathematics 28 (1978), 102-28.</p> http://mathoverflow.net/questions/42986/computing-homology-of-very-large-posets/43461#43461 Answer by Justin Koonin for Computing homology of very large posets Justin Koonin 2010-10-25T02:22:27Z 2010-10-25T02:22:27Z <p>Hmm... seems I can't comment yet, so I'll post my response here.</p> <p>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.</p>