THE TREE REPRESENTATION OF Σ_{n+1}

Alan Robinson and Sarah Whitehouse

Abstract

We show that the space of fully-grown n-trees has the homotopy type of a bouquet of spheres of dimension n − 3 and that the character of the representation of Σ_{n+1} on its only non-trivial reduced homology group is

ϵ · (Ind_{Σ_{n}}^{Σ_{n+1}} Lie_{n} − Lie_{n+1}).

Introduction

We investigate a certain space T_{n} called the space of fully-grown n-trees, and we prove that it has the homotopy type of a bouquet of spheres of dimension n − 3. The symmetric group Σ_{n+1} acts in a natural way on T_{n}, so the reduced homology of T_{n} affords an integral representation of Σ_{n+1}, which we call the tree representation. It has dimension (n − 1)!. Its restriction to Σ_{n−1} is isomorphic (over the integers) to the regular representation.

We show that the character of the tree representation is

ϵ · (Ind_{Σ_{n}}^{Σ_{n+1}} Lie_{n} − Lie_{n+1})

where ϵ is the alternating character, and Lie_{n} is the character of the representation of Σ_{n} on that component of the free Lie algebra on n generators which is spanned by those words involving each generator exactly once. In the proof we use the Lefschetz fixed-point theorem, and a formula of Brandt [3] to the effect that Lie_{r} = Ind_{C_{r}}^{Σ_{r}} ρ_{r}, where ρ_{r} is a faithful linear character of the subgroup generated by an r-cycle in Σ_{r}.

We became interested in the space T_{n} because it arises in Γ-homology theory for commutative rings. This is very close to the study of E_{∞} structures in homotopy theory, where T_{n} originated [2], and to configuration spaces and free Lie algebras. The connections among these are described in [5]. Restricting the tree representation to Σ_{n} gives ϵ · Lie_{n}. Our Theorem 3.1 therefore implies a result on the top-dimensional homology of configuration spaces due to F. Cohen (see [6], Thm.12.3, p.302) which is also proved by completely different methods in [9]. The restriction to Σ_{n} also yields a known result, due to Stanley [11] on the homology of partition lattices: there is an explicit proof of this in Barcelo [1].

Our results were announced in [10] and [13]. Some related results have since been obtained by Hanlon [8].

Typeset by AMS-TEX

1. The space of fully-grown trees

1.1 Definition. A tree is a compact contractible one-dimensional polyhedron Y. There is just one minimal triangulation of Y, namely that one in which every vertex is either an end (belongs to just one edge, called a free edge) or a node (belongs to at least three edges of Y). Non-free edges of Y are called internal edges. We shall almost always use this triangulation.

From now on, let n ≥ 2. We define an n-tree to be a tree Y in which

(1) there are exactly n + 1 ends, labelled by the integers 0, 1, 2, ..., n;

(2) each internal edge α is assigned a length l(α), where 0 < l(α) ≤ 1. Free edges always have length 1 assigned to them.

An isomorphism Y_{1} ⟶ Y_{2} of n-trees is a homeomorphism which is isometric on edges and which preserves the labelling of the ends. The space T̃_{n} of isomorphism classes of n-trees is a cubical complex. Two trees belong to the same open cube if they are homeomorphic in a fashion which preserves labels and edges of length 1. The coordinates within each cube are given by the internal edge-lengths. (We use here the fact that a tree has no non-trivial automorphisms.) Topologically, T̃_{n} is therefore a finite CW complex.

Since n ≥ 2, the space T̃_{n} has a natural contraction which shrinks all internal edges linearly and simultaneously. Therefore T̃_{n} is a cone. Its apex is the tree with no internal edges; its base is the space T_{n} of trees which are fully grown in the sense that at least one internal edge α has the maximum permitted length l(α) = 1. (The terminology comes from [2].) The symmetric group Σ_{n+1} acts upon T_{n} and T̃_{n} by permuting the labels 0, 1, …, n.

We now investigate the subcomplex T_{n}. We recall that a cell complex has pure dimension r if every cell is a face of some r-cell.

1.2 Proposition.

(1) T_{n} can be triangulated as a simplicial complex of pure dimension n − 3.

(2) Every (n − 4)-simplex of T_{n} is a face of precisely three (n − 3)-simplices.

Proof. The simplices of this new structure on T_{n} are as follows. The vertices are those trees with just one internal edge (which therefore has length 1). From a general tree t ∈ T_{n} we can obtain various vertices v_{α} by stretching one internal edge α to length 1, and shrinking all other internal edges to zero. These v_{α} are the vertices of the simplex in which t lies: the barycentric coordinates of t are proportional to the lengths of the corresponding internal edges. Since such data uniquely determine a fully-grown tree, we have a triangulation of T_{n}.

(The original cell structure on T_{n} is recovered by subdividing each simplex into cubes according to which barycentric coordinate is greatest.)

Each simplex of T_{n} corresponds to a shape of fully-grown tree (i.e. an equivalence class under label-preserving homeomorphism). The maximal simplices correspond to the trees with the most internal edges. These have just three edges at each node. Consideration of the Euler characteristic shows that they have n − 2 internal edges and so give (n − 3)-dimensional simplices of T_{n}.

Any lower-dimensional simplex of T_{n} corresponds to a tree-shape containing a node where more than three edges meet. One can separate such a node into two, introducing a new edge. This process can be continued until a shape is reached which corresponds to an (n − 3)-simplex having the original simplex as a face. Therefore T_{n} has pure dimension n − 3.

Let σ be an (n − 4)-simplex of T_{n}. It corresponds to a tree-shape containing one node ϵ of order four, all other nodes having order three. The node ϵ can be separated in three ways

corresponding to the three ways of pairing off the sub-trees which meet at ϵ. The resulting shapes give the three (n − 3)-simplices having σ as a face. □

As the above proposition might suggest, the complex T_{n} shares many (but not all) of the properties of buildings [12]. In this it resembles the split buildings of Charney [4].

1.3 Definitions. Let i ∈ {0, 1, …, n} be one of the labels of a tree t ∈ T_{n}. The entry node of i is the first node one meets on entering the tree at the end labelled i. It is connected to i by an edge.

Let A be any subset of the set {0, 1, …, n} of labels. We denote by U_{A} the set of trees t ∈ T_{n} in which all i ∈ A have the same entry node. Evidently, U_{A} is a subcomplex of T_{n}. From now on we exclude, usually without further mention, the trivial cases |A| ≤ 1 and |A| ≥ n, which give respectively the whole of T_{n} and the empty set.

1.4 Lemma. The U_{A} are a family of contractible sets which cover T_{n}. Every nontrivial intersection of sets in this family is contractible, or empty.

Proof. In every shape of tree there are two labels with the same entry node. Therefore the sets U_{{i,j}} already cover T_{n}.

Any single U_{A} (where, as usual, 2 ≤ |A| ≤ n − 1) is a conical subset of the closed star of the vertex

and therefore can be linearly contracted to that vertex. (If A = {i, j} consists of two elements, then U_{A} is precisely the closed star.)

Now suppose A is a subfamily such that ⋂_{A∈A} U_{A} is non-empty. Take a tree belonging to a simplex of maximal dimension in this intersection. Shrink all the internal edges, except for one adjoining the entry node of the labels in some (at least) A ∈ A. The whole intersection is a conical subset of the closed star of this vertex, and is therefore contractible. □

1.5 Theorem. There is a homotopy equivalence

T_{n} ≃ ⋁_{(n−1)!} S^{n−3}

and the representation of the subgroup Σ_{n−1} of label permutations on H_{n−3}(T_{n}) is isomorphic to the regular representation.

Proof. By Σ_{n−1} we here understand the group of permutations of any n − 1 of the labels, but we may assume without loss of generality that they are 1, 2, …, n − 1. We consider the subset X = ⋃_{A⊂{1,2,... ,n−1}} U_{A} of T_{n}. This is covered by the contractible subcomplexes U_{{i,j}}, 1 ≤ i, j ≤ n − 1. Every intersection of these is non-empty, because it contains the vertex pictured above with A = {1, 2, …, n−1}. By 1.4, each intersection is contractible. Thus X is contractible.

The complement T_{n} \ X consists only of the interiors of the (n − 3)-dimensional simplices

where (i_{1}, i_{2}, …, i_{n−1}) is any permutation of (1, 2, …, n − 1). Therefore T_{n} is obtained from a contractible space by attaching (n−1)! simplices of dimension n−3 along their boundaries, and these simplices are regularly permuted by the subgroup Σ_{n−1} of the group of label permutations. It follows that T_{n} has the homotopy type of a wedge of (n−1)! spheres of dimension n−3 which are permuted in the standard manner by Σ_{n−1}. □

2. The sets of fixed points

In order to find the character of the action of Σ_{n+1} on H_{n−3}(T_{n}), we investigate the homotopy type of the fixed-point set T_{n}^{g} for each g ∈ Σ_{n+1}. This of course depends upon the cycle type (conjugacy class) of g. In general T_{n}^{g} is not a simplicial subcomplex of T_{n}, but is certainly a subcomplex of its first barycentric subdivision because Σ_{n+1} acts simplicially on T_{n}.

If t is a tree representing a point of T_{n}^{g}, then the permutation g of labels extends to a unique isometry of t with itself, so that t is a tree with a well-defined action of the cyclic subgroup ⟨g⟩. Conversely, any fully-grown tree with ⟨g⟩-action represents a point of T_{n}^{g}. We may therefore regard T_{n}^{g} as the space of (fully-grown) ⟨g⟩-trees.

We introduce the notation

U_{{i,j}}^{g} = U_{{i,j}} ∩ T_{n}^{g}

for the set of ⟨g⟩-trees where i and j have the same entry node. We shall call the set U_{{i,j}}^{g} balanced if i and j are distinct and belong to cycles of equal length, or to the same cycle, in the decomposition of the permutation g.

2.1 Lemma. The balanced sets U_{{i,j}}^{g} cover T_{n}^{g}.

Proof. We know from 1.4 that the collection of all subsets U_{{i,j}}^{g}, balanced or not, covers T_{n}^{g}. Suppose that a tree t belongs to U_{{i,j}}^{g}, where i belongs to a cycle of length m and j belongs to a cycle of shorter length l. Since t is a ⟨g⟩-tree, the entry node of the label i must then be fixed under g^{l}, and so t also belongs to the set U_{{i,g^{l}(i)}}^{g}, which is balanced. Thus the balanced sets are sufficient. □

Let A be any family of balanced sets. We introduce the A-equivalence relation on the set {0, 1, …, n} of labels, defining it to be the smallest equivalence relation which is stable under ⟨g⟩, and for which i ∼ j whenever U_{{i,j}}^{g} ∈ A. Alternatively, consider the set of all the labels as a ⟨g⟩-set. Then the A-equivalence classes are the elements of the quotient ⟨g⟩-set of this by the relations i ∼ j for U_{{i,j}}^{g} ∈ A.

2.2 Lemma. The intersection of a non-empty family A of balanced sets is always contractible, except when there is an A-equivalence class containing n or n+1 labels.

In particular, an individual balanced U_{{i,j}}^{g} is contractible except in certain cases where g is an n-cycle or an (n + 1)-cycle.

Proof. Choose any U_{{i,j}}^{g} in the given family A. Let A be the A-equivalence class of i and j. Provided |A| < n, there is a vertex v of T_{n} (illustrated in 1.4) in which the labels entering at one node are the labels in A. The translates g^{r}(v) span a simplex, of which the barycentre lies in ⋂ A. The whole of ⋂ A can be linearly and equivariantly contracted to this barycentre, which appears as follows.

The above demonstration works in particular when A has a single element U_{{i,j}}^{g}. Therefore the last claim of the Lemma follows from the observation that an Aequivalence class can then only contain n or n + 1 elements if g is an n-cycle or an (n + 1)-cycle and if i, j are labels related by a generator of the cyclic group ⟨g⟩. □

We will need the following result.

2.3 Lemma. Let Λ_{r} be the lattice of proper divisors of the integer r. Then the homotopy type of the nerve N_{r} = |Λ_{r}| is given by

(1) N_{r} ≃ S^{k−2} if r is a product of k distinct primes;

(2) N_{r} ≃ point if r is not square-free.

Proof. (1) We use induction on the number k of prime factors in r. The induction starts, because Λ_{r} is empty when r = 1 or r is prime. For the inductive step, it suffices to prove that N_{pq} is homeomorphic to the suspension of N_{q} when p is prime and (p, q) = 1, q > 1. In this case Λ_{pq} = {p, q} ∪ M, where M = {λ, pλ | λ ∈ Λ_{q}}. The partially-ordered subset M has realization N_{q} ×I, and the divisibility relations involving p and q with elements of M are such that N_{pq} is obtained by attaching a cone on N_{q} to each end of the cylinder |M| ≈ N_{q} × I, the vertices of the cones being the elements p and q. Therefore N_{pq} ≈ SN_{q}, and the induction is complete.

(2) If r is divisible by p^{2}, where p is prime, then the least common multiple map, x ↦ {p, x}, is a deformation retraction onto the sublattice of proper divisors of r divisible by p, which is a cone. □

2.4 Theorem.

(1) If g is a power of an n-cycle or of an (n + 1)-cycle, and thus has cycle type (r)^{s}(1) or (r)^{s}, then the fixed-point set T_{n}^{g} has the homotopy type of a wedge of spheres

T_{n}^{g} ≃ \{ \begin{matrix}⋁_{(s−1)! r^{s−1}} S^{s+k−3} & if r is a product of k distinct primes \\ point & if r is not square-free. \end{matrix}

(2) If g has any other cycle type, then T_{n}^{g} is contractible.

Proof. We first prove (2). Take A to be the family of all balanced sets U_{{i,j}}^{g}. When g is a power of neither an n-cycle nor an (n + 1)-cycle, there is no A-equivalence class containing n or n+1 labels. By Lemma 2.2, all the U_{{i,j}}^{g} and all intersections of them are contractible: therefore their union is contractible. But this union is T_{n}^{g}, by Lemma 2.1. Thus (2) is proved.

We turn now to the proof of (1), in the special case when g is an n-cycle or an (n + 1)-cycle, so that r = n or r = n + 1. As we remarked at the beginning of §2, the cyclic group ⟨g⟩ acts by isometries on every tree t in T_{n}^{g}. Since it acts transitively upon the labels (or upon all labels except 0), such a tree is necessarily star-shaped: the cyclic action has a single fixed point if r = n + 1, and fixes only the edge labelled 0 if r = n.

This implies that T_{n}^{g} is homeomorphic to the nerve N_{r} of the partially-ordered set of proper divisors of r. By 2.3 the special case of (1) is proved.

In the remaining case of (1), when g has cycle type (r)^{s} or (r)^{s}(1) with s > 1, we select one of the r-cycles in the decomposition of g. Without loss of generality we may take this cycle to be (12 … r). Let B be the family of balanced sets U_{{i,j}}^{g} in which i and j belong to cycles other than the selected one. It follows as above from Lemma 2.2 that ⋃ B is contractible: but ⋃ B is no longer the whole of T_{n}^{g}.

Consider any tree t in the complement T_{n}^{g} \ ⋃ B. As t ∉ ⋃ B, the action of ⟨g⟩ must be free on the entry nodes of the elements of each non-selected r-cycle; and only the entry nodes of elements of {1, 2, …, r} may coincide with those of any element of another cycle. It follows that t must have the following form: it is a star-shaped tree from the space N_{r} of proper divisors of r, on each end of which has been attached a frond

with j ∈ {1, 2, …, r}, and each a_{i} chosen from a different non-selected r-cycle. By virtue of the ⟨g⟩-action on t, any one frond (say that with j = 1) determines all the others, so that there are just (s − 1)! r^{s−1} possible patterns of fronds. (If r = n, the label 0 enters at the fixed node.)

Since the fronds introduce s − 1 new barycentric coordinates, we conclude that T_{n}^{g} is obtained from the contractible space ⋃ B by attaching (s − 1)! r^{s−1} copies of the pair (Δ^{s−2}, ∂Δ^{s−2}) ∗ N_{r}, where N_{r} is again the nerve of the partially-ordered set of proper divisors of r. Knowing the homotopy type of N_{r} as above, we deduce that

T_{n}^{g} ≃ \{ \begin{matrix}⋁_{(s−1)! r^{s−1}} S^{s+k−3} & if r is a product of k distinct primes \\ point & if r is not square-free. \end{matrix}

The proof of the theorem is now complete. □

2.5 Corollary. The Euler characteristic of the fixed-point set T_{n}^{g} is given by the formula

χ(T_{n}^{g})−1 = \{ \begin{matrix}(s − 1)! (−r)^{s−1}μ(r) & if g has cycle type (r)^{s} with r > 1, or (r)^{s}(1) \\ 0 & if g has any other cycle type, \end{matrix}

where μ is the standard Möbius function. □

We may note here that on restriction to the subgroup Σ_{n} this agrees with a result which Hanlon [7] obtained for the partition lattice by other methods.

3. The tree representation

3.1 Theorem. The integral representation of Σ_{n+1} on the homology group H_{n−3}(T_{n}) has character

ϵ · (Ind_{Σ_{n}}^{Σ_{n+1}} Lie_{n} − Lie_{n+1})

where ϵ is the alternating character, and Lie_{n} is the character of the representation of Σ_{n} on that component of the free Lie algebra on n generators which is spanned by those words involving each generator exactly once.

Proof. By the Lefschetz fixed-point theorem, the alternating sum of the traces of the homology automorphisms induced by any element g ∈ Σ_{n+1} equals the Euler characteristic of the corresponding fixed-point set T_{n}^{g}. If χ is the character of the representation on H_{n−3}(T_{n}), we have by 2.5 that

(−1)^{n−3}χ(g) = \{ \begin{matrix}(s − 1)! (−r)^{s−1}μ(r) & if g has cycle type (r)^{s} with r > 1, or (r)^{s}(1) \\ 0 & if g has any other cycle type, \end{matrix}

because the only other homology group is the trivial module H_{0}(T_{n}).

On the other hand, the induced character formula gives precisely these values for the virtual character

ϵ · (Ind_{C_{n}}^{Σ_{n+1}} ρ_{n} − Ind_{C_{n+1}}^{Σ_{n+1}} ρ_{n+1})

where ρ_{r} is a faithful linear character of the subgroup of Σ_{n+1} generated by an r-cycle, and ϵ is the alternating character.

Now a result of Brandt [3] for the Lie character implies that Lie_{r} = Ind_{C_{r}}^{Σ_{r}} ρ_{r}. The theorem thus follows from the formula above and the transitivity of induction. □

References

[1] H. Barcelo, “On the action of the symmetric group on the free Lie algebra and the partition lattice,” J. Combin. Theory Ser. A 55 (1990), 93–129.

[2] J.M. Boardman, “Homotopy structures and the language of trees,” Proc. Symp. Pure Math. 22 (1971), 37–58.

[3] A.J. Brandt, “The free Lie ring and Lie representations of the full linear group,” Trans. Amer. Math. Soc. 56 (1944), 528–536.

[4] Ruth M. Charney, “Homology stability for GL_{n} of a Dedekind domain,” Invent. Math. 56 (1980), 1–17.

[5] F.R. Cohen, “Artin’s braid groups, classical homotopy theory, and sundry other curiosities,” in Braids (Santa Cruz, CA), Contemporary Mathematics #78, American Mathematical Society, Providence, RI, 1988, 167–206.

[6] F.R. Cohen, T.J. Lada & J.P. May, “The homology of iterated loop spaces,” Springer Lect. Notes in Math. 533 (1976).

[7] P. Hanlon, “The fixed-point partition lattices,” Pacific J. Math. 96 (1981), 319– 341.

[8] P. Hanlon, “Otter’s method and the homology of homeomorphically-irreducible k-trees,” to appear in J. Combin. Theory Ser. A.

[9] G.I. Lehrer & L. Solomon, “On the action of the symmetric group on the cohomology of the complement of its reflecting hyperplanes,” J. Algebra 104 (1986), 410–424.

[10] C.A. Robinson, “The space of fully-grown trees,” Sonderforschungsbereich 343, Universität Bielefeld, Preprint 92-083, 1992.

[11] R.P. Stanley, “Some aspects of groups acting on finite posets,” J. Combin. Theory Ser. A 32 (1982), 132–161.

[12] J. Tits, “On buildings and their applications,” in Proc. International Congress of Mathematicians, Vancouver, 1974, 209–220.

[13] S.A. Whitehouse, Γ-(Co)homology of commutative algebras and some related representations of the symmetric group, Ph.D. thesis, University of Warwick, 1994.

Mathematics Institute, University of Warwick, Coventry, England CV4 7AL E-mail address: car@uk.ac.warwick.maths, sarah@uk.ac.warwick.maths