Spectral Sequences on Combinatorial Simplicial Complexes.
The goal of this paper is twofold. First, we give an elementary introduction to the usage of spectral sequences in the combinatorial setting. Second we list a number of applications.In the first group of applications the simplicial complex is the nerve of a poset&semi; we consider general posets and lattices, as well as partition-type posets. Our last application is of a different nature: the {\cal S}_n-quotient of the complex of directed forests is a simplicial complex whose cell structure is defined combinatorially.
Introduction
In this paper we use spectral sequences to compute homology groups of combinatorially
given simplicial complexes, whether they come as nerves of posets or
with an explicit combinatorial description of the cell structure.
This idea is not new, in fact spectral sequences have been used for that purpose
in a quite general setting, already in, e.g. [Ba75, Ba77, Ba80], [Q1]. Recently, these
methods have started to take more concrete forms, for example Phil Hanlon used
them in [H] to compute the homology groups of the so-called generalized Dowling
lattices. In the joint paper [FK], Eva Maria Feichtner and the author used spectral
sequences to attack an especially difficult case of subspace arrangements, namely
the so-called D n;k -arrangements.
In Section 2 we define some basic notions. Then, in Section 3, we give a thorough
and elementary, from scratch, description of one possible way to use spectral
sequences for poset homology computations.
In Section 4 we derive several corollaries of the properties of the spectral se-
quences, which can be applied to a wide class of posets. These results include both
M-obius function computations and finding the Betti numbers of a poset. We take
a look at the Whitney homology of a poset and the intriguing questions coming up
in this context. In Theorem 4.1 we prove two inequalities for the Betti numbers of
an arbitrary lattice.
In Section 5 we apply these methods to different partition-type posets. In Sub-section
5.1 we consider the intersection lattices of orbit arrangements, \Pi
Furthermore, we compute completely the homology groups of the particular lattice
\Pi 3;2;2;1 . This example shows that the homology groups of orbit arrangements A -
can have very irregular structure in general, which was not known before. We
remind the reader that it was shown in [Ko1, Theorem 4.1] that when a partition
- has no primitive partition identities then \Pi - is shellable, in particular it is
Date: March 21, 2000
Research at IAS was supported by von Hoffmann, Arcana Foundation.
homotopy equivalent to a wedge of spheres. In Subsection 5.2 we take a look at
the subspace arrangements associated with certain partitions with restricted block
sizes.
In Section 6 we use spectral sequences to study homology groups of the Sn -
quotient of the complex of directed forests \Delta(G n )=Sn . In [Ko2] it was shown that
\Delta(G n ) is shellable. Here we derive a formula for the rational Betti numbers of
\Delta(G n )=Sn and also detect torsion in its integer homology groups.
2. Basic notions and definitions
In this section we introduce the basic notions which we use throughout the text.
Definition 2.1. Let P be a finite poset. The nerve of P , \Delta(P ), (also known as
the order complex of P ), is the abstract simplicial complex whose vertices are
the elements of P and whose faces of dimension k are the chains x
in P . See [Q2] for a more general definition.
If P is explicitly given with adjoint elements then we consider the
simplicial complex \Delta( -
1g. Where it causes no confusion we
often write \Delta(P ) instead of \Delta( -
We also use the convention that unless the bar ( - ) is explicitly written, the
concerned poset always has adjoint elements
For an arbitrary simplicial complex C, e
will denote the kth reduced homology
group of C (see [Sp] for a definition). For the sake of brevity we will often
Furthermore we let -P (x; y) denote the value of the M-obius function on the
interval (x; y) of the poset P . The definition and many properties of the M-obius
function can be found for example in [St1]. We use the convention -
Definition 2.2. A poset P is called Cohen-Macaulay (or just CM) if for every
interval (x; y) of the poset P we have e
2.
Recall that a chain complex C of vector spaces (resp. abelian groups) is a sequence
\Gamma! Cn d
\Gamma!
of vector spaces (abelian groups) and maps between them,
such that d
A filtration on C, a collection of filtrations on
each
all i, j; here we denote F
3. Spectral sequences for the nerves of posets
Spectral sequences constitute a convenient tool for computing the homology
groups of a simplicial complex. Here we give a short description of one possible
way to apply spectral sequences to compute homology groups of the nerve of a poset.
A special case of this particular approach has been previously used by Phil Hanlon,
in the work cited above.
Of course, the filtrations considered here are very special, but we hope that this
may be a good starting point for a combinatorialist. A few good sources for the
material on spectral sequences are [McC, Sp, Mas].
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 3
3.1. The definition and some properties of spectral sequences.
A spectral sequence associated with a chain complex C and a filtration F on C
is a sequence of 2-dimensional tableaux (E r
r=0 , where every component E r
k;i is
a vector space (for simplicity we start with considering field coefficients), E r
unless k; i - 0, and a sequence of differential maps (d r ) 1 r=0 such that
d r
im(E r
k+1;i+r
d r
Comments.
It follows from (0) and (2) that E 1
1. In the general case
k;i is defined using the notion of convergence of the
spectral sequence. We will not explain this notion in general, since for the spectral
sequence that we consider only a finite number of components in every tableau E r
are different from zero, so there exists N 2 N, such that d
one sets
k;i .
2. For the case of integer coefficients, (3.2) becomes more involved: rather than
just summing the entries of one needs to solve extension problems to get
H   (C). This difficulty will not arise in our applications, so we refer the interested
reader to [McC] for the detailed explanation of this phenomena. When considering
integer coefficients, E r
;  are not vector spaces, but just abelian groups.
3. We would like to warn the reader that our indexing is different from the
standard (but more convenient for our purposes). The standard indexing is more
convenient for the spectral sequences associated to fibrations, an instance we do
not discuss in this paper.
For a finitely generated abelian group G, let rk G denote the dimension of the
G. When specializing to a spectral sequence for the homology of the
nerve of a finite bounded poset, we immediately observe that its M-obius function
can be read off from the E r
non-negative integer r.
Proposition 3.1. Let P be a finite poset and (E r
an associated spectral se-
quence, then
Proof. It is a well known fact that
k;i , see for example [McC, Example 6, pp. 15-16].
Furthermore the theorem of Ph. Hall says that
Formula (3.3) follows from (3.4) and (3.5).
As we will see later, formula (3.3) specializes to several well-known formulae for
M-obius function computations, once the spectral sequence is specified.
Proposition 3.2. Let P be any poset and (E r
spectral sequence for
H   (\Delta(P )). Then we have
(for some r
and, for any k,
Proof. From (3.1) we have rk E r+1
and (3.6) follows. It also follows that
We shall now prove (3.8). Let us denote d
n+1;i+r
, then we have the following diagram
d2
n+1;i+r
d3
From the definition of the spectral sequence we know that
hence
Comment. We use here the fact that if G is an abelian group and H is a sub-group
of G then rk
Summing over all i 2 Zin (3.9) we obtain
hence using formula (3.2) we obtain
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 5
3.2. A class of filtrations.
In this subsection we consider all homology groups with coefficients in F, where
F is either a field or the ring of integers. In fact, everything prior to (3.13) is valid
for F being an arbitrary ring.
Let us describe a special class of filtrations on the chain complex for \Delta(P ).
First of all one chooses the following data: J a subposet of -
P and a function
N, such that f( -
other words the preimage of each element in N forms an antichain in J . The most
frequent choices of the function f are the rank function on J (when it exists) and
an arbitrary linear extension of the partial order on J . The choice of J is more
subtle and usually depends heavily on the structure of the poset P , see [FK, H].
Having chosen f and J , we will define an increasing filtration on the chain
complex for \Delta(P ). be a chain (not necessarily
maximal) in P . Define the pivot of \Gamma, piv(\Gamma), to be the element of \Gamma " J with the
highest value of the function f . Since the preimages under f of each natural number
form an antichain, we know that f takes different values on different elements in
hence the notion of pivot is well defined. Furthermore, let the weight
of \Gamma, !(\Gamma), be the value of f on the pivot, i.e.,
take - 0 as a pivot and say that the chain \Gamma has weight 0. This assignment of weights
gives us the filtration of the chain complex C   (P
ff
F
with h \Delta i F denoting the linear span of the given chains with coefficients in F.
Recall that by the definition of the nerve of a poset,
Omitting an element other than the pivot does not alter the weight of the chain,
omitting piv(\Gamma) turns another element into the pivot, on which f takes a lower
value than on the former pivot, so the resulting chain has a strictly lower weight.
Hence the differential operator @ respects the filtration.
By construction, the filtration is bounded from below.
By definition
ff
F
The differential d
k\Gamma1;i is induced by the simplicial boundary operator.
be a generator of
k;i , then
since the weight of a chain is lowered by the omission of an element if and only if
it is the pivot which is removed.
Now we shall replace the chain complexes
chain isomorphic complexes. The latter allow us to give an explicit description of
6 DMITRY N. KOZLOV
the
in terms of the homology groups of certain subposets of P . First
we need some notations: for a 2 J , let S a
f(a)g.
There is an obvious isomorphism between the following chain complexes "divid-
ing" each chain \Gamma in P with pivot a ? - 0 into two chains, namely its subchains below
and above the pivot:
with e
denoting the augmented simplicial chain complex of the respective intervals.
We need to use augmented complexes including the empty chain in order to get
proper counterparts for chains which have the pivot as maximal element below - 1
or as minimal element above - 0.
Let
~
id\Omega ~
with the usual sign conventions, namely ~
@c
p\Omega ~
for c p 2 e
One can see that the isomorphism
commutes with the boundary operators d 0 and ~
@\Omega , respectively. Hence ' is actually
a bijective chain map and we get
For simply have
In case F is a field, or F = Zand at least one of the subposets ( - 0; a) " S a and
S a has free homology groups, we can apply the algebraic K-unneth theorem
and deduce
In this setting, Proposition 3.1 specializes to
Special cases of formula (3.14) can be found in for example [St1]. Observe that
when P is a lattice and
P , and f is an arbitrary order
preserving function on J [ f - 0g, then (3.14) gives Weisner's theorem:
For the explicit derivation of the E 1  ;  -tableau in this case see Theorem 4.1. For
more information on Weisner's theorem itself the reader may want to consult [St1,
Corollary 3.9.3].
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 7
When J is a lower ideal and f is an order-preserving function, i.e. if x ? y then
specializes to
a)\Omega e
4. Applications for general posets
Let P be a pure poset. Form a spectral sequence by choosing
P and
according to (3.15) and (3.12),
rk (a)=i
e
We can read off the so-called Whitney homology groups of P (first introduced
and studied by Baclawski in [Ba75]) from the E 1
e
now P be a CM poset, then
2. It means
that under the first differential d 1 all of the groups W k (P ), except for the highest
one, cancel in some intriguing way. It would be of a great interest to clarify the
combinatorial nature of these cancellations.
Theorem 4.1. Let P be a finite lattice, x an atom in P . Then the following
inequalities hold:
In particular, if fi k\Gamma2 ( - 0;
Proof. Let
P-x and let x be any linear extension of J . Consider
the spectral sequence E which is associated to the ideal J , where we filtrate using
the given linear extension of J . Observe first that -
P-x is contractible.
Also, for any a 2 J , we have (a; -
P-x-a .
This means that (a; -
contractible (actually a cone with apex x- a)
using formulae
(3.12) and (3.15), we obtain
0; otherwise.
The inequalities (4.2) and (4.3) follow from inequalities (3.7), resp. (3.8).
Applications of Theorem 4.1 will be given in the next section. The following
theorem may be occasionally useful.
Theorem 4.2. Let P be a pure poset of rank r. Suppose that there exists a subposet
J of P such that
(2) for any a 2 J , both [ - 0; a] and [a; - 1] J are CM and rk [a; -
e
a)\Omega e
Proof. Construct the spectral sequence
r=0 with the subposet J as in the
proof of the Theorem 4.1 and with f(x) =rk(x). Then it follows from the formulae
and (3.12) that E 1
rk (a)=i;a2J
a)\Omega e
Using the fact that P nJ , [ - 0; a] and [a; - 1] J are CM and that rk (P nJ) =rk (P
r\Gamma2. The spectral sequence collapses
here, hence (4.4) and e
2, follow from (3.2).
Let us recall a theorem proved in [BWal].
Theorem 4.3. (Complementation Theorem).
If L is a bounded lattice, s 2 -
L, and the complements of s form an antichain,
then -
wedge
x?s
Remark 4.4. In the special case, when the complements of an atom x 2 P form
an antichain, the spectral sequence above allows us to derive the homology counter-part
of the Complementation Theorem 4.3.
Reason. If the complements of x form an antichain one can choose the function
f so that it takes the same value v on all of the complements of x. Then there will
be only one non-zero row in E 1
namely
e
All the differentials d r will be zero maps for r - 1, so we obtain
e
5. Applications to partition-type posets
5.1. Orbit arrangements.
A subspace arrangement A is a finite collection of affine subspaces
in the Euclidean space R n . Let A be a central subspace arrangement (all
the subspaces pass through the origin) and take all possible non-empty intersections
t, ordered by reverse inclusion, that is
This is a partially ordered set, which is actually a lattice. The
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 9
bottom element is - and the top element is This
lattice is called the intersection lattice and is often denoted by LA .
We use the notation - for the partition of the number
into blocks of sizes - and we always have these blocks ordered in non-increasing
. By \Pi n we denote the partition lattice
of the set [n]. It is the poset with elements all different partitions of [n] ordered
under refinement.
The following class of subspace arrangements was first introduced in [Bj94, sub-section
3.3]. If nontrivial partition of the set [n], let
The type of - is the number partition of n given by the block sizes jB i j. Given
a non-trivial number partition - ' n, let
A - is called an orbit arrangement, expressing the fact that A - is the orbit
of any single subspace K - under the natural action of Sn on R n . Let \Pi
Note that \Pi
Theorem 5.1. Consider a partition -
notation means that we have m blocks of size 1). Let
2. Then \Pi - is
Remark. For this bound to be useful, we should have much larger
For example, for
Proof. Take a coatom consider the spectral sequence
associated with the ideal We have
e
Let d be the number of blocks in y, then [y; - 1] ' \Pi d (here we use that 2 occurs
as a block size in -). We shall show that d - t. Let y have blocks of sizes
. The set fs gives a number partition of n, means that
- is a refinement of fs g. The condition x - means that there exists
a block of y, without loss of generality we can assume it is s d , such that - is not
a refinement of fs 1g. It means it is impossible to pack disjointly
blocks of sizes - blocks of sizes s
We will attempt to perform such a packing with a version of a greedy algorithm.
Let us start with packing - 1 into some of the blocks s 1. If it is possible
continue with - 2 and so on. At some point we will have to stop. Say we stopped
at - i , i.e., it is impossible to pack - i into the rest (after packing -
the blocks s 1. Then the rests of the blocks s have at most
us an inequality
or
which implies
hence d - t.
The lattice \Pi d has nonzero homology group only in dimension d \Gamma 3, so
using (3.6), we can conclude that \Pi - is
Often spectral sequences can be used for a direct computation of the poset homology
groups. We will give here an informative example.
1). We shall compute the homology groups of \Pi 3;2;2;1 . The poset
\Pi 3;2;2;1 is pure and ranked by the function (the number of blocks in x).
\Pi 3;2;2;1 , f(x) =rk(x), and construct the corresponding spectral sequence.
As was described in Section 4 we obtain Whitney homology groups. It is easy
to see that ( - 0; a) is CM for all a 2 -
\Pi 3;2;2;1 except for the case when a has partition
type (4; 4). These intervals are schematically shown in Figure 1.
Figure

1.
The Betti numbers of intervals ( - 0; a) are given in the following table.
type of a number e
e
e
44
Observe that we can use formulae (3.15) and (3.12), since the intervals ( - 0; a) have
. Hence, the
f(x) =rk(x), can be easily computed. The only non-zero entries are
It is easy to check that the first two rank levels of \Pi 3;2;2;1 form a connected
poset, hence d 1 is exact in E 1
0;1 . It means that
Already this shows that H 1 (\Pi 3;2;2;1 ) 6= 0.
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 11
It is not difficult to show that d 1 is exact in E 1
1;2 too (this will be done later).
Hence the associated spectral sequence collapses at its second term, and the non-zero
entries of the tableau
are:
Hence,
e
In [Ko1, Theorem 4.1] it has been proved that \Pi - is shellable if - has no primitive
partition identities. This of course does not apply to \Pi 3;2;2;1 , since
has the identity 3+ 1. It is however not difficult to adapt the proof of [Ko1,
Theorem 4.1] to show that is shellable. This
adaptation is technical and requires to go into the details of the 4-pages proof of
the mentioned theorem, so we shall omit this argument. Alternatively, one could
show that P is shellable by a direct argument.
Now, associate a spectral sequence ( e
to P in the same way as above. The
Whitney homology groups of P are subgroups of the Whitney homology groups of
\Pi 3;2;2;1 . On the other hand, since P is shellable, d 1 must be exact in e
1;2 . Then,
of course, d 1 is also exact in E 1
1;2 .
5.2. Partitions with restricted block sizes.
Let \Pi n;1;:::;k denote the poset consisting of partitions with block sizes from the
set n). These lattices were considered in [W] in
connection with certain relative subspace arrangements. It is believed that \Pi n;1;:::;k
is torsion-free. We can obtain some information on the homology groups of these
lattices from the following proposition.
Proposition 5.2. \Pi n;1;:::;k is
Proof. \Pi n;1;:::;k is a lower ideal of the partition lattice \Pi n . \Pi n is a CM poset and
\Pi n;1;:::;k contains the first k \Gamma 1 rank levels of \Pi n . Let J be a subposet of \Pi n;1;:::;k
consisting of the complement of the first k \Gamma 1 rank levels of \Pi n , f(x)
Then the formulae (3.13) specialize to
e
since (a; -
Every interval ( - 0; a) is a CM poset of rank rk(a) - k, also P n J is CM of rank
k, hence
Using (3.2) we conclude that e
6. Sn-quotient of the complex of directed forests
In this section we shall assume the following notions to be known: directed graph,
a subgraph of a directed graph, directed tree, directed forest. If needed the reader
may consult any textbook on graph theory for the definitions. We shall use V (G),
resp. E(G), to denote the sets of vertices, resp. edges, of a directed graph G. We
think of E(G) as a subset of (V (G) \Theta V (G)) n f(x; (G)g. Since all the
graphs considered in this section are directed, we will often omit this word.
Following a hint of R. Stanley, [St2], the following simplicial complexes were
considered in [Ko2].
Definition 6.1. Let G be an arbitrary directed graph. Construct a simplicial complex
\Delta(G) as follows: the vertices of \Delta(G) are given by the edges of G and k-
simplices are all directed forests with are subgraphs of G.
Let Gn be the complete directed graph on n vertices, i.e., a graph having exactly
one edge in each direction between any pair of vertices, all together n(n \Gamma 1) edges.
It was shown in [Ko2] that \Delta(G n ) is shellable, thus all its homology groups are 0
except for the top one, and one can show that fi n\Gamma2 (\Delta(G n
Furthermore, there is an action of Sn on \Delta(G n ) induced by the permutation
action of Sn on [n], thus one can form the topological quotient
see

Figure

2 for the case It was asked in [Ko2, Section 6, Question 2]
what H   was. The answer to that turned out to be more complex than we
thought. In this section we show that the groups H   are not, in general,
free, and also give a formula for fi n\Gamma2
A combinatorial description for the cell structure of Xn . Clearly, the
action of Sn on \Delta(G n ) is not free. What is worse, the elements of Sn may fix
the simplices of \Delta(G n ) without fixing them pointwise: for example for
permutation (23) "flips" the 1-simplex given by the directed tree 2 /\Gamma 1 \Gamma! 3.
Therefore, one does not have a bijection between the orbits of simplices of \Delta(G n )
and simplices of Xn . To rectify the situation, consider the barycentric subdivision
We have a simplicial Sn -action on Bn induced from the Sn -
action on \Delta(G n ) and, clearly, Bn =Sn is homeomorphic to Xn . Furthermore, if
an element of Sn fixes a simplex of Bn then it fixes it pointwise. In this situation,
it is well-known, e.g. see [Br], that the quotient projection Bn !
a simplicial structure on Xn , in which simplices of Xn correspond to Sn -orbits of
the simplices of Bn with appropriate boundary relation.
Let us now give a combinatorial description of the Sn -orbits of the simplices of
Bn . Let oe be a simplex of Bn , then oe is a chain of forests on
labeled vertices, such that T i is a subgraph of T i+1 , for dim(oe). One can
view this data in a slightly different way: it is a forest with dim(oe)+1 integer labels
on edges (labels on different edges may coincide). Indeed, given a chain of forests
above, take the forest T dim(oe)+1 and put label 1 an all edges of the forest T 1 ,
label 2 on all edges of T 2 , which are not labeled yet, etc. Vice versa, given a forest
T with a labeling, let T 1 be the forest consisting of all edges of T with the smallest
label, let T 2 be the forest consisting of all edges of T with one of the two smallest
labels, etc. To make the described correspondence a bijection, one should identify
all labeled forests on which labelings produce the same order on edges.
Formally: the p-simplices of Bn are in bijection with the set of all pairs (T; OE T ),
where T is a directed forest on n labeled vertices and OE Z, such that
there exists an order-preserving injection / : Z! Z, such that
The boundary operator is given by: for a p-simplex (T; OE T
takes the same values as OE T except for the edges on which OE T takes ith and
(i+1)st largest values (say a and b), on these edges OE T i takes value a. Furthermore,
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 13
T p+1 is obtained from T be removing the edges with the highest value of OE T , OE Tp+1
is the restriction of OE T . Of course, this description of the boundary map is just
a rephrasing of the deletion of the ith forest from the chain of forests in the original
description. However, we will find it more convenient to work with the labeled
forests rather than the chains of forests.
The orbits of the action of Sn can be obtained by forgetting the numbering of
the vertices. Thus, using the fact that simplices of Xn and Sn -orbits of simplices
of Bn are the same thing, we get the following description.
The p-simplices of Xn are in bijection with pairs (T; OE T ), where T is a directed
forest on n unlabeled vertices and OE T is an edge labeling of T with
modulo a certain equivalence relation. This equivalence relation and the boundary
operator are exactly as in the description of simplices of Bn .
Figure

2.
On

Figure

2 we show the case 3. On the left hand side we have \Delta(G 3 ),
on the right hand side is X . The labeled forests next to the edges
indicate the bijection described above, labeling on the forests corresponding to the
vertices in X 3 is omitted. S 3 acts on \Delta(G 3 ) as follows: 3-cycles act as rotations
around the line which goes through the middles of the triangles, each transposition
acts as a central symmetry on one of the quadrangles, and as a "flip" on the edge
which is parallel to that quadrangle.
Filtration. There is a natural filtration on the chain complex associated to the
simplicial structure on described above. Let F i be the union of all simplices
has at most i edges. Clearly,
The description of the E 1 tableau. Recall that E 1
we use the indexing from Section 3. In other words, the homology is computed
with "truncated" boundary operator: the last term, where some edges are deleted
from the forest, is omitted. Clearly,
where the sum is over all forests with k edges and E T is a chain complex generated
by the simplices (T; OE T ), for various labelings OE T , with the truncated boundary
operator as above.
Let us now describe a simplicial complex whose reduced homology groups, after
a shift in the index by 1, are equal to the nonreduced homology groups of E T . The
arrangement of k(k \Gamma 1)=2 hyperplanes x cuts the space S
simplices, where H is the hyperplane given by the equation x 1
14 DMITRY N. KOZLOV
Denote this simplicial complex A k . The permutation action of S k on [k] induces
an S k -action on A k . It is easy to see that if an element of S k fixes a simplex of
A k , then it fixes it pointwise. Hence, for any subgroup \Gamma ' S k , the \Gamma-orbits of the
simplices of A k are in a natural bijection with the simplices of A k =\Gamma.
Let T be an arbitrary forest with n vertices and k edges. Assume that vertices,
resp. edges, are labeled with numbers acts on [n] by
permutation, let Stab (T ) be stabilizer of T under this action, that is the maximal
subgroup of Sn which fixes T . Then Stab (T ) acts on E(T ), i.e., we have a homomorphism
does not depend on
the choice of the labeling of vertices. However, relabeling the edges changes S(T )
to a conjugate subgroup. Therefore, for a forest T without labeling on vertices and
edges, S(T ) can be defined, but only up to a conjugation.
Proposition 6.2. The chain complex of A k =S(T ) and E T (with a shift by 1 in the
indexing) are isomorphic. In particular, e
Proof. Label the k edges of T with numbers As mentioned above, the
p-simplices of E T are in bijection with labelings of the edges of T with numbers
(using each number at least once). Taking in account the chosen labeling
of the edges, this is the same as to divide the set [k] into an ordered tuple of
non-empty sets, modulo the symmetries of [k] induced by the symmetries of T .
Clearly, these symmetries of [k] are precisely the elements of S(T ).
The (p \Gamma 1)-simplices of A k are in bijection with dividing [k] into an ordered tuple
of p+1 non-empty sets: by the values of the coordinates. Therefore we conclude that
the p-simplices of E T are in a natural bijection with the (p\Gamma1)-simplices of A k =S(T ).
Here the unique 0-simplex of E T , (T; 1), (1 is the constant function taking value 1),
corresponds in A k =S(T ) to the empty set, which is a (\Gamma1)-simplex. One verifies
immediately that the boundary operators of E T and A k =S(T ) commute with the
described bijection. Therefore E T and A k =S(T ) are isomorphic as chain complexes
(after a shift in the indexing). In particular, e
coefficients. Proposition 6.2 allows us to give a description of -entries in
the case when the homology groups are computed with rational coefficients. Indeed,
it is well known that, when a finite group \Gamma acts on a finite simplicial complex X,
one has e
is the maximal vector subspace
of e
acts trivially (more generally Q can be replaced with a field
whose characteristic does not divide j\Gammaj). Since A k is homeomorphic to S k\Gamma2 we
have e
2. It is easy to compute
e
In fact, for -
Q), one has
where sgn denotes the sign homomorphism sgn 1g. Therefore
e
0; otherwise,
where A k is the alternating group, A
Combined with the Proposition 6.2 this gives H i
cases. Therefore it follows
from (6.1) that rk E 1
is equal to the number of forests T
with k edges and n vertices, such that S(T ) ' A k . rk
that fi i
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 15
in [Ko2]), and fi i
In particular, by computing the Euler
characteristic of Xn in two different ways, we obtain
Theorem 6.3. For n - 3, fi n\Gamma2
The first values of f k;n are given in the table below. Note that there are zeroes
on and below the main diagonal and that the rows stabilize at the entry (k;
(for k - 2).
Zcoefficients. The case of integer coefficients is more complicated. In general,
we do not even know the entries of the first tableau. However, we do know that it
is different from the rational case, i.e., torsion may occur.
For example, let T be the forest with 8 vertices and 6 edges depicted on Figure 3.
Clearly, (12)(34)(56)g. It is easy to see that A 6 =S(T ) is a double
suspension (by which we mean suspension of suspension) of RP 2 , thus the only
nonzero homology group is e
In particular, E 1
4;6 is not free.

Figure

3.
2 6On the positive side, we can describe the values which d 1 takes on the "rational"
generators of E 1
us call a forest admissible if S(T ) ' A jE(T )j . For every
admissible forest T with k edges we fix some order on the edges, i.e., a bijection
determines uniquely an integer generator e T of H
by
where we sum over all right cosets of S(T ), (we choose one representative for each
coset). Observe that the sign of g, resp. the simplex (T; g ffi / T ), are the same for
different representatives of the same right coset class, because S(T ) ' A k , resp. by
the definition of S(T ).
Proposition 6.4. For an admissible forest T , we have
ff
where the sum is over S(T )-orbits of E(T ), for which there exists a representative ff,
such that T n ff is admissible, we choose one representative for each orbit; note that
the admissibility of T n ff depends only on the S(T )-orbit of ff, not on the choice of
the representative. Notation in the formula: T n ff denotes the forest obtained from
T by removing the edge ff; ~
defined by ~
~
consists of those permutations
of edges of T n ff which can be extended to T by fixing the additional edge.
Proof. For an admissible forest T with k edges and a bijection OE : E(T
OE) denote a face simplex of (T; OE), where e
T is obtained from T by removing
the edge with the highest label, ~
OE is the restriction of OE to e
T . In our notations
However, for convenience, we use the notation
"tilde" in the rest of the proof.
According to the general theory for spectral sequences, d 1
@ denotes the usual boundary operator, and we view @(e T ) as embedded into the
relative homology group H k\Gamma2 linear combination of simplices
which are obtained from the simplices (T; g ffi / T ) by either merging two
labels, or omitting the edge with the top label. e T 2 H means that
the application of the "truncated" boundary operator to e T gives 0, therefore all
the simplices obtained by merging two labels will cancel out. Furthermore, since
2, and the group H k\Gamma2
freely generated by e U , where U is an admissible forest with edges, we can
conclude that also the contributions ( e
OE), where e
T is not admissible, will cancel
out. Combining these arguments with (6.2) we obtain:
sgn (g)( e
where we have only those terms left in the sum, for which e
T is admissible. After
regrouping we get
sgn (g)( e
ff
sgn (g)( e
where in the second term the first sum is taken over all S(T )-orbits of [k], for which
e
T is admissible, while the second sum is taken over all right cosets S(T )g which
have a representative g such that g ffi / T we take one representative per
coset. To verify (6.5) we just need to observe that the S(T )-orbit of (g
does not depend on the choice of the representative of S(T )g; this follows from the
definition of S(T ).
Finally, one can see that, for ff being an edge of T , such that T n ff is admissible,
sgn (g)( e
S(Tnff)h
where the sum in the first term is again taken over all right cosets S(T )g which
have a representative g such that g ffi / T and the sum in the second term is
simply over all right cosets of S(T n ff).
Indeed, on the left hand side we have a sum over all labelings of E(T ) with
such that ff gets a label k, and we consider these labelings up to
a symmetry of T ; each labeling comes in with a sign of the permutation g, which
is obtained by reading off this labeling in the order prescribed by / T . On the right
hand side the same sum is regrouped, using the observation that to label E(T ) with
[k], so that ff gets a label k, is the same as to label E(T n ff) with [k \Gamma 1]. The only
details which need attention are the multiplicity and the sign.
Every S(T )-orbit of labelings of E(T ) with [k] so that ff gets a label k corresponds
to [S(T
S(T )] of S(T n ff)-orbits of labelings of E(T n ff) with [k \Gamma 1], since
we identify labelings by the actions of different groups: S(T n ff) ' e
S(T ). Each of
this S(T n ff)-orbits comes with the same sign, because S(T n ff) ' A k\Gamma1 . The sign
SPECTRAL SEQUENCES ON COMBINATORIAL SIMPLICIAL COMPLEXES 17
corresponds to the change of the order in which we read off the
edges: instead of reading them off according to / T , we first read off along / Tnff
and then read off the edge ff last. Formally: g ffi /
hence sgn
defined by ~ hj h, ~
Combining (6.4), (6.5) and (6.6) we obtain (6.3).
Homology groups of
just a point. As shown in Figure 2, X 3 ' S 1 , where ' denotes homotopy
equivalence. With a bit of labour, one can manually verify that X 4 ' S 2 . Further-
more, one can see that H 3 (X 5
We leave this
to the reader, while confining ourselves to the case Figure 4 we have all
forests on 6 vertices. We denote some of the forests by two digits. The numbers
over the edges denote the order in which we read the labels, i.e., the bijection / T .
It is easy to see that A k =S(T ) is homeomorphic to S k\Gamma2 for all admissible T , and
is contractible otherwise. The only nontrivial cases are 41, 47, 48, 51, 55, and 59,
all of which can be verified directly. Therefore, the only nontrivial entries of E 1
(Zcoefficients) will lie on the can be computed
from the chain complex 0
k=1 k=2, not admissible31 33213 1
k=3, admissible k=3, not admissible
k=4, not admissible
3 4k=5, admissible
Figure

4.
k=5, not admissible
From Proposition 6.4 we have
here the two-digit strings denote the corresponding forests on Figure 4. Thus
e
Therefore 6 is the smallest value of n, for which the homology groups H
are not free.



--R

Whitney numbers of geometric lattices
Galois connections and the Leray spectral sequence

"Handbook of Combinatorics"
"First European Congress of Mathematics, Paris 1992"
Introduction to compact transformation groups
A homotopy complementation formula for partially ordered sets

The generalized Dowling lattices
Fundamentals of the Theory of Groups

Complexes of directed trees
Exact couples in algebraic topology I
User's Guide To Spectral Sequences
Homotopy properties of the poset of nontrivial p-subgroups of a group
Higher algebraic K-theory I



group actions on subspace arrangements and combinatorics of discriminants
--TR
shellability;homology groups;posets;spectral sequences;graphs