COXETER-LIKE COMPLEXES

ERIC BABSON AND VICTOR REINER

Abstract. Motivated by the Coxeter complex associated to a Coxeter system (W, S), we introduce a simplicial regular cell complex Δ(G, S) with a G-action associated to any pair (G, S) where G is a group and S is a finite set of generators for G which is minimal with respect to inclusion.

We examine the topology of Δ(G, S), and in particular the representations of G on its homology groups. We look closely at the case of the symmetric group 𝔖_{n} minimally generated by (not necessarily adjacent) transpositions, and their type-selected subcomplexes. These include not only the Coxeter complexes of type A, but also the well-studied chessboard complexes.

1. Introduction.

The Coxeter complex Δ(W, S) associated to a Coxeter system (W, S) is a beautiful simplicial complex which encodes the structure of the Weyl chambers for W. Its poset of faces has a very simple description as the poset of cosets of parabolic subgroups ordered by reverse inclusion [20, §1.15]. This description has many consequences for its topology and homology representations.

In this paper, we propose a more general construction of a simplicial cell complex for a pair (G, S) where G is a group and S is any finite generating set which is minimal with respect to inclusion. We observe a number of easy general facts about these complexes in Section 2, and give many examples in Section 3.

In Section 4, we focus on the case where G = 𝔖_{n}, the symmetric group, and S is a set of transpositions. Here S corresponds to a choice of spanning tree on n vertices, and (G, S) forms a Coxeter system exactly when this tree is a path. There turn out to be many constraints on the homology representations of Δ(G, S) in this case, some related to the properties of the spanning tree. In particular, we are led naturally to consider type-selected subcomplexes of Δ(G, S), which turn out to include the much-studied chessboard complexes as a special case.

Key words and phrases. Coxeter complex, simplicial poset, Boolean complex, chessboard complex, Shephard group, unitary reflection group, simplex of groups, homology representation.

Authors supported by NSF grants DMS-0070571 and DMS-9877047.

In Section 5, we look even more closely at the special case where the spanning tree has only one branched vertex (i.e. vertex of degree at least three). Here one can prove further constraints on the homology, and our results are most complete when the unique branched vertex has degree exactly three.

Contents

1. Introduction. 1 2. Generalities. 2 2.1. The cell complex and its face poset. 2 2.2. Pseudomanifolds, links, and singularities. 6 2.3. Morphisms and quotients. 6 2.4. Homology representations. 8 2.5. Type selection. 9 3. Examples. 10 3.1. Euclidean reflection groups. 10 3.2. Unitary reflection groups. 12 3.3. Unipotent groups over 𝔽_{2}. 14 4. The case of the symmetric group. 16 4.1. Trees and forests. 16 4.2. Deletion-contraction and flossing. 18 4.3. Constraints on the homology representations. 21 4.4. Some examples. 25 5. The case of a single branch vertex. 26 5.1. A general lower bound. 27 5.2. The case of three leaves. 28 6. Remarks and questions. 30 7. Appendix: A special case of the connectivity Conjecture 4.12. 31 References 34

2. Generalities.

2.1. The cell complex and its face poset. This section gives the basic construction, and explores some of its general properties. Good references for some of the terminology and facts regarding posets, simplicial complexes and cell complexes are [4] and [5].

Let G be a (finitely generated) group, and S a finite generating set for G which is minimal with respect to inclusion. Given any subset J ⊆ S, let G_{J} denote the subgroup ⟨J⟩ generated by J in G (by analogy with Coxeter groups, call G_{J} a parabolic subgroup). Form the poset P (G, S) whose elements are the cosets {gG_{J} : g ∈ G, J ⊆ S} with ordering by reverse inclusion, i.e. gG_{J} < g′G_{J′} if gG_{J} ⊃ g′G_{J′}. Proposition 2.1. P (G, S) is a simplicial poset in the sense of Stanley [31], that is, every lower interval in P (G, S) is isomorphic to a Boolean algebra.

Proof. It suffices to show that if gG_{K} ⊆ g′G_{K′} then g′G_{K′} = gG_{K′} and K ⊆ K′, since then the interval below gG_{K} in P (G, S) would consist of {gG_{J}|J ⊇ K}, and hence be isomorphic to the Boolean algebra 2^{S−K} via the map gG_{J} ↦ S − J. To show this, we have these implications:

gG_{K} ⊆ g′G_{K′} ⇒ 1 ∈ G_{K} ⊆ g^{−1}g′G_{K′}
⇒ g^{−1}g′G_{K′} = G_{K′}
⇒ g′G_{K′} = gG_{K′}
⇒ gG_{K} ⊆ gG_{K′}
⇒ G_{K} ⊆ G_{K′}
⇒ K ⊆ K′

where the last implication uses the minimality of the generating set S. □

A simplicial poset P is balanced if there is a coloring of the atoms of P so that every maximal element of P lies above exactly one atom of each color. Clearly P (G, S) is balanced with color set S by assigning the atom gG_{S−{s}} the color s.

We have the following immediate consequence. Corollary 2.2. There is a unique (up to isomorphism) balanced regular cell complex of Boolean type [5] or Boolean complex [16] having P (G, S) as its poset of faces. □

We denote this regular cell complex having face poset P (G, S) by Δ(G, S); it will be our main object of study.

The regular nature of the face poset P (G, S) implies that the Boolean complex Δ(G, S) enjoys many of the pleasant properties of Coxeter complexes, which we review here.

Recall that a pure d-dimensional cell complex is gallery-connected if any pair F, F′ of d-faces are connected by a path

F = F_{0}, F_{1}, …, F_{r−1}, F_{r} = F′

of d-faces in which F_{i} and F_{i+1} share a (d − 1)-face for each i. The next proposition is immediate from the definition of P (G, S).

Proposition 2.3. (i) Δ(G, S) is a pure Boolean complex of dimension |S| − 1, which is gallery-connected and balanced with color set S.

(ii) The group G acts transitively on its maximal faces.

(iii) Stabilizers of codimension 1 faces are non-trivial cyclic groups, and the stabilizer of an arbitrary face is the subgroup generated by the stabilizers of the codimension 1 faces containing it. In particular, the transitive G-action on maximal faces is simply transitive.

Remark 2.4. It is not hard to check that the properties listed in the preceding proposition completely characterize the Boolean complexes Δ(G, S). To be precise, if one assumes that Δ is a balanced Boolean complex carrying a G-action satisfying properties (ii),(iii) listed above, then G has a minimal generating set S consisting of a set of generators for the cyclic groups that stabilize the codimension 1 faces of some fixed maximal face of Δ, and Δ ≅ Δ(G, S).

We also note^{1} that Δ(G, S) is a very special case of what has been called a (developable) simplex of groups (see [18, §2.4] and [30]).

Although Δ(G, S) has simplicial cells, it need not be a simplicial complex; see Example 3.4 below. However, there is a simple criterion for this to occur. Given any Boolean complex Δ with vertex set (0cells) V, define an abstract simplicial complex \overline{Δ} on the same vertex set V as follows: F ⊂ V spans a face of \overline{Δ} if and only if there exists at least one cell of Δ containing all the vertices in F. Given any cell σ of Δ, let vertices(σ) denote its set of vertices. The following fact about Boolean complexes is then straightforward. Proposition 2.5. For any Boolean complex, the map

f : Δ →  \overline{Δ}
σ ↦ vertices(σ)

induces a dimension-preserving simplicial surjection.

It is an isomorphism if and only if every cell σ of Δ is uniquely determined by its set of vertices, or equivalently, if and only if Δ is a simplicial complex. □

In the case of Δ = Δ(G, S), there is a natural alternative description of \overline{Δ} which ties it in with Tits coset complexes, as studied in [6] and [17]. Let

C(G, S) = {gG_{S−s} : g ∈ G, s ∈ S}.

1Thanks to Mike Davis for pointing this out.

denote the covering of the set G by the cosets of maximal (proper) parabolic subgroups. Let N (C(G, S)) be the nerve of this covering, that is, the abstract simplicial complex with typical vertex labeled gG_{S−s} and a face {g_{i}G_{S−s_{i}}}_{i=1}^{r} whenever ⋂_{i=1}^{r} g_{i}G_{S−s_{i}} ≠ ∅.

Corollary 2.6. The simplicial complex \overline{Δ(G, S)} which is associated to the Boolean complex Δ(G, S) is N (C(G, S)). Hence the map

\begin{aligned}f : & Δ(G, S) & → & N (C(G, S)) \\ & gG_{J} & ↦ & \{gG_{S−s} : s ∈ S − J\} \end{aligned}

induces a dimension-preserving G-equivariant cellular surjection.

It is an isomorphism if and only if (G, S) satisfies the intersection condition

(2.1)  ⋂_{s∈S−J} G_{S−s} = G_{J}  for every J ⊂ S,

or equivalently, if and only if Δ(G, S) is a simplicial complex.

Proof. The first assertion is a restatement of the definitions. The rest is then a straightforward application of Proposition 2.5. The condition that every cell is uniquely determined by its vertices translates into the intersection condition: we always have an inclusion

G_{J} ⊆ ⋂_{s∈S−J} G_{S−s},

but whenever there exists g ∈ (⋂_{s∈S−J} G_{S−s}) − G_{J} then gG_{J} ≠ G_{J} give two different faces of Δ(G, S) with the same vertex set. □

Remark 2.7. All of the previous results easily generalize to a relative framework that includes Tits buildings associated to groups with a BN-pair. Let G be a group, and B any subgroup. Given a finite subset S ⊂ G which is minimal with respect to inclusion having the property that G = ⟨B, S⟩, define subgroups P_{J} := ⟨B, J⟩ for J ⊆ S. Then the poset P (G, B, S) whose elements are the cosets {gP_{J} : g ∈ G, J ⊆ S} with ordering by reverse inclusion is again a simplicial poset, so it is the face poset of a unique regular cell complex Δ(G, B, S). This Δ(G, B, S) shares many of the properties of Δ(G, S) proven above. In the case where G is a group with BN-pair having associated Coxeter system (W, S), this Δ(G, B, S) is the usual Tits building. Remark 2.8. We should mention that Brown [8] recently studied a (different) topological space built from proper cosets of a group ordered by inclusion. We are not aware of a direct link with his work.

2.2. Pseudomanifolds, links, and singularities. Note that maximal faces of Δ(G, S) are indexed by cosets gG_{∅} = {g} and hence correspond to the elements of G. Codimension one faces are indexed by cosets gG_{{s}}, and such a face will lie in as many facets as the order of s in G. Since Δ(G, S) is gallery-connected, this implies the following. Proposition 2.9. Δ(W, S) is a pseudomanifold if and only if S contains only involutions. When this is the case, Δ(W, S) is orientable as a pseudomanifold if and only if the set map

\begin{aligned}ϵ : & S & → & ℤ^{×} = \{±1\} \\ & s & ↦ & −1 \end{aligned}

extends to a group homomorphism G →^{ϵ} ℤ^{×}. In this situation,

H_{|S|−1}(Δ(G, S), ℤ) ≅ ℤ

and the homomorphism ϵ coincides with the action of G on this top homology.

In the cases where Δ(G, S) is a pseudomanifold, it is often singular. The following trivial proposition about the links of its faces is helpful in understanding its singularities (see [13, §3.3] for a careful discussion of links in simplicial posets). Proposition 2.10. The link of the face indexed by gG_{J} in Δ(G, S) is isomorphic to Δ(G_{J}, J). □

Note that this implies that the singularities of Δ(G, S) are fairly easy to understand by induction on |S|. In particular, we have the following. Corollary 2.11. When S contains only involutions, the singularities of the pseudomanifold Δ(G, S) have codimension at least 3. In particular, when S consists of involutions and |S| ≤ 3, then Δ(G, S) is smooth.

Proof. Use the previous proposition and Proposition 2.3. The link of every codimension 2 face is a gallery-connected pseudomanifold of dimension 1 and hence a sphere. □

2.3. Morphisms and quotients. Given pairs (G, S) and (Ĝ, Ŝ) as above, say that a group homomorphism ϕ : Ĝ → G is a morphism of pairs if ϕ(Ŝ) ⊆ S. The following proposition is straightforward. Proposition 2.12. The map on cosets

ĝĜĴ ↦ ϕ(ĝ)G_{ϕ(Ĵ)}

induces an order-preserving map of posets P (Ĝ, Ŝ) → P (G, S) and hence also a map of Boolean complexes Δ(Ĝ, Ŝ) → Δ(G, S).

Furthermore, surjectivity of the following maps are equivalent:

(i) Δ(Ĝ, Ŝ) → Δ(G, S), (ii) P (Ĝ, Ŝ) → P (G, S), (iii) Ĝ → G, (iv) Ŝ → S.

Lastly, the map Δ(Ĝ, Ŝ) → Δ(G, S) is dimension-preserving if and only if the map Ŝ → S is injective. □

Morphisms of pairs relate to a natural construction of a quotient complex H\Δ(G, S) for a subgroup H of G (here H acts on cosets gG_{J} by left-translation). Because the left-translation action of H on Δ(G, S) is type-preserving (so in particular, a face is stabilized by a group element if and only if it is stabilized pointwise), this quotient is again a Boolean complex whose geometric realization as a topological space is homeomorphic to the quotient space of the geometric realization of Δ(G, S) by the action of H. Its face poset H\P (G, S) has the following description involving double cosets HgG_{J}: the elements of H\P (G, S) are pairs (J, HgG_{J}) where J ⊆ S and g ∈ G, and we define

(J, HgG_{J}) ≤ (J′, Hg′G_{J′}) if J ⊇ J′ and HgG_{J} ⊇ Hg′G_{J′}.

Remark 2.13. The previous definition of H\P (G, S) corrects [24, pp. 12-13], where it was incorrectly asserted that H\P (G, S) is the poset of all double cosets {HgG_{J} : g ∈ G, J ⊆ S} ordered by reverse inclusion. Fortunately, this has no effect on the later results of [24], as they proceed from the (correct) assumption that the faces of H\Δ(G, S) having color set S − J are in bijection with double cosets of the form HgG_{J} inside G.

The slight subtlety here is that whenever there exist coincidences HgG_{J} = HgG_{J′} for J ≠ J′ (as happens in many interesting examples), there will exist different poset elements (J, HgG_{J}) ≠ (J′, HgG_{J′}) with the same double coset in the second coordinate (but different color sets: S − J ≠ S − J′).

A good example of this occurs when H = G, so that HgG_{J} = G for all g ∈ G and all J ⊆ S. Then the quotient complex G\Δ(G, S) is an (|S| − 1)-simplex whose face poset G\P (G, S) has elements (J, G) for J ⊆ S, ordered by reverse inclusion on the first coordinate. Proposition 2.14. Let ϕ : (Ĝ, Ŝ) → (G, S) be a morphism of pairs which is bijective when restricted to a map Ŝ → S, and let

K := ker(ϕ : Ĝ → G).

Then there is an isomorphism of Boolean complexes

K\Δ(Ĝ, Ŝ) → Δ(G, S)

induced by the isomorphism of face posets given by

(Ĵ, KĝĜĴ) ↦ ϕ(ĝ)G_{ϕ(Ĵ)}.

Proof. Using the fact that K is a normal subgroup, so that

KĝĜĴ = ĝKĜĴ = ĝĜĴK

and the fact that G ≅ Ĝ/K, it is easy to check that the above map of face posets is indeed an isomorphism. □

Corollary 2.15. When (G, S) has S consisting of involutions, Δ(G, S) is a quotient of the Coxeter complex Δ(Ŵ , Ŝ) for the Coxeter system (Ŵ , Ŝ) in which the order of ŝŝ′ in Ŵ is defined to be the same as the order of ss′ in G. □

As will been seen in the next section, this corollary can be useful for visualizing examples where |S| is small. Here one can often identify the Coxeter complex Δ(Ŵ , Ŝ) either as a sphere or affine space (when (Ŵ , Ŝ) is finite or affine), and visualize the action of K on this space giving rise to the quotient space Δ(G, S). P. Webb has also pointed out to us that many finite simple groups have involutive generating sets whose presentations (as listed in the Atlas [2]) exhibit them as quotients of Coxeter groups by easily described subgroups. See also [24] for some combinatorics related to quotients of Coxeter complexes.

2.4. Homology representations. From the homological viewpoint, a pleasant feature of Δ(G, S) is the simple description of its cellular chain complex. Given a coefficient ring R, as R[G]-modules, the (augmented) cellular chain groups C_{•}(Δ(G, S), R) with coefficients in R can be described in terms of coset representations R[G/H]:

(2.2)  \begin{aligned}0 → R[G] & → ⨁_{s∈S} R[G/G_{\{s\}}] → \\ & ⋯ → ⨁_{J⊆S:|J|=i} R[G/G_{J}] → ⋯ \\ & → ⨁_{s∈S} R[G/G_{S−s}] → R → 0. \end{aligned}

Here the boundary maps can be defined componentwise, and up to sign, in each component are the natural maps R[G/K] → R[G/H] with [gK] ↦ [gH] whenever K ⊆ H. The homological indexing is given by

C_{i}(Δ(G, S), R) := ⨁_{J⊆S:|J|=|S|−1−i} R[G/G_{J}].

One consequence of this is an expression for the (reduced) Euler characteristic when G is finite:

(2.3) χ(Δ(G, S)) = ∑_{J⊂S}(−1)^{|S|−|J|−1}[G : G_{J}] = |G| ∑_{J⊂S} \frac{(−1)^{|S|−|J|−1}}{|G_{J}|} .

Another immediate consequence is the following description of the top homology as an intersection of kernels. Corollary 2.16.

H_{|S|−1}(Δ(G, S), R) = ⋂_{s∈S} ker(R[G] → R[G/G_{{s}}]). □

The previous corollary already tells us something, when G is finite, about the occurrence of one-dimensional representations of G in the top homology considered as a ℂ[G]-module. We use the notation ⟨V, W ⟩ to denote the inner product of the complex characters of two ℂ[G]- modules V and W. Recall that for any irreducible ℂ[G]-module W, the quantity ⟨V, W ⟩ computes the multiplicity of W in V. Given a subgroup H of G, let V ↓_{H}^{G} and V ↑_{H}^{G} denote the restriction and induction of representations to and from H respectively. Proposition 2.17. Let χ : G → ℂ^{×} be a one-dimensional representation of G. Then

⟨H_{|S|−1}(Δ(G, S), ℂ), χ⟩ = \begin{cases}1 & if for all s ∈ S, one has χ ↓_{G_{\{s\}}}^{G}≠ 1 \\ 0 & else. \end{cases}

Proof. One knows that ℂ[G] = C_{|S|−1}(Δ(G, S), ℂ) carries exactly one copy of each one-dimensional representation χ, namely as the ℂ-span of the element

∑_{g∈G} χ(g^{−1})g.

It is then easy to check that χ ⊆ ker(ℂ[G] → ℂ[G/G_{{s}}]) if and only if χ ↓_{G_{{s}}}^{G}≠ 1, from which the statement follows. □

2.5. Type selection. Whenever one has a balanced Boolean complex Δ with color set S, one can talk about its type-selected or color-selected subcomplex Δ_{J} for J ⊆ S, that is, Δ_{J} is the subcomplex induced on the set of vertices whose color lies in J. Since the face indexed by gG_{J} in Δ(G, S) has color set S − J, the type-selected subcomplex Δ(G, S)_{J} is the unique Boolean complex whose face poset is

P (G, S)_{J} := { cosets gG_{K} : S − J ⊆ K, g ∈ G}

ordered by reverse-inclusion.

The following proposition is the key to many deletion-contraction arguments in Section 4. Proposition 2.18. If G is a group, S is a finite minimal generating set and s ∈ J ⊆ S then there is a short exact sequence of complexes of ℂ[G]-modules

\begin{aligned}0 & → C_{•}(Δ(G, S)_{J−s}) → C_{•}(Δ(G, S)_{J}) \\ & → (C_{•}(Δ(G_{S−s}, S − s)_{J−s}))[1] ↑_{G_{S−s}}^{G}→ 0. \end{aligned}

Here C_{•}[1] denotes the chain complex C_{•} with degree shift by 1, i.e. C_{i}[1] = C_{i−1}, and ↑_{H}^{G} denotes induction of a representation from a subgroup H to G.

Proof. The injective map is induced from the inclusion

Δ(G, S)_{J−s} ↪ Δ(G, S)_{J}.

The rest is straightforward. □

Remark 2.19. The short exact sequence in Proposition 2.18 actually reflects the cofibration sequence

Δ(G, S)_{J−s} ↪ Δ(G, S)_{J} ↠ ⋁_{[G:G_{S−s}]} Susp (Δ(G_{S−s}, S − s)_{J−s})

or in other words, the quotient space Δ(G, S)_{J}/Δ(G, S)_{J−s} is homotopy equivalent to the one-point wedge of [G : G_{S−{s}}] copies of the suspension of Δ(G_{S−{s}}, S −{s})_{J−{s}}. This generalizes [9, Proposition 2.1].

3. Examples.

3.1. Euclidean reflection groups. A Euclidean reflection group W is a finite group acting faithfully on a Euclidean space V and generated by linear reflections^{2}. Such groups are known to have a minimal generating set of reflections S which endows (W, S) with the structure of a Coxeter system (see [20, Chapter 1]). In this case, Δ(W, S) is called the Coxeter complex, and the description of its poset of faces P (W, S) was our motivating example. Here Δ(W, S) triangulates the sphere 𝕊^{dim V −1}, and may be identified with the simplicial decomposition of the unit sphere in V by the reflecting hyperplanes for the reflections in W. There is an extensive literature on Coxeter complexes; see [7] for some references.

2Some authors might apply the term “Euclidean reflection group” to the case where W is possibly infinite but generated by affine reflections. For this reason, one should perhaps call the finite reflection groups that we consider above spherical reflection groups.

Figure 1. Examples of Δ(G, S) which are 2-tori. In (a), G = 𝔖_{4} and S = (12), (13), (14) (cf. [9, Figure 2]). In (b), G is group of 4 × 4 unitriangular matrices over 𝔽_{2} and S is the subset of unitriangular matrices having one non-zero superdiagonal entry and all other entries above the diagonal zero.

On the other hand, if we choose any minimal generating set S of reflections for W, one can still form Δ(W, S), and the fact that the determinant or sign representation ϵ : W → ℤ^{×} is well-defined implies that it will be an orientable pseudomanifold by Proposition 2.9. Example 3.1. The first non-trivial example of the previous discussion occurs when W = 𝔖_{4} the symmetric group on 4 letters, and

S = {s_{1} = (12), s_{2} = (13), s_{3} = (14)},

where (ij) denotes the transposition which swaps i and j. Since |S| = 3, we know that Δ(W, S) is an orientable surface by Proposition 2.11. Its Euler characteristic is easily calculated as in (2.3) to be 0, so it must be a 2-torus.

One can apply Corollary 2.15 to visualize this torus. Consider the affine Coxeter system Ã_{2} = (Ŵ , Ŝ) where Ŝ = {ŝ_{1}, ŝ_{2}, ŝ_{3}} satisfy the following relations: (ŝ_{i})^{2} = (ŝ_{i}ŝ_{j})^{3} = 1 for all i ≠ j. One can check directly that the s_{i}’s satisfy all of these same relations, along with further relations of the form (s_{i}s_{j}s_{i}s_{k})^{2} = 1 with {i, j, k} = {1, 2, 3}. Thus if K is the subgroup of Ŵ generated by all words of the form (ŝ_{i}ŝ_{j}ŝ_{i}ŝ_{k})^{2} as above, then Δ(W, S) is isomorphic to the quotient of the affine Coxeter complex Δ(Ŵ , Ŝ) by the action of K. This affine Coxeter complex is a tessellation of the 2-plane by equilateral triangles, and K acts as a lattice of translations on this 2-plane, leaving a quotient homeomorphic to the 2-torus, which is Δ(W, S), as in Figure 3.1 (a).

It turns out that in this example Δ(W, S) is a simplicial complex (see Proposition 4.2 below), and that it is isomorphic to the 3×4 chessboard complex, first considered by Garst [17] in the context of coset complexes of groups, and later by Björner, Lovasz, Vrecica and Zivaljevic [9] and many other authors (see Example 4.5 below). In [9, p. 30] it was also pointed out that it is a 2-torus.

In Section 4, we discuss the case where W = 𝔖_{n} in more detail.

Example 3.2. The previous example raises the question of which manifolds can be achieved as Δ(G, S). The authors thank M. Özaydin for pointing out the following simple construction which achieves all orientable surfaces (orientable 2-manifolds) in this way. Let

\begin{aligned}G & := D_{4n} × ℤ/2ℤ \\ & = ⟨r, s, t : 1 = r^{2} = s^{2} = t^{2} = (rs)^{2n} = (rt)^{2} = (st)^{2}⟩ \end{aligned}

where D_{m} denotes the dihedral group of order m. We choose S := {r, s, rt}. Since the elements of S are involutions, and the map sending r, s to −1 and t to +1 extends to a homomorphism of G that sends all elements of S to −1, we must have that Δ(G, S) is an orientable surface, and then a quick Euler characteristic computation shows that it has genus n − 1.

3.2. Unitary reflection groups. A unitary reflection group is a finite group acting faithfully on a unitary space (a finite dimensional complex vector space with positive definite Hermitian bilinear form) and generated by unitary reflections, that is, elements of finite order which fix some hyperplane. Such groups were classified by Shephard and Todd [28], and contain many interesting examples. There is one infinite family of such groups G(de, e, r), consisting of the r × r matrices with one non-zero entry in each row and column for which all non-zero entries are (de)^{th} roots of unity, and for which the product of the non-zero entries is a d^{th} root of unity.

Unfortunately, unitary reflection groups seem to lack distinguished sets of generators in general. However, there are at least two wellbehaved subclasses of unitary reflection groups which have them

• the complexifications of Euclidean reflection groups (i.e. extending the action of a Euclidean reflection group acting on ℝ^{n} to ℂ^{n}), and

• the Shephard groups introduced by Shephard [27] and studied further by Coxeter [12], which are the automorphism groups of regular complex polytopes.

For Shephard groups and their distinguished generating sets S, the complex Δ(G, S) has many different descriptions, including some which make no reference to the choice of the generators S- see Orlik [21]. In this situation, Δ(G, S) turns out to be a simplicial complex which is homotopy equivalent to a wedge of spheres of dimension |S|−1, and the homology representation H_{|S|−1}(Δ(G, S), ℤ) has many beautiful guises, which are studied in [22]. Remark 3.3. Motivated by the Coxeter and Shephard cases, along with Corollary 2.16 and Proposition 2.17, one might naively hope that H_{|S|−1}(Δ(G, S), ℤ) carries some canonical representation of G, independent of the choice of the minimal generators S, say for some “nice” groups G.

Unfortunately, even for some of the groups in the infinite family G(de, e, r) this appears to fail, e.g. the rank of H_{|S|−1}(Δ(G, S), ℤ) can depend on the choice of minimal generators. For example, if G = G(6, 2, 2), define unitary reflections

s_{0} = [\begin{matrix}ω^{2} & 0 \\ 0 & 1 \end{matrix}] , s_{1} = [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}] , s_{2} = [\begin{matrix}0 & ω^{−1} \\ ω & 0 \end{matrix}] , s′_{2} = [\begin{matrix}0 & −1 \\ −1 & 0 \end{matrix}]

where ω is any primitive sixth root of unity. Letting

\begin{aligned}S & := \{s_{0}, s_{1}, s_{2}\} \\ S′ & := \{s_{0}, s_{1}, s′_{2}\}, \end{aligned}

one can easily check that both S and S′ are minimal generating sets of unitary reflections for G. However a computer calculation shows that

\begin{aligned}H_{2}(Δ(G, S), ℤ) & ≅ ℤ^{2} \\ H_{2}(Δ(G, S′), ℤ) & ≅ ℤ^{4}. \end{aligned}

Nevertheless, a happy situation occurs when the unitary reflection group G is generated by unitary reflections of order two (involutions).

Perhaps surprisingly, there are many instances where this occurs, even when the group is not the complexification of some Euclidean reflection group (see e.g. the tables at the end of [10]). Any minimal choice of generating involutive reflections S for such a group G will give rise to an orientable pseudomanifold Δ(G, S) (via Proposition 2.9) since the determinant representation is a well-defined homomorphism ϵ : G → ℤ^{×}. Example 3.4. Within the infinite family G(de, e, r), the groups in the subfamily G(2e, e, r) have the aforementioned property of being generated by involutive (unitary) reflections. A close look at the case of G = G(4, 2, 2) also illustrates how the Boolean complex Δ(G, S) can fail to be a simplicial complex. Choose the following generators S = {s_{1}, s_{2}, s_{3}}:

s_{1} = [\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix}, ] s_{2} = [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}, ] s_{3} = [\begin{matrix}0 & −i \\ i & 0 \end{matrix}] .

One can check (see [10, Appendix 2]) that the relations among these s_{i} are generated by

s_{i}^{2} = 1, s_{1}s_{3}s_{2} = s_{3}s_{2}s_{1} = s_{2}s_{1}s_{3}.

These relations have some other consequences, such as

(s_{i}s_{j})^{4} = 1 for i ≠ j
s_{i}s_{j}s_{i} = s_{k}s_{j}s_{k} whenever {i, j, k} = {1, 2, 3}.

An Euler characteristic computation then shows that Δ(G, S) is an orientable surface of genus 4. However, Δ(G, S) is not a simplicial complex, since for example, one can check that the two cosets s_{1}G_{{s_{2},s_{3}}} = s_{3}s_{1}G_{{s_{2},s_{3}}} and G_{{s_{1},s_{3}}} index two vertices which are the endpoints for two different edges, indexed by cosets s_{1}G_{{s_{3}}} and s_{3}s_{1}G_{{s_{3}}}.

3.3. Unipotent groups over 𝔽_{2}. Let G be the unipotent group consisting of all upper unitriangular n × n matrices over 𝔽_{2}, and let S = {s_{1}, …, s_{n−1}} where s_{i} has a 1 in the (i, i + 1) entry and zeroes elsewhere off the diagonal. It is easy to check that S is a minimal generating set for G consisting of involutions. One can also check that the map ϵ : s_{i} ↦ −1 extends to the homomorphism

\begin{matrix}G & →^{ϵ} ℤ^{×} \\ (a_{ij})_{i,j=1}^{n} & ↦ (−1)^{∑_{i=1}^{n−1} a_{i,i+1}} \end{matrix}

Therefore Δ(G, S) is an orientable pseudomanifold by Proposition 2.9.

Biss [3] has shown that all relations among the s_{i} are generated by the following Coxeter-like relations

(3.1)  \begin{aligned}s_{i}^{2} & = 1 \\ (s_{i}s_{i+1})^{4} & = 1 \\ (s_{i}s_{j})^{2} & = 1 for |i − j| > 1, \end{aligned}

along with the extra relations (s_{i}s_{i+1}s_{i+2})^{4} = 1. Consequently Corollary 2.15 implies that Δ(G, S) is a quotient of the Coxeter complex Δ(Ŵ , Ŝ) for the Coxeter system described by the relations (3.1), where one quotients by the normal subgroup K of Ŵ generated by the elements (ŝ_{i}ŝ_{i+1}ŝ_{i+2})^{4}. Example 3.5. Taking the special case where n = 4 in the previous discussion, the Coxeter complex Δ(Ŵ , Ŝ) is the regular tessellation of the 2-plane by isosceles right triangles, and K acts as a 2-dimensional lattice of translations, yielding a quotient Δ(G, S) which triangulates a 2-torus, as in Figure 3.1 (b). As in Example 3.1, the fact that one obtains a 2-torus can be predicted independently by an easy Euler characteristic computation. Example 3.6. We give an example where Δ(G, S) is non-orientable, but still comprehensible. Let

\begin{aligned}G & = 𝔖_{4} \\ S & = \{s_{0} = (12)(34), s_{1} = (23), s_{2} = (34)\}. \end{aligned}

One can easily check that S minimally generates G. By Proposition 2.9, Δ(G, S) will be a non-orientable surface, and an Euler characteristic computation shows that it is in fact the real projective plane.

Alternatively, one can use Corollary 2.15. Note that the s_{i} satisfy the Coxeter relations s_{i}^{2} = (s_{0}s_{1})^{4} = (s_{0}s_{2})^{2} = (s_{1}s_{2})^{3} = 1 for the (finite) Coxeter system (Ŵ , Ŝ) of type B_{3}. One can check that they also satisfy an extra relation: s_{0}s_{1}s_{0}s_{1}s_{2}s_{1}s_{0}s_{1}s_{2} = 1. The left-hand side in this relation happens to coincide with the image of the longest element w_{0} in Ŵ under the surjection Ŵ ↠ G, so the kernel K of this surjection must contain the cyclic group of order two generated by w_{0} in Ŵ. Hence K must coincide with this cyclic group, since |W | = 48 = 2|G|. As Ŵ is the symmetry group of the regular cube or octahedron, Δ(W, S) is a 2-sphere isomorphic to the barycentric subdivision of the boundary of the cube or octahedron. The longest element w_{0} happens to act in this case as the antipodal map on the 2-sphere Δ(Ŵ , Ŝ), and Δ(G, S) is the triangulation of the real projective plane arising from the antipodal identification.

4. The case of the symmetric group.

Here we examine more closely the case where G = 𝔖_{n} considered as a reflection group, and S is a minimal generating set of reflections.

4.1. Trees and forests. The following proposition is easy and wellknown. Proposition 4.1. The reflections in 𝔖_{n} are the transpositions (ij). A set S of transpositions forms a minimal generating set if and only if the graph on vertex set [n] := {1, 2, …, n} having an edge {i, j} for each (ij) in S is a spanning tree. □

In light of this proposition, we introduce the following bit of notation. Given a spanning tree T on [n], let Δ_{T} := Δ(𝔖_{n}, S_{T}) where S_{T} is the corresponding minimal generating set. Proposition 4.2. For any spanning tree T on [n], the pair (𝔖_{n}, S_{T}) satisfies the intersection condition (2.1), and hence Δ_{T} is a simplicial complex.

Proof. Given the spanning tree T with edge set corresponding to S_{T}, for any J ⊂ S_{T}, one has G_{J} = 𝔖_{B_{1}} ×⋯×𝔖_{B_{n−|J|}}, where B_{1}, …, B_{n−|J|} are the blocks of the partition of [n] into the vertices of the trees in the subforest of T induced by the edge subset J. Similarly, for each edge s in S_{T}, there is a corresponding partition of [n] into two blocks B_{1}^{s}, B_{2}^{s} (the bond or cocircuit induced by s) such that G_{S−s} = 𝔖_{B_{1}^{s}} × 𝔖_{B_{2}^{s}}. Showing the intersection condition then amounts to showing

𝔖_{B_{1}} × ⋯ × 𝔖_{B_{n−|J|}} = ⋂_{s∈S_{T} −J} 𝔖_{B_{1}^{s}} × 𝔖_{B_{2}^{s}}

or equivalently, in the lattice of partitions of [n] one has

{B_{1}, …, B_{n−|J|}} = ⋀_{s∈S_{T} −J}{B_{1}^{s}, B_{2}^{s}}.

This is easily shown by induction on n − |J|. □

The simplicial complex Δ_{T} has a useful alternate description. Fix a spanning tree T on [n], so that the vertices of T have a fixed labeling. By a labelled subforest (F, w) of T, we mean a subforest F of T along with an assignment w of a subset of [n] to each tree in F, such that a tree having r vertices is assigned a subset of cardinality r, and these subsets disjointly partition [n]. Order the labelled subforests by saying (F, w) ≤ (F′, w′) if the vertex set of every tree in F is a union of vertex sets of trees in F′, and the corresponding label sets in w are the unions of the label sets in w′.

Proposition 4.3. For any spanning tree T on [n], the face poset P (𝔖, S_{T}) of Δ_{T} is isomorphic to the above partial order on labelled subforests of T.

Proof. A coset wG_{J} corresponds to a pair (F, w) in which F is the subforest of T induced by the edge set J. Here w indicates how to relabel the vertices of T and hence also how to label the vertex sets of the subtrees in F. It is easy to check that this is a poset isomorphism.

□

In fact, the previous description of Δ_{T} suggests a slightly more general family of simplicial complexes which arise naturally as typeselections of Δ_{T}. Given a spanning tree T on [n], let a multiplicity sequence

m = (m_{1}, …, m_{n}) ∈ ℕ^{n}

be an assignment of a non-negative integer m_{i} to each vertex i of T, and call the pair (T, m) a spanning tree with vertex multiplicities. For any such pair (T, m), a labelled subforest is a pair (F, w) where

• F is a subforest of T,

• w is an assignment of a (possibly empty) subset of [m], where m := ∑_{i} m_{i}, to each tree in F,

• each tree in F is assigned a subset of cardinality equal to the sum of the m_{i} as i runs through its vertex set and

• these subsets disjointly partition [m]. Ordering these labelled subforests as before, it is not hard to check

that this defines the face poset of a simplicial complex which we will denote Δ_{T,m}. For example, when m = (1, 1, …, 1), then Δ_{T,m} = Δ_{T}.

It turns out that every complex Δ_{T,m} with m_{i} ≥ 1 is a type-selected subcomplex of a complex ΔT̂ for some spanning tree T̂ on [m] where m = ∑_{i} m_{i}. Given (T, m) with m_{i} ≥ 1, let T̂ be a tree on m vertices and J ⊂ ST̂ a subset of edges such that

• the induced subforest on J has subtrees with m_{i} vertices for each i,

• the tree obtained from T̂ by contracting the edges in J is T (in other words, T is the underlying tree structure connecting the components of the subforest induced by J).

With these definitions, the following proposition is a straightforward translation of the definitions. Proposition 4.4. In the above situation,

Δ_{T,m} ≅ (ΔT̂)_{ST̂−J}.

Example 4.5. Chessboard complexes.

Let T be an n-vertex star, i.e. T has n − 1 leaves each connected to the same central vertex v of degree n − 1. For r ∈ ℕ, define a multiplicity sequence m_{r} by setting m_{i} = 1 for each leaf vertex i, and m_{v} = r. Then one can easily check that Δ_{T,m_{r}} is isomorphic to the (n − 1) × (n + r − 1) chessboard complex Δ_{n−1,n+r−1} considered in [1, 9, 15, 17, 26, 34, 35], whose faces correspond to placements of non-attacking rooks on an (n − 1) × (n − 1 + r) chessboard.

In particular, when T is an n-vertex star,

Δ_{T} = Δ_{T,(1,1,...,1)} = Δ_{T,m_{1}} ≅ Δ_{n−1,n}.

It was noted in [9, §2] that Δ_{n−1,n} is a pseudomanifold with singularities lying in codimension at least 3 (but all other chessboard complexes are not pseudomanifolds), in agreement with Proposition 2.9.

We return to this example in the discussion of Example 4.15. Remark 4.6. For any pair (G, S) having only involutions in S, the facet graph of Δ(G, S), having vertices indexed by maximal faces and an edge for each pair of maximal faces that share a codimension one face, coincides with the (undirected) Cayley graph of G with respect to the generators S. Thus it is possible that the study of Δ(G, S) and its topology may have a bearing on questions about such Cayley graphs.

In particular, when G = 𝔖_{n} and T is a path, so that Δ_{T} is the Coxeter complex for 𝔖_{n}, many questions about this Cayley graph have been answered. For other spanning trees T on [n], less is known, although the case where T is the star graph (so that Δ_{T} is the chessboard complex Δ_{n−1,n} as in Example 4.5) was considered in [14, §5], and studied more extensively in [23].

4.2. Deletion-contraction and flossing. For the remainder of the paper, we examine the topology of Δ_{T}, and particularly the complex representation of 𝔖_{n} on its homology H_{•}(Δ_{T} , ℂ). For this purpose, we will make use of standard terminology about the symmetric group and its complex representations, such as can be found in [25, 32]. In what follows, all simplicial chain groups and homology groups are taken with ℂ coefficients, unless explicitly stated otherwise.

One useful feature of the setting (G, S) = (𝔖_{n}, S_{T}) is that Proposition 2.18 can be re-interpreted in terms of certain deletion and contraction operations, for which we now introduce notation.

Given a spanning tree with multiplicities (T, m) on [n], and an edge e in the tree with vertex set e = {i, j}, one can speak of the contraction T/e in the usual graph-theoretic sense. In other words, T/e has the same vertex set as T except that i, j have been coalesced into a single vertex ij, and the edges of T/e correspond to the edges of T other than e. Further define m/e by

\begin{aligned}(m/e)_{k} & = m_{k} for k ≠ i, j \\ (m/e)_{ij} & = m_{i} + m_{j} \end{aligned}

so that (T/e, m/e) is a spanning tree with multiplicity on [n − 1]. In light of Proposition 4.4, Δ_{T/e,m/e} is the type-selected subcomplex (Δ_{T})_{S_{T} −{e}}.

When one deletes the edge e from T to obtain the graph T −e, it splits into two connected components T′ and T′′ which (up to isomorphism) are trees on vertex sets [n′] and [n′′] respectively where n′ + n′′ = n. Let m′ and m′′ be the multiplicities in m restricted to the vertex sets of T′ and T′′ respectively, so that (T′, m′) and (T′′, m′′) are spanning trees with multiplicity on [n′] and [n′′] respectively.

In this case the exact sequence of Proposition 2.18 becomes the following crucial tool. Proposition 4.7. Given any spanning tree with multiplicities (T, m) on [n], and any edge e of T, there is a short exact sequence of complexes of ℂ[𝔖_{n}]-modules

0 → C_{•}(Δ_{T/e,m/e}) → C_{•}(Δ_{T,m})
→ (C_{•}(Δ_{T′,m′}) ⊗ C_{•}(Δ_{T′′,m′′}))[1] ↑_{𝔖_{n′}×𝔖_{n′′}}^{𝔖_{n}}→ 0. □

There is a particularly useful way to combine two instances of the previous proposition for inductive arguments (used in Subsection 4.3 below), which we will refer to as the flossing induction. Say that a pair of leaf vertices ℓ, ℓ′ in a tree T floss the vertex v if v is the unique branched vertex (i.e. having degree 3 or higher) on the path from ℓ to ℓ′ in T. Proposition 4.8. In any tree T which is not a path, there exists a triple of vertices (ℓ, ℓ̂, v) in which ℓ, ℓ̂ are leaves that floss the vertex v.

Proof. Root the tree T at one of its leaves, so that each edge of T connects a parent vertex to a child vertex, the child being the one further from the root. Also erase the vertices of degree 2 in T, so as to create a homeomorphic (rooted) tree T̄ with possibly fewer edges. Because neither T nor T̄ is a path, in T̄ there will always exist two leaves ℓ, ℓ̂ other than the root which share the same parent vertex v, and these will correspond to a triple (ℓ, ℓ̂, v) in T as desired. □

When ℓ, ℓ̂ floss v, relabel without loss of generality so that

dist_{T} (ℓ, v) ≤ dist_{T} (ℓ̂, v)

Figure 2. An example of flossing induction: two trees T, T̂ related by the two short exact sequences (4.1), (4.2).

where dist_{T} (−, −) denotes graph-theoretic distance in T. Definition 4.9. Define ℓ(T) to be the number of leaves of a tree T. Define

δ(T) := min{dist_{T} (ℓ, v) : (ℓ, ℓ̂, v) such that ℓ, ℓ̂ floss v},

a positive quantity whenever T is not a path, and for convenience define δ(T) = 0 when T is a path.

The flossing induction relates T to a tree T̂ which either has fewer vertices, or the same number of vertices but fewer leaves, or the same number of vertices and leaves but with δ(T̂) < δ(T); see Figure 4.2 for an example. Let (ℓ, ℓ̂, v) be a triple such that dist_{T} (ℓ, v) achieves the minimum δ(T), and define e to be the first edge on the path from v to ℓ. Then T̂ is formed in two steps: one first contracts T along e to create T/e, with a natural multiplicity sequence m/e assigning multiplicity 2 to the contracted vertex and multiplicity 1 on all other vertices, and then one obtains T̂ by “un-contracting” or “stretching” this contracted vertex into a new edge ê that extends along the path toward ℓ′ (equivalently, one can think of T̂ as obtained from T/e by subdividing the first edge along the path from the contracted vertex to ℓ̂).

Note that in this process, one has that T̂/ê = T/e, and hence the spanning tree with multiplicities (T/e, m/e) fits into two short exact sequences coming from Proposition 4.7,

(4.1)  \begin{aligned}0 & → C_{•}(Δ_{T/e,m/e}) → C_{•}(Δ_{T}) \\ & → (C_{•}(Δ_{T′}) ⊗ C_{•}(Δ_{P}))[1] ↑_{𝔖_{n′}×𝔖_{n′′}}^{𝔖_{n}}→ 0 \end{aligned}

(4.2)  \begin{aligned}0 & → C_{•}(Δ_{T̂/ê,m/ê}) → C_{•}(ΔT̂) \\ & → (C_{•}(ΔT̂′) ⊗ C_{•}(ΔP̂))[1] ↑_{𝔖_{n̂′}×𝔖_{n̂′′}}^{𝔖_{n}}→ 0 \end{aligned}

which are illustrated schematically in Figure 4.2. Here we denote by T′, P (= T′′) the two components of T − e, and by T̂′, P̂(= T̂′′), the two components of T̂ − ê, emphasizing the fact that the components P, P̂ which contain ℓ, ℓ̂, respectively, are paths.

We will say that a proof proceeds by flossing induction if it attempts to prove a property of the homology of Δ_{T} as follows. The base case is when T is a path. When T is not a path, one uses induction simultaneously on the number of vertices in T, the number of leaves ℓ(T), and on the quantity δ(T): one assumes that the property holds for any tree having either

• fewer vertices (such as T′, P, T̂′, P̂), or

• the same number of vertices but fewer leaves (such as T̂ if ℓ is adjacent to v in T), or

• the same number of vertices and leaves, but smaller δ value

(such as T̂ if ℓ is not adjacent to v in T), and then uses the long exact homology sequences associated with the sequences (4.1) and (4.2), possibly also taking advantage of the fact that P, P̂ are paths.

Flossing induction is used in the proofs of Theorem 4.10, 4.11, and 5.3 below.

4.3. Constraints on the homology representations. The goal of this subsection is to prove several constraints on the irreducible representations of 𝔖_{n} which can occur in the homology of Δ_{T} or Δ_{T,m}.

Recall that irreducible ℂ[𝔖_{n}]-modules are indexed by partitions λ of n. Let S_{λ} denote the irreducible indexed by λ. Recall that given a ℂ[𝔖_{n}]-module V, the notation ⟨V, S_{λ}⟩ denotes the multiplicity of S_{λ} in V.

We first consider the occurrences of hook representations S_{(r,1^{n−r})} in the homology of Δ_{T}. Theorem 4.10. For any spanning tree T on [n], we have

H_{n−2}(Δ_{T}) ≅ S_{1^{n}}.

For any hook shape (r, 1^{n−r}) and i < n − 2,

⟨H_{i}(Δ_{T}), S_{(r,1^{n−r})}⟩ = 0.

Proof. The first assertion follows from Proposition 2.9. For the rest, we proceed in two steps. Step 1: The case r ≤ 2.

Here we argue directly about the occurrences of S_{(r,1^{n−r})} in the chain groups, and their images under the boundary map.

For r = 1, from the description (2.2) of C_{•}(Δ_{T}) and the irreducible decompositions of the coset representations

ℂ[𝔖_{n}/(𝔖_{n_{1}} × ⋯ × 𝔖_{n_{r}})]

(sometimes called Young’s rule), one sees that S_{1^{n}} occurs exactly once in C_{•}(Δ_{T}), in degree n−2. Thus it must give rise to (n−2)-dimensional homology, in agreement with Proposition 2.9.

Similarly S_{(2,1^{n−2})} occurs • exactly n − 1 times in C_{n−2}(Δ_{T}),

• exactly once in each of the summands ℂ[G/G_{e}] of C_{n−3}(Δ_{T}), as e runs through the n − 1 edges of T,

• nowhere else in C_{•}(Δ_{T}). Based on this, we claim that it would suffice to show the following: there exists

• an ordering e_{1}, e_{2}, …, e_{n−1} of the edges of T, and

• for each i = 1, 2, …, n − 1 a copy V_{i} of the irreducible module S_{(2,1^{n−2})} in ℂ[𝔖_{n}]

with the property that the component maps ∂^{k} : ℂ[G] → ℂ[G/G_{e_{k}}] satisfy

• ∂^{k}(V_{l}) = 0 for k > l
• ∂^{k}(V_{k}) ≠ 0.

This would imply, via a triangularity argument and Schur’s Lemma, that the S_{(2,1^{n−2})}-isotypic component of C_{n−2} maps under the boundary map isomorphically onto that of C_{n−3}, leaving no S_{(2,1^{n−2})} in the homology.

To this end, note that if e has endpoints {i, j}, then ℂ[G/G_{e}] is isomorphic as an ℂ[𝔖_{n}]-module to the principal left ideal ℂ[𝔖_{n}]γ_{{i,j}}^{+}, where we define for any subset A ⊂ [n]

\begin{aligned}γ_{A}^{+} & := ∑_{w∈𝔖_{A}} w \\ γ_{A}^{−} & := ∑_{w∈𝔖_{A}} ϵ(w) w. \end{aligned}

and ϵ is the sign character. Also the e-component ℂ[G] → ℂ[G/G_{e}] of the boundary map is (up to a scalar multiple) the map

\begin{matrix}ℂ[𝔖_{n}] & → & ℂ[𝔖_{n}]γ_{\{i,j\}}^{+} \\ x & ↦ & x · γ_{\{i,j\}}^{+}. \end{matrix}

Order the edges e_{1}, e_{2}, …, e_{n−1} in such a way that for each i, the edge e_{i} has a vertex v_{i} which is a leaf of T − {e_{1}, e_{2}, …, e_{i−1}}. Define V_{k} to be the principal left ideal ℂ[𝔖_{n}]γ_{{v_{k},v′_{k}}}^{+}γ_{[n]−v_{k}}^{−}, where e_{k} has endpoints {v_{k}, v′_{k}}.

It follows from the theory of Specht modules that V_{k} ≅ S_{(2,1^{n−2})}. By construction, whenever k > l we have {v_{k}, v′_{k}} ⊂ [n] − v_{l}, so that γ_{[n]−v_{l}}^{−}γ_{{v_{k},v′_{k}}}^{+} = 0. This implies that

∂^{k}(V_{l}) = V_{l}γ_{{v_{k},v′_{k}}}^{+} = ℂ[𝔖_{n}]γ_{{v_{l},v′_{l}}}^{+}γ_{[n]−v_{l}}^{−}γ_{{v_{k},v′_{k}}}^{+} = ℂ[𝔖_{n}]γ_{{v_{l},v′_{l}}}^{+} · 0 = 0

for k > l. It only remains to show ∂^{k}(V_{k}) ≠ 0, for which it suffices to check that the coefficient of the identity permutation id in γ_{{v_{k},v′_{k}}}^{+}γ_{[n]−v_{k}}^{−}γ_{{v_{k},v′_{k}}}^{+} is exactly +2, coming from the two terms in the product

+id · +id · +id
+(v_{k}v′_{k}) · +id · +(v_{k}v′_{k}).

This completes the case r = 2. Step 2: The case r ≥ 3.

We will argue that ⟨H_{•}(Δ_{T}), S_{(r,1^{n−r})}⟩ = 0 for r ≥ 3 via the flossing induction, explained in Subsection 4.2.

First note that if V_{i} for i ∈ {1, 2} are ℂ[𝔖_{n_{i}}]-modules with n_{i} ≥ 1 and n_{1} + n_{2} = n having the property that ⟨V_{i}, S_{(r,1^{n_{i}−r})}⟩ = 0 for r ≥ 2, then the Littlewood-Richardson rule shows that

⟨(V_{1} ⊗ V_{2}) ↑_{𝔖_{n_{1}}×𝔖_{n_{2}}}^{𝔖_{n}}, S_{(r,1^{n−r})}⟩ = 0 for r ≥ 3.

(In fact, we will only need this in the special case of the Littlewood-Richardson rule known as Pieri’s formula, where V_{2} is the sign representation S_{1^{n_{2}}}; this is due to the fact that P, P̂ are paths, and hence have only the sign representation occurring in the homology of the Coxeter complexes Δ_{P} , ΔP̂).

Since T′, P, T̂′, P̂ all have fewer vertices than T, induction applies to them, and then the Künneth formula along with the previous fact shows that the homology of the third term in both short exact sequences (4.1) and (4.2) contains no occurrence of S_{(r,1^{n−r})} for r ≥ 3. On the other hand, induction also applies to T̂, because it has its shortest distance from a leaf to a branched vertex shorter than in T or else the distance was 1 and T̂ has fewer leaves than T. So the homology of the middle term in (4.2) has no occurrences of S_{(r,1^{n−r})} for r ≥ 2. This implies by the long exact sequence in homology that the homology of the first term in (4.2) contains no occurrences of S_{(r,1^{n−r})} for r ≥ 3. But since T̂/ê = T/e implies that this is the same as the homology of the first term in (4.1), we can conclude that the homology of the middle term in (4.1) has this same property, as desired. □

A similar flossing induction argument gives a bound on the length of the longest row of λ for any S_{λ} which occurs in the homology of Δ_{T}. Theorem 4.11. For any spanning tree T on [n] with ℓ(T) leaves, and any partition λ of n

⟨H_{•}(Δ_{T}), S_{λ}⟩ = 0 unless λ_{1} > ℓ(T) − 1.

Proof. We use flossing induction, as in the last proof, taking advantage of the fact that P, P̂ are paths, so that their homology only contains the irreducible representations S_{1^{n′′}}, S_{1^{n̂′′}} respectively. Note that Pieri’s formula implies that for any partition μ of n′ and λ a partition of n, one has

⟨(S_{μ} ⊗ S_{1^{n′′}}) ↑_{𝔖_{n′}×𝔖_{n′′}}^{𝔖_{n}}, S_{λ}⟩ = 0 if λ_{1} > μ_{1} + 1.

The other crucial facts are that

\begin{aligned}ℓ(T′) & = ℓ(T) − 1 \\ ℓ(T̂′) & = ℓ(T̂) − 1 \\ ℓ(T̂) & ≤ ℓ(T). \end{aligned}

□

We conjecture that the number of leaves ℓ(T) also gives rise to a (loose) lower bound on the connectivity of Δ_{T,m}. Recall that a topological space X is said to be k-connected if its homotopy groups π_{i}(X) vanish for i ≤ k. Conjecture 4.12. For any spanning tree with multiplicities (T, m) on [n] with ℓ(T) leaves, the complex Δ_{T,m} is (n − 1 − ℓ(T))-connected.

This conjecture is well-known and tight for ℓ(T) = 2; see Example 4.14 below. It also turns out to hold when m = (1, 1, …, 1) for ℓ(T) = 3 (see Appendix 7), and is tight in this case by Theorem 5.3. However, see the discussion of chessboard complexes in Example 4.15 below as an illustration of the looseness of this conjectural connectivity bound in general.

Some recent ideas of P. Hersh [19] regarding a notion of weak ordering on (n − ℓ(T))-faces of Δ_{T,m} may lead to a stronger assertion than Conjecture 4.12, namely that the (n − ℓ(T))-skeleton is shellable. Similar results were proven by Ziegler [34], Shareshian and Wachs, [26], and Athanasiadis [1], for chessboard and matching complexes.

Lastly we mention a somewhat trivial constraint on the homology representations of Δ_{T,m} which ignores the tree structure T. Given two partitions λ and μ of the same number, say that λ dominates μ, written λ ▷ μ, if ∑_{i=1}^{k} λ_{i} ≥ ∑_{i=1}^{k} μ_{i} for all k.

Proposition 4.13. Assume m_{1} ≥ ⋯ ≥ m_{n} by re-indexing, if necessary.

Then ⟨H_{•}(Δ_{T,m}), S_{λ}⟩ ≠ 0 implies λ ▷ m.

Proof. The same constraint turns out to hold on the chain level. One checks that C_{•}(Δ_{T,m}) is a direct sum of ℂ[𝔖_{m}]-modules of the form ℂ[𝔖_{m}/(𝔖_{m′_{1}} × ⋯ × 𝔖_{m′_{n′}})] where m′ = (m′_{1}, …, m′_{n′}) is obtained from m by merging parts, and therefore m′ ▷ m. On the other hand, it is well-known from Young’s rule that

⟨ℂ[𝔖_{m}/(𝔖_{m′_{1}} × ⋯ × 𝔖_{m′_{n′}})], S_{λ}⟩ ≠ 0

implies λ ▷ m′. Hence λ ▷ m′ ▷ m. □

4.4. Some examples.

Example 4.14. Rank-selections of Boolean algebras.

In the case when ℓ(T) = 2, so that T is a path with n vertices, the complex Δ_{T,m} is a type-selected subcomplex of the Coxeter complex for 𝔖_{m} where m = ∑_{i} m_{i}. Equivalently, it is the order complex for a rankselection of the Boolean algebra 2^{[m]}. Specifically, if the vertices along the path T are labelled 1, 2, …, n in order, then Δ_{T,m} corresponds to selecting 2^{[m]} at the rank

D_{m} := {m_{1}, m_{1} + m_{2}, …, m_{1} + m_{2} + ⋯ + m_{n−1}}.

The Coxeter complex is shellable, a property which is automatically inherited by all of its type-selected subcomplexes (see e.g. [4, §11]). Hence in this case Δ_{T,m} is homotopy equivalent to a wedge of (n − 2)- spheres, which is (n−3)-connected, in agreement with Conjecture 4.12.

The homology is also well-known as an ℂ[𝔖_{m}]-module (see [33, Theorem 4.3]): the multiplicity of S_{λ} in H_{n−3}(Δ_{T,m}) is the number of standard Young tableaux of shape λ whose descent set is exactly D_{m}.

We should point out that this entire discussion is known to generalize to Coxeter complexes associated to an arbitrary finite Coxeter system (W, S); see [7, Remark 6.7]. The Coxeter complex Δ(W, S) and all of its type-selections Δ(W, S)_{J} are shellable, and their associated homology representations can be expressed in terms of the Kazhdan-Lusztig cell representations corresponding to left cells having a fixed descent set (using an appropriate definition of descents for Coxeter group elements).

Example 4.15. Chessboard complexes revisited.

Recall from Example 4.5 that when T is an n-vertex star and m assigns r to the central vertex and 1 to the remaining vertices, Δ_{T,m} is the chessboard complex Δ_{n−1,n+r−1}. In [9] it was shown that Δ_{m,n} is ν − 2-connected, where we assume m ≤ n and

ν = min (m, ⌊\frac{m + n + 1}{3}⌋) .

It was also conjectured there (and recently proven by Shareshian and Wachs [26]) that this connectivity bound is tight. This shows that the above conjecture on the connectivity of Δ_{T,m} for T a star and m as above is very far from tight: these known results show that in this chessboard case, Δ_{T,m} is roughly \frac{2n+r−2}{3}-connected, while Conjecture 4.12 would only assert that it is 0-connected (i.e. connected) .

The chessboard examples also illustrate how far the homology with complex coefficients can deviate from the integral homology for Δ_{T,m}. The homology with complex coefficients of Δ_{m,n} was described completely by Friedman and Hanlon [15], even as a ℂ[𝔖_{m} × 𝔖_{n}]-module. For example, if T is a star, then using their results for Δ_{n−1,n} one can deduce that H_{i}(Δ_{T} , ℂ) will start to vanish for i roughly below dimension n − \sqrt{n}, while the results of [9, 26] show that the H_{i}(Δ_{T} , ℤ) will only start to vanish for i roughly below dimension \frac{2n}{3}.

5. The case of a single branch vertex.

In this section, we examine more closely the simplicial complexes Δ_{T} (and more generally, Δ_{T,m}) introduced in the previous section, in the case where T is a tree having at most one branch vertex, i.e. at most one vertex of degree 3 or higher. Note that this class encompasses both Examples 4.14 and 4.15.

5.1. A general lower bound. We begin with a companion lower bound for the upper bound on λ_{1} given in Theorem 4.11. Note that this bound is sensitive to the dimension in which the homology occurs. Theorem 5.1. Assume T is a spanning tree on [n] having at most one branch vertex v, and that m achieves its maximum value at m_{v}. Then

⟨H_{i}(Δ_{T,m}), S_{λ}⟩ = 0 if λ_{1} < m_{v} + n − 2 − i.

Remark 5.2. The assumptions that T has only one branch vertex v and that m_{v} achieves the maximum value in m turn out to be necessary here. The spanning tree T on [n] = [8] with edge set

{12, 13, 14, 45, 56, 67, 68}

has more than one branch vertex, and computer calculations show that ⟨H_{4}(Δ_{T}), S_{(2,2,2,2)}⟩ = 1, violating the above inequality. The spanning tree T on [n] = [5] having edge set {12, 23, 34, 35} has one branch vertex v = 3, and if we take m = (2, 1, 1, 1, 1) so that m_{3} = 1 is not the maximum value in m, then computer calculations show ⟨H_{2}(Δ_{T,m}), S_{(2,2,2)}⟩ = 1, violating the above inequality.

Note also that the hypotheses of the theorem are satisfied by the pairs (T, m) for which Δ_{T,m} is a chessboard complex (see Example 4.5).

Proof. We use induction on the number of edges in T and utilize Proposition 4.7, choosing e to be any edge of T incident to the branch vertex v. Note that since λ_{1} < m_{v} + n − 2 − i and (m/e)_{v} ≥ m_{v} + 1, we have λ_{1} < (m/e)_{v} + (n − 1) − 2 − i. Therefore induction applies to show ⟨H_{i}(Δ_{T/e,m/e}), S_{λ}⟩ = 0 so S_{λ} does not occur in the i-dimensional homology of the first term of the short exact sequence of Proposition 4.7.

We wish to show that S_{λ} also does not occur in the i-dimensional homology of the third term of this short exact sequence, so that the desired vanishing would follow from the associated long exact sequence in homology. Without loss of generality, we may assume that T′ is the subtree containing v, so that T′′ is a path. Induction applies to T′, so that ⟨H_{i′}(Δ_{T′,m′}), S_{μ′}⟩ ≠ 0 implies μ′_{1} ≥ m_{v} + n′ − 2 − i′. Also note that Example 4.14 implies Δ(T′′) only has homology in dimension n′′ − 2. Therefore by the Künneth formula, S_{λ} can only occur in the i-dimensional homology of the third term if it occurs in the decomposition of some tensor product S_{μ′} ⊗ S_{μ′′} into irreducibles where n′ + n′′ = n, μ′ ⊢ n′, μ′′ ⊢ n′′ and one has μ′_{1} ≥ m_{v} + n′ − 2 − i′ for some i′ satisfying i′ + (n′′ − 2) = i − 2. On the other hand, the Littlewood-Richardson rule for decomposing this tensor product easily implies that λ_{1} ≥ μ′_{1}. Putting all of these inequalities and equalities together gives λ_{1} ≥ m_{v} + n − 2 − i, a contradiction. □

5.2. The case of three leaves. The case ℓ(T) = 2 was discussed in Example 4.14, and using some of our results constraining the homology, we can now deal with the case where ℓ(T) = 3 with all multiplicities 1, i.e. m = (1, 1, …, 1). Let T_{a,b,c} be the spanning tree on [n] for n = a + b + c + 1 which has a central vertex v of degree 3, and three “arms” consisting of a, b and c other vertices respectively. We assume without loss of generality that a ≥ b ≥ c ≥ 1.

We introduce the following convenience for describing the homology representations of Δ_{T_{a,b,c}}. For two pairs (p, q), (r, s) of positive integers satisfying p + q = r + s = n and p > max(r, s) ≥ min(r, s) > q, define a (virtual) ℂ[𝔖_{n}]-module by the equation

V_{(p,q),(r,s)} ⊕ (S_{1^{p}} ⊗ S_{1^{q}} ↑_{𝔖_{p}×𝔖_{q}}^{𝔖_{n}}) ≅ S_{1^{r}} ⊗ S_{1^{s}} ↑_{𝔖_{r}×𝔖_{s}}^{𝔖_{n}}

which actually turns out to define a genuine (not virtual) representation

(5.1)  V_{(p,q),(r,s)} ≅ ⨁_{k=q+1}^{min(r,s)} S_{(2^{k},1^{n−2k})}.

Theorem 5.3. Let a ≥ b ≥ c ≥ 1 and n = a + b + c + 1. Then Δ_{T_{a,b,c}} has all of its (reduced) integral homology concentrated in dimensions n − 2 and n − 3, and no torsion.

Furthermore, the homology with ℂ coefficients has the following description as an ℂ[𝔖_{n}]-module:

H_{i}(Δ_{T_{a,b,c}}) ≅ \begin{cases}S_{1^{n}} & if i = n − 2 \\ ⨁_{c_{1},c_{2}≥1, c_{1}+c_{2}=c+1} V_{(a+b+c_{1},c_{2}),(b+c_{2},a+c_{1})} & if i = n − 3 \end{cases}

Remark 5.4. Note that using this theorem, one could easily write down a formula which is piecewise-linear in k for the multiplicities

c_{k} := ⟨H_{n−3}(Δ_{T_{a,b,c}}), S_{(2^{k},1^{n−2k})}⟩.

However the presence of the min(r, s) in the formula (5.1) for V_{(p,q),(r,s)} would make this somewhat clumsy. Remark 5.5. Note also that the theorem is consistent with the constraints from Theorems 4.10, 4.11 and 5.1. In fact, these results would suffice to imply all of the assertions about vanishing homology in the theorem, except for the lack of torsion.

Proof. Since Δ_{T_{a,b,c}} has dimension n−2, Theorem 7.3 below implies the result about homology concentration. It also implies that there is no torsion in H_{i}(Δ_{T_{a,b,c}}, ℤ): the only non-vanishing homology groups are the top two, and Proposition 2.9 implies that Δ_{T_{a,b,c}} is an orientable pseudomanifold, which never has torsion in its top two homology groups (see e.g. [29, p. 206, Exerc. 4.E.2]).

We know from Proposition 2.9 that the assertion of the theorem for i = n − 2 is correct, and that this top homology gives the only occurrence of S_{1^{n}}. Thus only the homology in the single dimension n − 3 is unknown, and there can be no two occurrences of the same irreducible module in two different homology groups. It therefore suffices to compute the (virtual-)ℂ[𝔖_{n}]-module Euler characteristic (or Lefschetz character) which is the formal sum of modules

χ(T_{a,b,c}) := ∑_{i≥0}(−1)^{i}⟨H_{i}(Δ_{T_{a,b,c}}), S_{λ}⟩ S_{λ}

For this we again use the two exact sequences (4.1) and (4.2), choosing the edge e on T := T_{a,b,c} to be the edge containing the central vertex v and lying on the arm having c vertices, and choosing the edge ê on T̂ := T_{a+1,b,c−1} to be the edge containing v which lies on the arm having a + 1 vertices (Note: this is again an example of the flossing induction). Let m and m̂ be the multiplicity sequences of all ones on T and T̂ respectively so that (T, m)/e = (T̂, m̂)/ê. If we let P_{r} denote a path having r vertices, these two exact sequences become:

(5.2)

0 → C_{•}(Δ_{T/e,m/e}) → C_{•}(Δ_{T_{a,b,c}})
→ (C_{•}(Δ_{P_{c}}) ⊗ C_{•}(Δ_{P_{a+b+1}}))[1] ↑_{𝔖_{c}×𝔖_{a+b+1}}^{𝔖_{n}}→ 0

0 → C_{•}(Δ_{T̂/ê,m̂/ê}) → C_{•}(Δ_{T_{a+1,b,c−1}})
→ (C_{•}(Δ_{P_{a+1}}) ⊗ C_{•}(Δ_{P_{b+c+1}}))[1] ↑_{𝔖_{a+1}×𝔖_{b+c+1}}^{𝔖_{n}}→ 0

Since Euler characteristics are additive on short exact sequences and multiplicative on tensor products, one concludes that

\begin{aligned}χ(T_{a,b,c}) & = χ(T/e, m/e) − χ(Δ_{P_{c}}) ⊗ χ(Δ_{P_{a+b+1}}) \\ χ(T_{a+1,b,c−1}) & = χ(T̂/ê, m/ê) − χ(Δ_{P_{a+1}}) ⊗ χ(Δ_{P_{b+c+1}}). \end{aligned}

where the symbols ⊗ on the right-hand side should be interpreted as the induction product on virtual characters. Since Δ_{P_{r}} is the Coxeter complex for 𝔖_{r} whose homology vanishes except for S_{1^{r}} in the top dimension, one concludes that

χ(T_{a,b,c}) − χ(T_{a+1,b,c−1})
= S_{1^{b+c}} ⊗ S_{1^{a+1}} ↑_{𝔖_{b+c}×𝔖_{a+1}}^{𝔖_{n}} −S_{1^{a+b+1}} ⊗ S_{1^{c}} ↑_{𝔖_{a+b+1}×𝔖_{c}}^{𝔖_{n}}
= −V_{(a+b+1,c),(b+c,a+1)}

By induction on c, and using the fact that T_{a,b,0} = P_{a+b+1} for the base case, one obtains

χ_{T_{a,b,c}} = (−1)^{n−2} (S_{1^{n}} − ∑_{c_{1},c_{2}≥1,c_{1}+c_{2}=c+1} V_{(a+b+c_{1},c_{2}),(b+c_{2},a+c_{1})})

as desired. □

6. Remarks and questions.

We begin by asking: What is the correct (tight) version of Conjecture 4.12? Can one prove such a result via shellability or vertexdecomposability of some skeleton of Δ_{T,m}, as in [1, 34]?

A different question deals with how the two extremes of trees from Examples 4.5 and 4.14 bound the homology of Δ_{T} for an arbitrary spanning tree T on [n]. Let P_{n} denote the path with n vertices, and Star_{n} the star graph on n vertices. Since for any tree T, the complex Δ_{T} is an orientable pseudomanifold carrying the sign representation of 𝔖_{n} on its top homology (Proposition 2.9), the homology of the Coxeter complex for 𝔖_{n} (that is, Δ_{P_{n}}) trivially gives a lower bound for the multiplicities of irreducible 𝔖_{n}-representations in any homology group H_{·}(Δ_{T} , ℂ). We speculate that the chessboard complex Δ_{n−1,n} (that is Δ_{Star_{n}}) provides a companion upper bound:

Question 6.1. Is it true that for every irreducible 𝔖_{n}-representation S_{λ}, and every spanning tree T on [n], one has

⟨H̃_{i}(Δ_{P_{n}}, ℂ), S_{λ}⟩ ≤ ⟨H̃_{i}(Δ_{T} , ℂ), S_{λ}⟩ ≤ ⟨H̃_{i}(Δ_{Star_{n}}, ℂ), S_{λ}⟩?

One can check using Theorem 5.3 and the results of [15] that the answer is affirmative when T has at most 3 leaves, but we have not checked it extensively in other cases. One could also ask more generally whether there exists a partial ordering ≤ on all spanning trees on [n], roughly from “less branched” to “more branched”, so that paths are at the bottom and stars are at the top, with the property that T ≤ T′ implies

⟨H̃_{i}(Δ_{T} , ℂ), S_{λ}⟩ ≤ ⟨H̃_{i}(Δ_{T′}, ℂ), S_{λ}⟩.

Lastly, we remark that chessboard complexes have the unexpected property that the combinatorial Laplacians defined from their simplicial boundary maps have only integer spectra [15], but unfortunately, the same property is not shared by Δ_{T} in general. This fails, in fact, even when T is a path P_{n} for n ≥ 4.

7. Appendix: A special case of the connectivity Conjecture 4.12.

Our goal here is to use nerve-type arguments as in [9] to prove Theorem 7.3 below. This result confirms Conjecture 4.12 in a very special case needed for the assertions about torsion-free homology in Theorem 5.3: the case where T has 3 leaves, and the multiplicity sequence m assigns 1 to all vertices except possibly for the unique vertex v of degree 3. It is due to the different flavor of the arguments in this proof, and our hope that the conjecture (or a tighter connectivity bound) will eventually be proven, that we have relegated this discussion to an appendix.

Let Δ_{a_{1},...,a_{k}}^{r} denote the complex Δ_{T,m} when T has

• ℓ(T) = k,

• a central vertex v of degree k,

• k arms consisting of a_{i} other vertices each,

• n := 1 + ∑ a_{i} vertices total,

• m assigning multiplicity 1 to all vertices except v,

• m_{v} = r.

For example Δ_{a,b,c}^{1} is what was previously called Δ_{T_{a,b,c}}. We also allow for the possibility that r < 0, even though this was not originally allowed in the definition of Δ_{T,m}; one can check that Δ_{a_{1},...,a_{k}}^{r} is a welldefined, non-empty simplicial complex as long as m := r + ∑_{i} a_{i} ≥ 0. Our goal will be to describe the homotopy type of Δ_{a_{1},a_{2}}^{r} for r an arbitrary integer, and the connectivity of Δ_{a_{1},a_{2},a_{3}}^{r} for r ≥ 1.

We begin with Δ_{a_{1},a_{2}}^{r}. Of course, here the tree T is unbranched, and hence Example 4.14 applies as long as r ≥ 1. But since we are allowing r to be an arbitrary integer, more needs to be said to determine the homotopy type of Δ_{a_{1},a_{2}}^{r} in general.

Lemma 7.1. For a_{1} ≥ a_{2} ≥ 0 and r ∈ ℤ, let

\begin{matrix}m = a_{1} + a_{2} + r \\ n = a_{1} + a_{2} + 1. \end{matrix}

Then the homotopy or homeomorphism type of Δ_{a_{1},a_{2}}^{r} is as follows. For r ≥ 1, one has that Δ_{a_{1},a_{2}}^{r} is a type-selected subcomplex of the

Coxeter complex of type A_{m−1}, and hence homotopy equivalent to a wedge of (n − 2)-spheres.

Otherwise, Δ_{a_{1},a_{2}}^{r} is

a homotopy (m − 2)-sphere if 0 ≤ −r < a_{2}
contractible  if a_{2} ≤ −r < a_{1}
a type A_{m} Coxeter complex if a_{1} ≤ −r < n
empty  if n ≤ −r.

Proof. The assertions for r ≥ 1 and for n ≤ −r follow from the previous discussion.

For r in the range 0 ≤ −r < a_{2}, we use a nerve argument. Cover Δ_{a_{1},a_{2}}^{r} by the stars of the vertices v_{i} for i = 1, 2, …, m, where v_{i} corresponds to the labelled subforest of the path on n vertices which has a singleton on the end-vertex of the a_{1}-vertex branch labelled by the singleton subset {i} and the remaining path of n−1 vertices labelled by the set [m]−{i}. It is easy to check that this indeed covers Δ_{a_{1},a_{2}}^{r}, using the fact that a_{1}+r ≥ 1. One can also check that for any t < m, the intersection of the stars of v_{i_{1}}, …, v_{i_{t}} will have a cone vertex. Specifically, this cone vertex corresponds to the labelled subforest with s = t if t ≤ a_{1} and s = t − r + 1 otherwise, partitioning the path into the s vertices furthest toward the a_{1}-vertex branch, labelled by the set {i_{1}, …, i_{t}}, and the n − s remaining vertices, labelled by the complementary set [m] − {i_{1}, …, i_{t}}. On the other hand, for t = m, this labelled subforest is no longer a vertex as it does not partition the path into two sets (the second set has cardinality n − t + r − 1 = n − m + r − 1 = 0), and in fact the intersection of all of the stars of the v_{i} is the empty face. Hence by the usual nerve lemma (see [4, (10.7)], or the limiting case k = ∞ in the Lemma 7.2 below), Δ_{a_{1},a_{2}}^{r} is homotopy equivalent to the nerve of this covering, which is the boundary of an (m−1)-dimensional simplex, so an (m − 2)-sphere.

The same nerve argument works for r in the range a_{2} ≤ −r < a_{1}. The only difference is that now for t = m ≤ a_{1} the intersection will no longer be the empty face, and will again have a cone vertex corresponding to the labelled subforest described as the first case in previous paragraph. Hence the usual nerve lemma implies that Δ_{a_{1},a_{2}}^{r} is contractible in this situation.

If a_{1} ≤ −r < n = a_{1} + a_{2} + 1, we repeatedly use the following isomorphism of simplicial complexes:

(7.1)  Δ_{a_{1},a_{2}}^{r} ≅ Δ_{a_{1},a_{2}−1}^{r+1} if a_{1} + r < 0.

This isomorphism (7.1) is a special case of the inclusion in the cofibration sequence of Remark 4.7, in which e is one of the two edges incident to the vertex v, namely the edge pointing toward the branch having a_{2} vertices. Here the inclusion is also surjective (and hence an isomorphism) because the assumption that a_{1} + r < 0 implies every non-trivial labelled subforest must use e in one of its subtrees. We obtain

Δ_{a_{1},a_{2}}^{r} ≅ Δ_{a_{1},m}^{−a_{1}} ≅ Δ_{m,m}^{−m}

by applying the isomorphism (7.1) first −(r + a_{1}) times to lower the a_{2} in the subscript, and then −(r + a_{2}) times to lower the a_{1} in the subscript.

It only remains to describe an isomorphism from Δ_{m,m}^{−m} to the Coxeter complex of type A_{m}. Given a typical labelled subforest corresponding to a face of Δ_{m,m}^{−m}, its subtrees are labelled by sets which give an ordered decomposition of [m], i.e. a sequence of sets B_{1}, …, B_{r} with [m] = ⨿_{i}B_{i}, where it is possible that the set B_{i_{0}} labeling the unique subtree containing vertex v is the empty set. Replacing B_{i_{0}} by B_{i_{0}} ∪ {m + 1} gives an ordered decomposition of [m + 1] into non-empty sets, which labels a typical face in the Coxeter complex of type A_{m}. One can easily

check that this is the desired isomorphism.  □  □

For the case of Δ_{a_{1},a_{2},a_{3}}^{r}, we use a connectivity nerve lemma from [9]. Lemma 7.2. [9, Lemma 1.2] Let Δ be a simplicial complex covered by a family {Δ_{i}}_{i=1}^{s}. Suppose that every non-empty intersection ⋂_{j=1}^{t} Δ_{i_{j}} is (k − t + 1)-connected for t ≥ 1. Then Δ is k-connected if and only if the nerve of the covering {Δ_{i}}_{i=1}^{s} is k-connected. □ Theorem 7.3. Given a_{1}, a_{2}, a_{3} ≥ 0, let n = a_{1} + a_{2} + a_{3} + 1.

If r ≥ 1, the complex Δ_{a_{1},a_{2},a_{3}}^{r} is (n − 4)-connected. In particular, Δ_{T_{a,b,c}} is (n − 4)-connected. Remark 7.4. Note that this agrees with Conjecture 4.12 in this case, since ℓ(T) = 3 here. Remark 7.5. Although Δ_{a_{1},a_{2},a_{3}}^{r} is a well-defined simplicial complex even for r negative, some lower bound on r is necessary for the conclusion of the theorem. For example, the complex Δ_{1,1,1}^{−2} is isomorphic to the 1 × 3 chessboard complex, and has n = 4, but is disconnected, i.e. not 0-connected.

Proof. We use a nerve argument as in the proof of the previous theorem, but applying Lemma 7.2. Cover Δ_{a_{1},a_{2},a_{3}}^{r} by the stars of the vertices v_{i} for i = 1, 2, …, m, where v_{i} corresponds to the labelled subforest which has a singleton on the end-vertex of the a_{1}-vertex branch labelled by the singleton subset {i} and the remaining tree of n−1 vertices labelled by the set [m] − {i}. As before, these stars do indeed cover Δ_{a_{1},a_{2},a_{3}}^{r}, using the fact that a_{1} + r ≥ 1. Also as before, one can check that for any t ≤ min(a_{1}, m − 1), the intersection of the stars of v_{i_{1}}, …, v_{i_{t}} will have a cone vertex with a similar description to the one in the previous proof: the branch with a_{1} vertices has an end subtree labelled by the set {i_{1}, …, i_{t}}, and the remaining vertices form a subtree labelled by the complementary set [m] − {i_{1}, …, i_{t}}.

For t in the range a_{1} < t < m, one can check that the intersection of the stars of v_{i_{1}}, …, v_{i_{t}} is isomorphic to Δ_{a_{2},a_{3}}^{r+a_{1}−t}. By checking various cases using Lemma 7.1, one concludes that Δ_{a_{2},a_{3}}^{r+a_{1}−t} is always at least (n − 3 − t)-connected for t in this range.

Finally, if t = m, this intersection of stars is the empty face. This means that the nerve of this covering is the boundary of an (m − 1)- simplex, and hence (m − 3)-connected. Since r ≥ 1 implies m − 3 ≥ n − 3, the nerve is (n − 3)-connected, and we can apply Lemma 7.2 to conclude that Δ_{a_{1},a_{2},a_{3}}^{r} is (n − 3)-connected. □

References

[1] C. Athanasiadis, Decompositions and connectivity of matching and chessboard complexes, preprint, 2002.

[2] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, R.A. Wilson, Atlas of finite groups, Oxford University Press, Eynsham, 1985.

[3] D. Biss, A presentation for the unipotent group over 𝔽_{2}. Comm. Algebra 26 (1998), 2971–2975.

[4] A. Björner, Topological methods. Handbook of combinatorics, Vol. 1, 2, 1819– 1872, Elsevier, Amsterdam, 1995.

[5] A. Björner, Posets, regular CW complexes and Bruhat order. European J. Combin. 5 (1984), 7–16.

[6] A. Björner, Some Cohen-Macaulay complexes arising in group theory. Commutative algebra and combinatorics (Kyoto, 1985), 13–19, Adv. Stud. Pure Math. 11, North-Holland, Amsterdam, 1987.

[7] A. Björner, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings. Advances Math. 52 (1984), 173–212.

[8] K.S. Brown, The coset poset and probabilistic zeta function of a finite group. J. Algebra 225 (2000), 989–1012.

[9] A. Björner, L. Lovász, S.T. Vrećica, and R.T. Živaljević, Chessboard complexes and matching complexes. J. London Math. Soc. 49 (1994), 25–39.

[10] M. Broué, G. Malle, and R. Rouquier, Complex reflection groups, braid groups, Hecke algebras. J. Reine Angew. Math. 500 (1998), 127–190.

[11] M. Chari, On discrete Morse functions and combinatorial decompositions. Discrete Math. 217 (2000), 101–113.

[12] H.S.M. Coxeter, Regular complex polytopes. Second edition. Cambridge University Press, Cambridge, 1991.

[13] A.M. Duval, Free resolutions of simplicial posets. J. Algebra 188 (1997), 363– 399.

[14] P.H. Edelman, On inversions and cycles in permutations. Europ. J. Combinatorics 8 (1987), 269–279.

[15] J. Friedman and P. Hanlon, On the Betti numbers of chessboard complexes. J. Algebraic Combin. 8 (1998), 193–203, (with printing errors corrected in J. Algebraic Combin. 9 (1999)).

[16] A.M. Garsia and D. Stanton, Group actions of Stanley-Reisner rings and invariants of permutation groups. Adv. in Math. 51 (1984), 107–201.

[17] P.F. Garst, Cohen-Macaulay complexes and group actions, Ph.D. Thesis, Univ. of Wisconsin-Madison, 1979.

[18] A. Haefliger, Complexes of groups and orbihedra. Group theory from a geometrical viewpoint (Trieste, 1990), 504–540, World Sci. Publishing, River Edge, NJ, 1991.

[19] P. Hersh, personal communication, June 2002.

[20] J.E. Humphreys, Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics 29, Cambridge University Press, Cambridge, 1990.

[21] P. Orlik, Milnor fiber complexes for Shephard groups. Adv. Math. 83 (1990), 135–154.

[22] P. Orlik, V. Reiner, and A.Shepler, The sign representation for a Shephard group, to appear in Math. Annalen.

[23] I. Pak, Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees. Discrete Math. 204 (1999), 329–335.

[24] V. Reiner, Quotients of Coxeter complexes and P -partitions, Mem. Amer. Math. Soc. 95 (1992), no. 460.

[25] B.E. Sagan, The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition. Graduate Texts in Mathematics 203. Springer-Verlag, New York, 2001.

[26] J. Shareshian and M. Wachs, Homology of matching and chessboard complexes, Extended abstract, Formal Power Series and Algebraic Combinatorics. 13th International Conference, Arizona State University, Tempe, 2001.

[27] G.C. Shephard, Regular complex polytopes. Proc. London Math. Soc. 2, (1952), 82–97.

[28] G.C. Shephard and J.A. Todd, Finite unitary reflection groups. Canadian J. Math. 6, (1954), 274–304.

[29] E.H. Spanier, Algebraic topology. McGraw-Hill Book Co., New York-Toronto-London 1966.

[30] J.R. Stallings, Non-positively curved triangles of groups. Group theory from a geometrical viewpoint (Trieste, 1990), 491–503, World Sci. Publishing, River Edge, NJ, 1991.

[31] R.P. Stanley, f-vectors and h-vectors of simplicial posets. J. Pure Appl. Algebra 71 (1991), 319–331.

[32] R.P. Stanley, Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics 62. Cambridge University Press, Cambridge, 1999.

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

[34] G.M. Ziegler, Shellability of chessboard complexes. Israel J. Math. 87 (1994), 97–110.

[35] R.T. Živaljević and S.T. Vrećica, The colored Tverberg’s problem and complexes of injective functions. J. Combin. Theory Ser. A 61 (1992), 309–318.

Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195-4350

E-mail address: babson@math.washington.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

E-mail address: reiner@math.umn.edu