Subject: nov 4
To: rusin@math.niu.edu
Date: Mon, 4 Nov 96 15:12:24 MST
From: [Permission pending]
Dear David Rusin,
From some letters I was emailed about algorithmic
computations of homology and homotopy, I think you may be able to
help me on the (much simpler) homology calculations. What I am
looking for is a program that will give the homology groups of
various finite simplicial complexes, that arise in combinatorics
and hence can have many vertices, simplexes. Thanks for any help
in this matter, I am sure that such programs have existed for
quite a while but don't know offhand how to locate one.
Regards,
[Permission pending]
P.S. Is niu=Northern Illinois Univ?
==============================================================================
Date: Mon, 4 Nov 96 16:48:26 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: nov 4
I'm not sure what exactly you seek. Theoretically, homology groups
are fairly easy to calculate for finite simplicial complexes.
Although homology can be defined in terms of huge (infinitely-generated)
chain complexes, one may in fact show that the this complex is
chain-homotopic to the finite chain complex freelyl generated by the
cells of the simplicial complex. Thus for example, the cohomology
of a hollow cube may be computed with a chain complex of the form
Z^6 -> Z^12 -> Z^8
since there are 6 faces, 12 edges, and 8 vertices. One need then
simply compute the kernel and cokernel of certain matrices
(12 x 6, 8 x 12, and 1 x 8) which have integer coefficients.
In some settings it's even easier since the homology is equally well
determined by a CW-decomposition of the space. In the case of the
cube, for example, we simply observe that the space is homeomorphic
to the CW complex formed by adjoining a 2-cell (a closed disk in R^2)
to a 0-cell (a point) by sending the whole boundary of the disk to
the point. The resulting chain complex is now quite simple:
Z -> 0 -> Z
so that the homology groups may be simply read off.
I concede however that when you start to allow nonlinear attaching maps
that it can be a little more problematic trying to figure out what
the boundary maps in the chain complex are.
So if you wanted to know whether the (abstract) homology groups of
a simplicial complex could be computed in finite time, the answer is
certainly yes. On the other hand, you might be asking for something
more subtle, in which case I'm not entirely sure what to say:
1) You might want to know what the homology classes "really are",
that is, you might want a description of the generators of the groups,
sufficient to enable you to determine (for example) the effect of
the induced maps f:H*(X)->H*(Y) corresponding to maps between spaces.
I guess this is calculable if f is piece-wise linear; I don't
think I could find a way to machine-encode it for general continuous f.
2) You might want more of the algebraic structure of the
homology or more likely of the cohomology. For example, it's natural to
ask about the ring structure of H^*(X). I suppose I could compute this
from first principles (the definition of cup product) but I'm not sure
I would have the patience to do so. I am even less certain that I could
compute the action of the (co)homology operations (e.g. Steenrod squares.
You didn't say if you wanted coefficients in Z, R, F_p, etc.)
3) You might hope for something "efficient"; a rank-26 chain
complex does seem a little exorbitant for a space whose homology groups
have total rank 2. In one sense I think you're out of luck: there
exist spaces whose minimal triangulations (in some sense) grow much
faster than their homology.
4) Finally you might be asking for some explicit code to do
the calculations. I don't know of any turn-key programs of this type.
Really the biggest hurdle would be in finding an appropriate way to
enter the complex in the first place. For example, no one has any
trouble visualizing a cube made from the 26 cells, but how would you
want a user to input the incidence data which would define the cube for
the program -- must the user fill a 26 x 26 matrix? Yuk (especially
since signs are crucial and yet likely to be entered wrong).
Perhaps you could send an example of the kind(s) of questions you
would want answered; then I could be more helpful in connecting you
with appropriate software.
dave
PS - Yes, NIU is Northern Illinois University. One of our state's best kept
secrets.
==============================================================================
Subject: Re: nov 4
To: rusin@math.niu.edu (Dave Rusin)
Date: Fri, 8 Nov 96 13:59:21 MST
From: [Permission pending]
Dear Dave,
[...]
While the idea of explicit computations of homotopy groups,
where possible, is intriguing, I am looking for something much
simpler, just a program that can find the homology groups of a
given (say abstract) simplicial complex. The number of vertices
will be ${n\choose r}$ for any $n,4$, so might be very large. I
want to give this project to my M Sc student and have her find
the homology groups of various examples of this kind - to be
completely explicit these complexes will be neighbourhood
complexes of Kneser graphs, and will be glad to define all that
if you wish. Clearly a computer will help for a simplicial cx
with, say ${10\choose 3}=120$ vertices, and that's only a small
one.
Of course, the text Seifert-Threfall from the 30's already
gives a complete algorithm for homology groups, so what I am
looking for is a computer implementation of this or an equivalent
algorithm.
Regards, [Permission pending]
==============================================================================
Subject: Re: nov 4
To: rusin@math.niu.edu (Dave Rusin)
Date: Tue, 26 Nov 96 17:13:06 MST
From: [Permission pending]
Dear Dave,
Thanks again for the detailed note. Will think about the
details tomorrow, I believe MAPLE has a routine for normal form
of matrices over $Z$, and that may be good enough to do the
homology of any chain complex of f.g. free abelian groups. Will
check into these things and those you have mentioned. Ideally I
would like a program that I could feed a finite (abstract) simp
complex into, or even any finite chain complex of free abelian
groups with given differentials, and have it tell me the homology
groups, preferably also the generators too.
More later,
Regards, [Permission pending]
==============================================================================
Subject: Re: nov 4
To: rusin@math.niu.edu (Dave Rusin)
Date: Fri, 13 Dec 96 11:56:13 MST
From: [Permission pending]
Dear Dave,
We had John Selfridge here last week, it's always nice to see
him and talk. Together with my M Sc student and using Maple,
namely the ismith procedure within the linear algebra package, we
have quite easily been able to set up a program that computes the
homology groups of any chain complex
$$ 0\rightarrow C_n \rightarrow ...\rightarrow C_1 \rightarrow
C_0 \rightarrow 0,$$
where each $C_i$ is a fin gen free abelian group. It is equally
easy to set up a feeder program which will set up the chain
complex of any finite simplicial complex into the above form, and
thus obtain its homology. I would imagine that variants of this,
such as cohomology (with cup products), or $Z/p$ coefficients,
should be equally simple to do. I also used an idea from the old
Seifert-Threfall text in doing this.
Regards,
[Permission pending]