HOMOTOPY TYPE OF THE BOOLEAN COMPLEX OF A COXETER SYSTEM

KÁRI RAGNARSSON AND BRIDGET EILEEN TENNER

Abstract. In any Coxeter group, the set of elements whose principal order ideals are boolean forms a simplicial poset under the Bruhat order. This simplicial poset defines a cell complex, called the boolean complex. In this paper it is shown that, for any Coxeter system of rank n, this boolean complex is homotopy equivalent to a wedge of (n − 1)-dimensional spheres, and the number of such spheres can be computed recursively. Specific calculations of this number are given for all finite and affine irreducible Coxeter systems, as well as for systems with graphs that are disconnected, complete, or stars. One implication of these results is that the boolean complex is contractible if and only if a generator of the Coxeter system is in the center of the group.

1. Introduction

The boolean complex of a finitely generated Coxeter system (W, S) arises from the Bruhat order on W. Regarding W as a poset in the Bruhat order, we define the boolean ideal 𝔹(W, S) ⊆ W to be the subposet consisting of those elements whose principal order ideals are boolean. The boolean ideal is a simplicial poset, and, as the name suggests, it is an order ideal of W. In fact, it is maximal among order ideals that are simplicial posets. The boolean complex is defined as the regular cell complex Δ(W, S) associated to 𝔹(W, S). That is, the cell complex that has 𝔹(W, S) as its face poset.

The elements in 𝔹(W, S) are easily described: an element in 𝔹(W, S) is an element of W that can be written as a product of distinct elements from the generating set S. Consequently the boolean complex is pure, with each maximal cell having dimension |S| − 1. These elements play an important role in the study of Coxeter groups because their boolean nature has a variety of consequences related to Rpolynomials, Kazhdan-Lusztig polynomials, and g-polynomials (see [2]).

As described above, elements of the boolean ideal are products of distinct elements of the generating set S, and thus are governed by the commutability of elements of S. Consequently, this ideal is determined by the Coxeter graph of (W, S). Recall that the Coxeter graph G = G(W, S) has vertex set S, with an edge between vertices s and t if and only if s and t do not commute in W. An edge is labeled by the order m(s, t) of st ∈ W when m(s, t) > 3. Since we are only concerned with the commutability of generators in this paper, we suppress the labels and consider the underlying unlabeled graph. Because elements of S are involutions, the elements s and t commute if and only if m(s, t) = 2, and hence if and only if the vertices s and t are non-adjacent in G. For more information about Coxeter systems, see [1].

Date: June 5, 2008.

2000 Mathematics Subject Classification. Primary 20F55; Secondary 05E15, 06A07, 55P15.

From the graph G, one constructs a simplicial poset 𝔹(G) whose elements are equivalence classes of strings of distinct elements of S, where two strings are equivalent if one can be transformed into the other by commuting elements that are non-adjacent in G. The partial order on 𝔹(G) is induced by substring inclusion. Of course, when G = G(W, S), the poset 𝔹(G) is isomorphic to the poset 𝔹(W, S), so this construction recovers the boolean ideal from the (unlabeled graph underlying the) Coxeter graph. We refer to 𝔹(G) as the boolean ideal of G, and to the associated regular cell complex Δ(G) as the boolean complex of G.

Example 1.1. If the graph G consists of two vertices and a single edge between them, then the poset 𝔹(G) and the boolean complex Δ(G) are depicted in Figure 1.

(a) 1 2 (b) 21 1  2 ∅ 12 (c)  21 1  2 12

Figure 1. (a) A graph G. (b) The poset 𝔹(G). (c) The boolean complex Δ(G), with geometric realization |Δ(G)| ≃ S^{1}.

Because their unlabeled Coxeter graphs are the same, Example 1.1 applies to the Coxeter groups A_{2}, B_{2}/C_{2}, G_{2} and I_{2}(m), and shows that in each case the geometric realization of the boolean complex is homotopy equivalent, denoted ≃, to the unit circle S^{1}. In this paper, we prove more generally that the boolean complex of any finite simple graph, and hence of any Coxeter system, has geometric realization homotopy equivalent to a wedge of top dimensional spheres, and give a recursive formula for calculating the number of these spheres. In specific cases, including the finite and affine irreducible Coxeter systems, we calculate this number explicitly.

The subsequent organization of this paper begins with a section precisely defining the primary objects and putting this project in the greater context of the study of the Bruhat order of Coxeter group. This is followed by a discussion of previous work for somewhat related complexes. Section 4 states the main result of the article, that the boolean complex for any finite simple graph is homotopy equivalent to a wedge of a particular number of top dimensional spheres. The homotopy types for the boolean complexes of the finite and affine irreducible Coxeter systems are given as a corollary in this section. Section 5 discusses discrete Morse theory, which is the main tool in the proof presented in Section 6. A selection of corollaries to the main theorem are given in Section 7. Section 8 contains a discussion on how generating cycles for the homology of Boolean complex enumerate the spheres occurring in the wedge sum representing the homotopy type of its geometric realization. The paper concludes with suggestions for follow-up questions in Section 9.

2. Motivation and definitions

As noted above, the motivation for this work is the study of Coxeter systems and Coxeter graphs, and the importance of their boolean elements. Henceforth, all Coxeter systems are assumed to be finitely generated.

Definition 2.1. Let W be a group defined on generators S. The pair (W, S) is a Coxeter system if the relations in W are of the form s^{2} = e for all s ∈ S, and (st)^{m(s,t)} = e for (s, t) ∈ S^{2} and m(s, t) ∈ ℤ^{+} ∪ {∞}.

Because S consists of involutions, two elements s, t ∈ S commute if and only if m(s, t) = 2. The involution condition also implies that m(s, t) = m(t, s). Since S generates W, any σ ∈ W can be written as a word on letters in S. That is, σ admits an expression σ = s_{1} ⋯ s_{ℓ}, where s_{i} ∈ S. The product s_{1} ⋯ s_{ℓ} is a reduced expression for σ if it is of minimal length ℓ, in which case ℓ is the length of σ.

Definition 2.2. For a Coxeter system (W, S), the (strong) Bruhat order is the partial order on W where σ ≤ τ if and only if σ admits a reduced expression that is a subword of a reduced expression of τ.

Remark 2.3. The Bruhat order makes W a ranked poset, with rank determined by length. Because the minimal element in a simplicial poset corresponds to the empty face in the geometric realization of that poset, we make the the convention that this minimal element has rank −1, thus emphasizing that the face data in the poset is contained in the non-negative ranks.

The structure of the Bruhat order for finite Coxeter groups was studied by the second author in [9]. One aspect of this study was a description of elements with boolean principal order ideals.

Definition 2.4. Let (W, S) be a Coxeter system and regard W as a poset under the Bruhat order. An element σ ∈ W is boolean if its principal order ideal in W is boolean. The boolean ideal 𝔹(W, S) ⊆ W is the subposet of boolean elements.

It is clear from the definition that 𝔹(W, S) is an order ideal in the Bruhat order, thus justifying the terminology. It is also clear, by construction, that 𝔹(W, S) is a simplicial poset.

The results in [9] state that for the finite Coxeter groups of types A, B, and D, boolean elements can be characterized by pattern avoidance. Moreover, the boolean elements of these groups are enumerated by length. For example, the number of boolean elements of length k in the finite Coxeter group A_{n} is

∑_{i=1}^{k} \binom{n + 1 − i}{k + 1 − i}\binom{k − 1}{i − 1}.  (1)

As the unlabeled Coxeter graphs for A_{n} and B_{n} are identical, the boolean elements of length k in B_{n} are also enumerated by (1). For the group D_{n}, the enumeration is more complicated, and a recursive formula is given in [9].

The following lemma is immediate from the description of the Bruhat order above, and gives a useful characterization of boolean elements.

Lemma 2.5. Let (W, S) be a Coxeter system. An element of W is boolean if and only if it has no repeated letters in its reduced decompositions.

It follows from the lemma that every maximal element in 𝔹(W, S) has the same rank, equal to |S| − 1.

Definition 2.6. Let (W, S) be a Coxeter system. The boolean complex of (W, S) is the regular cell complex Δ(W, S) associated to the simplicial poset 𝔹(W, S).

More precisely, Δ(W, S) is the cell complex that has 𝔹(W, S) as its face poset. The minimal element of 𝔹(W, S) represents the empty cell, and an element of rank k ≥ 0 represents a k-dimensional cell (see in Remark 2.3). One can think of the cells in 𝔹(W, S) as simplices, because the minimal subcomplex containing each cell is isomorphic to a simplex of the same dimension. Nevertheless, the boolean complex itself is not a simplicial complex because the cells are not determined by the vertices they contain. One obtains a geometric realization |Δ(W, S)| of the boolean complex in the standard way, by taking one geometric simplex of dimension k for each cell of dimension k, and gluing them together according to the face poset.

The main result of this paper, Theorem 4.4, shows that |Δ(W, S)| has the homotopy type of a wedge of spheres of dimension |S| − 1. Moreover, we give a recursive formula for computing the number of spheres in the wedge. To describe this recursion, we present an alternative construction of the boolean complex, in terms of the unlabeled Coxeter graph of (W, S).

Definition 2.7. The Coxeter graph G(W, S) of a Coxeter system (W, S) has vertex set S and an edge between s and t if and only if m(s, t) > 2. An edge corresponding to m(s, t) > 3 is labeled by m(s, t). The unlabeled Coxeter graph is the underlying simple graph obtained by omitting all edge labels.

A Coxeter system (W, S) can be recovered from its Coxeter graph G. Taking the vertex set of G to be S, one forms the group W generated by S subject to the relations mandated by the edges in G, and the condition that S should consist of involutions. An unlabeled Coxeter graph, however, contains less information, and only allows one to determine when two elements in S commute. Thus, if one is only concerned with commutability of generators, this graph suffices.

Example 2.8. Let W be the group generated by S = {a, b, c, d}, with relations s^{2} = e for all s ∈ S, and m(a, c) = m(a, d) = m(c, d) = 2, m(a, b) = 3, m(b, c) = m(b, d) = 4. The (unlabeled) Coxeter graph G(W, S) is shown below.

d a  b  c

For a finite simple graph G with vertex set S, define the poset 𝔹(G) as follows. First, let 𝕎(S) be the set of words on S with no repeated letters, ordered by the subword order relation. A typical element in 𝕎(S) is thus of the form s_{1}s_{2} ⋯ s_{ℓ}, where s_{1}, s_{2}, …, s_{ℓ} are distinct elements of S. Next, consider the equivalence relation generated by the requirement that

s_{1} ⋯ s_{i−1}s_{i}s_{i+1}s_{i+2} ⋯ s_{ℓ} ∼ s_{1} ⋯ s_{i−1}s_{i+1}s_{i}s_{i+2} ⋯ s_{ℓ}

if {s_{i}, s_{i+1}} is not an edge in G. Let 𝔹(G) be the set of equivalence classes of 𝕎(S) with respect to this equivalence relation. A preimage of an element σ ∈ 𝔹(G) is called a word representative. Note that the set of letters occurring in each word representative of σ is the same. We say that σ contains a letter s if s occurs in the string representatives of σ. A partial ordering is induced on the set 𝔹(G) from the subword order. That is, σ < τ in 𝔹(G) if some word representative of σ is a subword of a word representative of τ.

Definition 2.9. The boolean ideal of a finite simple graph G is the poset 𝔹(G).

The motivation for the construction of 𝔹(G) is of course the following obvious fact, which we record as a lemma.

Lemma 2.10. If G is the unlabeled Coxeter graph of a Coxeter system (W, S), then 𝔹(G) ≅ 𝔹(W, S).

It can be shown directly, or via the relationship between graphs and Coxeter systems, that 𝔹(G) is a simplicial poset for all finite simple graphs G.

Definition 2.11. The boolean complex of a finite simple graph G is the regular cell complex Δ(G) associated to 𝔹(G).

The main result of this paper, as mentioned above, can be equivalently stated as saying that for any finite simple graph G with vertex set S, the geometric realization |Δ(G)| is homotopy equivalent to a wedge of (|S| − 1)-dimensional spheres. It is this version of the result that we shall prove. The promised recursive formula for the number of spheres is given in terms of basic graph operations. These results are stated precisely in Theorem 4.4.

3. Previous related work

Before stating the main results precisely, it is informative to mention similar work which has been done for the independence complex. Ehrenborg and Hetyei [3] and Kozlov [7] prove, each in the context of different results and frameworks, that the complex of sparse sets of [n] is contractible in some cases and homotopy equivalent to a sphere in the remaining cases. In the context of the Bruhat order, the sparse subsets of [n] correspond to the fully commutative elements in the Coxeter group A_{n}. That is, all letters in such a reduced decomposition commute with each other. Thus, these results show that the complex formed from the subposet of 𝔹(A_{n}) consisting of the fully commutable elements is either contractible or homotopy equivalent to a sphere.

Note also that the enumeration from [9] cited in (1) enables the calculation of the Euler characteristic χ of the boolean complex for the Coxeter group A_{n}.

Definition 3.1. The Euler characteristic of a simplicial poset P is the number

χ(P) = ∑_{k≥0}(−1)^{k}|P_{k}|,

where P_{k} ⊆ P is the subset of elements having rank k.

Given Remark 2.3, the Euler characteristic of a simplicial poset equals the Euler characteristic of its associated regular cell complex, which in turn equals the Euler characteristic of the geometric realization.

Corollary 3.2. For all n ≥ 1, χ(Δ(A_{n})) = (−1)^{n−1}f(n − 1) + 1, where {f(n)} are the Fibonacci numbers.

Note the relationship between {χ(Δ(A_{n}))} and sequences A008346 and A119282 in [8]. Also, Corollary 3.2 foreshadows the fact that Δ(A_{n}) is homotopy equivalent to the wedge of f(n − 1) (n − 1)-spheres.

4. Main results

In this section, we state the main result of the article and draw consequences for the classical Coxeter groups. The proof of the main theorem is rather technical, and is postponed until Section 6.

It is convenient to use the notation

m · S^{r} := ⋁_{i=1}^{m} S^{r}

for a wedge sum of m spheres of dimension r. Since the wedge sum is the coproduct in the category of pointed spaces, 0 · S^{r} then denotes a single point.

There will also be graph-theoretic notation used in the statement of the theorem and in its proof.

Definition 4.1. For a finite graph G, let |G| denote the number of vertices in G.

Definition 4.2. Let G be a finite simple graph, and let s, t ∈ G be distinct vertices.

• If {s, t} is not an edge in G, then the graph G + st is obtained from G by adding the edge {s, t}.

• If {s, t} is an edge in G, then the graph G − st is obtained from G by removing the edge {s, t}.

• G/st is the (simple) graph obtained from G by identifying s and t and deleting any resulting redundant edges and loops.

• G \ st is the graph obtained from G by removing the vertices s and t, and all incident edges.

Definition 4.3. For n ≥ 1, let δ_{n} be the graph consisting of n disjoint points.

We can now state the main theorem of this paper.

Theorem 4.4. For every finite simple graph G, there is an integer m(G) so that

Δ(G) ≃ m(G) · S^{|G|−1}.

Moreover, the values m(G) can be computed recursively by the following equations.

m(δ_{n}) = 0
m(G) = m(G − st) + m(G/st) + m(G \ st)  (2)

if {s, t} is an edge in G

We adopt the convention that m(∅) = 1.

As discussed in Section 2, the theorem implies that the geometric realization of the boolean complex of a Coxeter system (W, S) is homotopy equivalent to a wedge of spheres of dimension |S| − 1. The number of spheres occurring in the wedge can be calculated recursively using (2). This process can be greatly expedited by the following proposition.

Proposition 4.5. If G = H_{1} ⊔ H_{2} for graphs H_{1} and H_{2}, then

Δ(G) = Δ(H_{1}) ∗ Δ(H_{2}),

and consequently

|Δ(G)| ≃ m(H_{1})m(H_{2}) · S^{|H_{1}|+|H_{2}|−1}.

In particular, m(G) = m(H_{1})m(H_{2}).

Proof. Since H_{1} and H_{2} are disjoint, every element of 𝔹(H_{1}) commutes with every element of 𝔹(H_{2}). Thus, the complex Δ(G) is formed by taking the simplicial join of the complexes Δ(H_{1}) and Δ(H_{2}), and hence the geometric realization |Δ(G)| is the topological join of |Δ(H_{1})| and |Δ(H_{2})| (see [6]). The last claim now follows from Theorem 4.4. □

The homotopy types of the boolean complexes associated to the finite and affine irreducible Coxeter systems can be calculated as a corollary to Theorem 4.4.

Corollary 4.6. The homotopy types of the boolean complexes for the finite and affine irreducible Coxeter systems are listed below, where f(n) is the sequence of Fibonacci numbers (with f(1) = f(2) = 1) and c(n) is the sequence defined by c(1) = 1 and c(n) = c(n − 1) + f(n) + f(n − 2).

Coxeter Homotopy type
group W of |Δ(W, S)|
A_{n}  f(n − 1) · S^{n−1}
B_{n}  f(n − 1) · S^{n−1}
D_{n}  f(n − 2) · S^{n−1}
E_{6}  4 · S^{5}
E_{7}  6 · S^{6}
E_{8}  10 · S^{7}
F_{4}  2 · S^{3}
G_{2}  S^{1}
H_{3}  S^{2}
H_{4}  2 · S^{3}
I_{2}(m) S^{1}

Coxeter Homotopy type
group W of |Δ(W, S)|
Ã_{n}  c(n) · S^{n}
B̃_{n}  f(n − 2) · S^{n}
C̃_{n}  f(n − 1) · S^{n}
D̃_{n}  f(n − 3) · S^{n}
Ẽ_{6}  7 · S^{6}
Ẽ_{7}  9 · S^{7}
Ẽ_{8}  16 · S^{8}
F̃_{4}  3 · S^{4}
G̃_{2}  S^{2}

The sequence c(n) is entry A014739 in [8]. It can be written in closed form as

c_{n} = (\frac{1 + \sqrt{5}}{2})^{n+1} + (\frac{1 − \sqrt{5}}{2})^{n+1} − 2.

5. Discrete Morse theory

The primary tool in the proof of Theorem 4.4 is discrete Morse theory, which gives an expedient way to analyze the homotopy type of the geometric realization of a regular cell complex through combinatorial properties of its face poset. Discrete Morse theory is a rich subject, and in this section we present only those ideas and results necessary for our argument. The reader is encouraged to read [4, 5] for a detailed background.

Definition 5.1. Let P be a ranked poset. A matching on P is a collection M of pairs (x, y) where x ⋖ y is a covering relation in P, and each element of P occurs in at most one pair in M. If (x, y) ∈ M, then x ⋖ y is a matched edge in M. If x ∈ P occurs in a matched edge in M, then x is matched. Otherwise, x is unmatched.

Definition 5.2. Let P be a poset, and let M be a matching on P. Consider the Hasse diagram of P as a directed graph, with an edge v → u if v ⋗ u. Reverse the direction of each edge in the Hasse diagram which corresponds to a matched edge in M. Let P (M) be the resulting directed graph. The matching M is acyclic if there are no directed cycles in P (M). In the Hasse diagram for P, those edges whose directions have been changed will be said to point up, while unchanged edges point down.

Discrete Morse theory allows one to reduce regular cell complexes without changing the homotopy type of their geometric realizations. Roughly speaking, when X is a regular cell complex with face poset P, and M is an acyclic matching on P, one can collapse cells along matched edges in M without changing the homotopy type of |X|. We will apply this method to regular cell complexes associated to simplicial posets. A small technical issue has to be addressed here, as the minimal element in a simplicial poset is represented by the empty cell in the associated cell complex and thus plays no role in the geometric realization. Therefore we establish the following convention, with the intent of ignoring the minimal element henceforth. This convention is also taken in [4, 5], and it should bring to mind Remark 2.3.

Remark 5.3. In this paper, we require that a matching on a simplicial poset always leaves the minimal element unmatched.

The particular result which we will use to analyze the boolean complex Δ(G) is stated below.

Theorem 5.4 (see [4, 5]). Let P be a simplicial poset, and let M be an acyclic matching on P. For each r ≥ 0, let u_{r} denote the number of elements of rank r that are unmatched. Then the geometric realization of the regular cell complex associated to P is homotopy equivalent to a CW-complex with exactly u_{r} cells of dimension r for each r ≥ 0.

Theorem 4.4 will be proved inductively by constructing an acyclic matching of the simplicial poset 𝔹(G) with all elements of non-negative rank matched except for one element of rank 0 and some number, which we will denote by m(G), of maximal elements. There are two important points to make about such a matching, summarized in the following remark.

Remark 5.5. If M is an acyclic matching on a simplicial poset P, and the only elements on non-negative rank unmatched by M are one element of rank 0 and m elements of rank r, then the geometric realization of the regular cell complex associated to P is homotopy equivalent to m · S^{r}. Also, note that the number m is determined by the homotopy type of the cell complex, and is therefore independent of the matching M. In fact, the number m is determined by the Euler characteristic of P and the formula

χ(P) = χ(m · S^{r}) = 1 + m · (−1)^{r}.

The following lemma is useful for proving the acyclicity of matchings.

Lemma 5.6. Consider a matching M on a ranked poset P. If M has a cycle, then the elements in the cycle lie in two adjacent ranks of P.

Proof. Because M is a matching, there cannot be two incident upward pointing edges in P (M). Thus, after moving upward, one must move downward at least once before moving upward again. So if x is an element in a directed cycle, then no element in the cycle can be more than one rank higher than x in P. □

6. Proof of Theorem 4.4

In this section we prove Theorem 4.4 by constructing, for each nonempty finite simple graph G, an acyclic matching of 𝔹(G) where the only unmatched elements of non-negative rank are one element of rank 0 and some number of maximal elements. As noted in Remark 5.5, this implies that |Δ(G)| is homotopy equivalent to a wedge of spheres of maximal dimension. Furthermore, the number of such spheres, which we shall denote by m(G), is determined by the Euler characteristic of 𝔹(G), prompting the next definition.

Definition 6.1. For a finite simple graph G on n vertices, set

m(G) = (−1)^{n}(χ(P) − 1).

Although this definition gives a way to calculate the value m(G) in Theorem 4.4, computing the Euler characteristic requires knowing a significant amount about the structure of P, as opposed to the recursive formula in equation (2) which requires only basic graph operations. The formula of equation (2) arises from Lemma 6.7.

We construct the matchings by induction on the number of edges in G. The inductive step is somewhat complicated, and we will in fact produce matchings with more specific properties than are actually needed for the desired conclusion. The inductive hypothesis is stated below, after introducing the following notation.

Definition 6.2. For a finite simple graph G and a vertex s in G, let 𝔹(G)_{s} ⊂ 𝔹(G) be the subposet of elements containing the letter s.

The goal of this section is to show inductively that the following statement holds for every integer e ≥ 0.

Inductive Hypothesis (H(e)). For every graph G with at most e edges, and for every vertex s in G, there exists an acyclic matching M on the poset 𝔹(G) with the following properties:

H1 The only unmatched elements in 𝔹(G) of non-negative rank are one element

of rank 0 and m(G) maximal elements; H2 In the restriction of M to the subposet 𝔹(G)_{s}, the only unmatched elements

are m(G) + m(G \ s) maximal elements; and H3 If σ ⋖ τ is a matched edge in M, and τ contains s, then τ and σ can be

written so that one of the following conditions hold s

(a) τ = σs, or

(b) σ is obtained from τ by deleting a letter appearing to the left of s.

We refer to a matching with properties H1 – H3 as an H-matching of 𝔹(G) at s, or just as an H-matching.

For a finite simple graph G, the maximal elements of 𝔹(G) are products of |G| letters. Therefore, if G has an H-matching, then Theorem 5.4 and H1 imply that Δ(G) ≃ m(G) · S^{|G|−1}. Property H2 is needed to preserve H1 for the inductive step, and also to prove the recursive formula in Theorem 4.4. Property H3 is needed purely for the purposes of the induction, specifically, to prove acyclicity of the constructed matching.

The next lemma establishes the base case of the induction.

Lemma 6.3 (Base case). H(0) holds, and m(δ_{n}) = 0 for all n ≥ 1.

Proof. We show that for each vertex s ∈ δ_{n}, there exists an H-matching at s. Let the vertices of δ_{n} be labeled 1, 2, …, n. Without loss of generality, suppose that the vertex s is n. Let M be the matching consisting of all covering relations of the form σ ⋖ 1σ for σ ⊆ {2, …, n}. First notice that the only unmatched element of non-negative rank in 𝔹(δ_{n}) is the vertex 1, so M has property H1, with m(δ_{n}) = 0. Secondly, there are no unmatched elements in 𝔹(δ_{n})_{s}, unless n = 1, proving H2. Property H3 follows from the fact that the Coxeter group with graph δ_{n} is commutative, so the letters in σ and τ can be permuted at will.

It remains to show that M is acyclic. This is straightforward, due to the fact that all the matched edges represent adding or removing the letter 1 from an element in the poset. Recall from Lemma 5.6 that a cycle is contained in two adjacent ranks of 𝔹(δ_{n}), so an “up” edge σ ⋖ 1σ would have to be followed by a “down” edge 1σ ⋗ τ. The next step must be an up edge τ ⋖ 1τ, so τ cannot contain 1. However, this implies that σ = τ, contradicting the directions of the edges. Therefore M is acyclic. □

The remainder of the section is devoted to proving the inductive step. Henceforth we assume that H(e) holds for some e ≥ 0 and consider a graph G with e+1 edges. We show that for an arbitrary vertex s ∈ G, there exists an H-matching of 𝔹(G) at s. If s is the endpoint of an edge {s, t}, then we construct in Lemma 6.7 the H-matching of 𝔹(G) from H-matchings of 𝔹(G − st) and 𝔹(G/st), which exist by the induction hypothesis. The case when s is an isolated vertex is treated in Lemma 6.8 by constructing the required matching from an H-matching of 𝔹(G \ s).

6.1. Considering a non-isolated vertex.

Suppose that s is the endpoint of an edge {s, t}, and set H := G − st. By the induction hypothesis, there exists an H-matching M_{H} of 𝔹(H) at s. We want to use this matching to produce an H-matching of 𝔹(G) at s. To this end, we first compare the complexes 𝔹(G) and 𝔹(H). The complex 𝔹(H) is obtained from 𝔹(G) by identifying an element that can be written as αstβ with the element represented by αtsβ. Consequently, there is a canonical projection of posets

π: 𝔹(G) ↠ 𝔹(H).

Now, let 𝔹(G)_{st} ⊂ 𝔹(G) be the subset of elements that can be written in the form αstβ. Let 𝔹(G)s̃t be the set complement of 𝔹(G)_{st} in 𝔹(G). This gives a decomposition of sets

𝔹(G) = 𝔹(G)s̃t ⊔ 𝔹(G)_{st},  (3)

where ⊔ denotes the disjoint union. However, this is not a decomposition of posets, as there are covering relations between 𝔹(G)s̃t and 𝔹(G)_{st}, as recorded in the following lemma. The proof of the lemma is not difficult, and is left to the reader.

Lemma 6.4.

(1) If σ⋖τ is a covering relation in 𝔹(G) such that τ ∈ 𝔹(G)_{st} and σ ∈ 𝔹(G)s̃t, then σ is obtained from τ by deleting either s or t.

(2) If σ⋖τ is a covering relation in 𝔹(G) such that τ ∈ 𝔹(G)s̃t and σ ∈ 𝔹(G)_{st}, then τ can be written as αsw_{1}w_{2} ⋯ w_{r}tβ, where σ is obtained from τ by removing a letter w_{i} between s and t, and the vertices s, w_{1}, w_{2}, …, w_{r}, t form a path in the graph H.

It is easy to see that π restricts to a bijective order-preserving map

πs̃t: 𝔹(G)s̃t ⟶ 𝔹(H).

However this is not a bijection of posets, as 𝔹(H) can have more covering relations than 𝔹(G)s̃t, corresponding to elements of 𝔹(G)s̃t covering elements of 𝔹(G)_{st}. The following lemma nevertheless allows us to pull back the H-matching M_{H} of 𝔹(H) at s to a matching on 𝔹(G)s̃t along the restriction πs̃t.

Lemma 6.5. If σ and τ are elements in 𝔹(G)s̃t such that π(σ)⋖π(τ) is a matched edge in M_{H}, then σ ⋖ τ is a covering relation in 𝔹(G)s̃t.

Proof. By Lemma 6.4, if π(σ) ⋖ π(τ) is a covering relation in 𝔹(H) but σ ⋖ τ is not a covering relation in 𝔹(G)s̃t, then τ can be written in the form αsw_{1}w_{2} ⋯ w_{r}tβ, where the vertices s, w_{1}, w_{2}, …, w_{r}, t form a path in the graph H, and σ is obtained by deleting a letter w_{i} between s and t. Property H3 prohibits the covering relation π(σ) ⋖ π(τ) from being a matched edge in this case. □

Lemma 6.5 allows us to define a matching Ms̃t on 𝔹(G)s̃t by declaring σ ⋖ τ to be a matched edge in Ms̃t if and only if π(σ) ⋖ π(τ) is a matched edge in M_{H}. Property H1 for M_{H} implies that the elements of non-negative rank in 𝔹(G)s̃t that are unmatched in Ms̃t are exactly one element of rank 0 and m(H) maximal elements.

This matching Ms̃t constitutes a part of our H-matching of 𝔹(G) at s, and what remains is to produce matched edges among the elements in 𝔹(G)_{st}.

Let F denote the graph G/st with x ∈ F denoting the new vertex obtained by identifying s and t. Then F has at most e edges, so there is an H-matching M_{F} of 𝔹(F) at x by the induction hypothesis. The following lemma allows us to pull the restriction of M_{F} to 𝔹(F)_{x} back to a matching on 𝔹(G)_{st}.

Lemma 6.6. There is an isomorphism of posets

ϕ: 𝔹(G)_{st} → 𝔹(F)_{x}

defined by

ϕ(αstβ) = αxβ.

The proof mainly consists of checking that ϕ is a well-defined, order-preserving map. The same reasoning then gives an inverse to ϕ. This is left to the reader.

We now define a matching M_{st} on 𝔹(G)_{st} by declaring σ⋖τ to be a matched edge in M_{st} if and only if π(σ) ⋖ π(τ) is a matched edge in M_{F}. Property H2 implies that the elements in 𝔹(G)_{st} that are unmatched in M_{st} are exactly m(F)+m(F \x) maximal elements.

Lemma 6.7. The matching M on 𝔹(G) obtained by combining the matching Ms̃t on 𝔹(G)s̃t and the matching M_{st} on 𝔹(G)_{st} is an H-matching of 𝔹(G) at s. Furthermore,

m(G) = m(G − st) + m(G/st) + m(G \ st).

Proof. It is clear that M is a matching on 𝔹(G). The unmatched elements of non-negative rank in 𝔹(G) are exactly one element of rank 0 and m(G) maximal elements, where

m(G) = m(H) + m(F) + m(F \ x)
= m(G − st) + m(G/st) + m(G \ st).

This proves H1 for M, and, indeed, the recursive formula for the function m.

Now consider restricting the matching M to elements of 𝔹(G) containing the letter s. The set of such elements in 𝔹(G)s̃t which are unmatched correspond to the unmatched elements in 𝔹(H)_{s}. By Property H2 of the matching M_{H}, these are m(H) + m(H \ s) maximal elements. Every element 𝔹(G)_{st} contains s, so this set of elements still gives exactly m(F) + m(F \ x) unmatched maximal elements. Since H \ s = G \ s, there are exactly m(G) + m(G \ s) unmatched elements in 𝔹(G)_{s}, proving H2 for M.

To prove H3 for M, recall that every matched edge in M lies in either Ms̃t or M_{st}. A matched edge in Ms̃t certainly has the required form, since it comes from a matched edge in M_{H}, which is an H-matching at s. A matched edge σ ⋖ τ in M_{st} corresponds to a matched edge ϕ(σ)⋖ϕ(τ) in M_{F} between two elements containing x. But M_{F} is an H-matching at x, and Property H3 for M_{F} implies that ϕ(σ) and ϕ(τ) can be written so that ϕ(σ) is obtained from ϕ(τ) by deleting a letter to the left of x. It follows that τ and σ can be written so that σ is obtained from τ by deleting a letter to the left of s.

It remains to show that M is acyclic. Recall the set decomposition of 𝔹(G) in equation (3), and the covering relations between 𝔹(G)_{st} and 𝔹(G)s̃t described in Lemma 6.4. Additionally, note that in the matching M, there are no matched edges between these two sets.

A cycle in M lying entirely in 𝔹(G)s̃t would induce a cycle in 𝔹(H), contradicting the acyclicity of M_{H}. Similarly, the acyclicity of M_{F} implies that no cycle lies entirely in 𝔹(G)_{st}. It remains only to show that no cycle involves both of these sets. If there is such a cycle C, then the covering relations in C going between the disjoint sets must be “down” edges. To move from 𝔹(G)_{st} to 𝔹(G)s̃t, we must delete either s or t from an element of the form αstβ. Traversing along C, we alternately move up along a matched edge in M by adding an element, and down along an unmatched edge by deleting an element. Property H3 guarantees that at no step in this process does the letter s appear to the left of the letter t. Therefore it is impossible to get back to 𝔹(G)_{st} by traversing along C, contradicting the assumption that C is a cycle. We deduce that M is acyclic. □

6.2. Considering an isolated vertex.

We now turn our attention to the case where s is an isolated vertex in G. That is, s has no incident edges in G.

Lemma 6.8. If s ∈ G is an isolated vertex, and 𝔹(G \ s) has an H-matching at x for some x ∈ (G \ s), then 𝔹(G) has an H-matching at s.

Proof. Set H := G \ s. Since s is an isolated vertex in G, the letter s commutes with every element in 𝔹(H). Hence we have a decomposition of sets

𝔹(G) = 𝔹(H) ⊔ (𝔹(H))s ⊔ {s}.  (4)

This is not a decomposition of posets as every element σ ∈ 𝔹(H) is covered by σs ∈ (𝔹(H))s, and s is covered by ts ∈ (𝔹(H))s for every vertex t ∈ H. However these are the only covering relations between distinct parts in the decomposition of equation (4).

Now suppose that M_{H} is an H-matching of 𝔹(G \ s) at some vertex x. Let σ_{1}, …, σ_{m(H)} be the maximal elements in 𝔹(H) which are unmatched by M_{H}, and denote the unmatched rank 0 element by 1. We construct a matching M of 𝔹(G) from M_{H}, by including matched edges as follows.

• If σ ⋖ τ is a matched edge in M_{H}, then σ ⋖ τ and σs ⋖ τs are matched edges in M

• s ⋖ 1s is a matched edge in M

• σ_{i} ⋖ σ_{i}s is a matched edge in M for each i ∈ {1, …, m(H)} To see that M is acyclic, first note that no cycle can be contained entirely in

𝔹(H) or (𝔹(H))s since M_{H} is acyclic. Next note that no cycle can include the element s ∈ 𝔹(G), since from s one can only move up to 1s, from which one can only move to 1, whence one cannot escape. Therefore any cycle would have to be contained in the blocks 𝔹(H) and (𝔹(H))s, intersecting both. In particular, at some point, the cycle moves from 𝔹(H) to (𝔹(H))s. The only way to do this is by moving along one of the matched edges σ_{i} ⋖ σ_{i}s, so a cycle has to pass through some σ_{i}. However, there is no way to move down to σ_{i}, so it cannot be part of a cycle. We conclude that M is acyclic.

We now show that M satisfies H1 – H3. Property H1 is immediate, since the only unmatched element in M of non-negative rank is the rank 0 element 1. The unmatched elements in 𝔹(G)_{s} are the maximal elements σ_{1}s, …, σ_{m(H)}s, proving Property H2. Property H3 follows from the fact that, as s is an isolated point in G, any element in 𝔹(G) containing s can be written so that s appears on the far right. □

Remark 6.9. It is interesting to note a fact that arises in the preceding proof: if the graph G has an isolated vertex, then m(G) = 0. In particular, this implies that Δ(G) is contractible. This fact will be discussed further in Section 7.

It is now straightforward to complete the proof of Theorem 4.4.

Proof of Theorem 4.4. By Theorem 5.4, the first claim follows if we can show that H(e) holds for all e ≥ 0. We prove this by induction on e. The base case, where e = 0 is Lemma 6.3. For the inductive step, assume that H(e) holds for some e ≥ 0 and consider a graph G with e+1 edges. Let s be a vertex in G. If s is the endpoint of an edge {s, t} in G, then 𝔹(G) has an H-matching at s by Lemma 6.7. If s is isolated, then, since e + 1 ≥ 1, there is some vertex s′ ∈ G that is the endpoint of an edge {s′, t}. Since the graph G \ s also has e + 1 edges, Lemma 6.7 implies that 𝔹(G \ s) has an H-matching at s′. Lemma 6.8 then implies that 𝔹(G) has an H-matching at s.

The inductive formula for m(G) follows from Lemma 6.7, and the base case, that m(δ_{n}) = 0, is included in Lemma 6.3. □

7. Corollaries to Theorem 4.4

Theorem 4.4 gives the homotopy type of the boolean complex for any finite simple graph G, specifically that it is the wedge of m(G) spheres S^{|G|−1}. For some classes of graphs, we can obtain more specific data regarding the function m. The most interesting of these results are listed below, with some proofs left to the reader.

In the case where the graph G is actually a tree, the recursion of equation (2) can be simplified by Proposition 4.5.

Corollary 7.1. If T is a tree, then the function m, where Δ(T) ≃ m(T) · S^{|T |−1}, is computed recursively as depicted in Figure 2.

The corollary shows in particular that if T is a tree with more than one vertex, then m(T) > 0. From this and Theorem 4.4, we draw the following conclusion.

m ( ) = 0
m (  ) = 1

m^{(  )} = m^{(  )} + m^{(  )}

m^{(  )} = m^{(  )}

Figure 2. Method for recursively calculating m(T) for a tree T. The region without detail is a subtree of T.

Corollary 7.2. A graph G has an isolated vertex if and only if m(G) = 0. That is, the center of a Coxeter group contains a generator of the group if and only if the group’s boolean complex is contractible.

We now determine the homotopy types of the boolean complexes of some specific families of graphs.

Definition 7.3. For n ≥ 1, let S_{n} be the tree on n vertices with a single vertex of degree n − 1.

Corollary 7.4. For all n ≥ 1, m(S_{n}) = 1. That is, the boolean complex Δ(S_{n}) is homotopy equivalent to S^{n−1}.

Definition 7.5. For n ≥ 1, let K_{n} be the complete graph on n vertices.

Corollary 7.6. For all n ≥ 1, the function m(K_{n}) satisfies the recurrence

m(K_{n}) = (n − 1)(m(K_{n−1}) + m(K_{n−2})),

with initial values m(K_{1}) = 0 and m(K_{2}) = 1.

Observe that the sequence {m(K_{n})} is sequence A000166 of [8], which is the number of derangements of [n].

From equation (2), we see that the function m is monotonically increasing with respect to edge addition. More precisely, if H ⊆ G is obtained by deleting some edges from the graph G, then m(H) ≤ m(G). One could ask when this inequality is strict, and when there is equality.

Corollary 7.7. Fix a graph G. Obtain H ⊆ G by removing an edge of G. Then m(H) = m(G) if and only if G has an isolated vertex, in which case m(G) = m(H) = 0.

Proof. Let H = G − st for some edge {s, t} in G. If G has an isolated vertex, then m(G) = 0, and so m(H) must also be 0 because m(H) ≤ m(G).

Suppose now that m(G) = m(H). Then by Theorem 4.4, it must be that m(G/st) and m(G \ st) are both 0. Therefore, each of these graphs contains an isolated vertex. If G/st contains an isolated vertex, then either G has an isolated vertex, in which case we are done, or the vertices s and t are adjacent, and comprise their own connected component in G. In the latter case, then, requiring that G \ st have an isolated vertex forces G to have an isolated vertex as well. □

8. Homology of the boolean complex

At this point we know that the boolean complex of a Coxeter system has the homotopy type of a wedge of spheres of maximal dimension. We also have an expedient way of calculating the number of spheres recursively from the Coxeter graph G. However we have little knowledge of the geometric or combinatorial relevance of the spheres in the wedge sum. Our proof of Theorem 4.4 used discrete Morse theory to determine the homotopy type of the boolean complex by producing an acyclic matching on its face poset, the boolean ideal. This matching leaves one element of rank 0 and m(G) maximal elements unmatched. The unmatched element of rank 0 represents a point x_{0} ∈ |Δ(G)|, and discrete Morse theory allows us to collapse all cells corresponding to matched cells down to this point without changing the homotopy type of |Δ(G)|, thus obtaining the homotopy equivalence |Δ(G)| ≃ m(G) · S^{|G|−1}, where each unmatched maximal element corresponds to a sphere summand. However, this process involves several choices, and the unmatched cells are not at all canonical representatives for the spheres. Furthermore, the cell corresponding to an unmatched element is generally not the boundary of a sphere in |Δ(G)|, and so does not represent the sphere in any geometric sense.

This discrepancy can by rectified by considering the homology of the boolean complex and we shall do so in this section. To avoid issues of orientation, we take coefficients in ℤ/2. Determining the homology groups is a simple matter, since the homology of Δ(G) is the reduced homology of |Δ(G)| (reduced because of the rank −1 element of Δ(G)). Thus, by Theorem 4.4,

H_{∗}(Δ(G); ℤ/2) ≅ \begin{cases}(ℤ/2)^{m(G)}, & if ∗ = |G| − 1; \\ 0, & if ∗ ≠ |G| − 1. \end{cases}

The important thing is therefore not calculating the homology, but finding the generating cycles, as a cycle representing a generator of H_{|G|−1}(Δ(G); ℤ/2) is a canonical representative for the corresponding sphere summand. Indeed, such a cycle consists of a sum of cells, which (together with their boundaries) form a sphere in the geometric realization.

The authors have calculated explicit generating cycles for boolean complexes of Coxeter systems of type A_{n}, for 1 ≤ n ≤ 6 and the results are presented below. The results also apply to Coxeter systems of type B_{n} as they have the same unlabeled Coxeter graphs. We omit the calculations and only present the results.

To establish notation, we consider the Coxeter graph of A_{n} to be a graph with vertices labeled 1 through n and an edge going from k to k + 1 for 1 ≤ k < n. The cycles generating the homology of Δ(A_{n}) are each a sum of cells of maximum dimension. We shall denote each cell by a string representing the corresponding maximal element in 𝔹(A_{n}), enclosed in square brackets.

Example 8.1. The cycles generating H_{∗}(Δ(A_{n}); ℤ/2) for 1 ≤ n ≤ 6 are as follows. A_{1} : H_{∗}(A_{1}; ℤ_{2}) = 0. A_{2} : H_{1}(A_{2}; ℤ_{2}) ≅ ℤ/2 with generator [12] + [21]. A_{3} : H_{2}(A_{3}; ℤ_{2}) ≅ ℤ/2 with generator

y := [123] + [213] + [312] + [321].

A_{4} : H_{3}(A_{4}; ℤ_{2}) ≅ (ℤ/2)^{2} with generators

y_{0} := [1234] + [2134] + [4123] + [4213],
y_{1} := [3124] + [3214] + [4312] + [4321].

A_{5} : H_{4}(A_{5}; ℤ_{2}) ≅ (ℤ/2)^{3} with generators y_{00} + y_{10}, y_{01} + y_{11}, and y_{00} + y_{01}, where

y_{00} := [12345] + [21345] + [51234] + [52134],
y_{01} := [41235] + [42135] + [54123] + [54213],
y_{10} := [31245] + [32145] + [53124] + [53214],
y_{11} := [43125] + [43215] + [54312] + [54321].

A_{6} : H_{5}(A_{6}; ℤ_{2}) ≅ (ℤ/2)^{5} with generators y_{000} + y_{010}, y_{001} + y_{011}, y_{100} + y_{110}, y_{101} + y_{111}, and y_{000} + y_{001} + y_{100} + y_{101}, where

y_{000} := [123456] + [213456] + [612345] + [621345],
y_{001} := [512346] + [521346] + [651234] + [652134],
y_{010} := [412356] + [421356] + [641235] + [642135],
y_{011} := [541236] + [542136] + [654123] + [654213],
y_{100} := [312456] + [321456] + [631245] + [632145],
y_{101} := [531246] + [532146] + [653124] + [653214],
y_{110} := [431256] + [432156] + [643125] + [643215],
y_{111} := [543126] + [543216] + [654312] + [654321].

There are clear patterns in these results, and we have tried to suggest this by the notation. The element y_{0} ∈ 𝔹(A_{4}) is formed by taking the first two terms of the element y ∈ 𝔹(A_{3}) and adding the letter 4 on either side, while y_{1} is formed similarly from the last two terms of y. This rule continues, so for example y_{101} is obtained by adding the letter 6 on either side of the last two terms of y_{10}. From these calculations, it seems that the elements formed in this way play a key role in enumerating the homology classes of the boolean complexes. It would be very interesting to determine the exact rules dictating how cells group together to form homology classes, for type A_{n} as well as other graphs.

It is also interesting to note that every cell of maximal dimension occurs in some homology class.

9. Further questions

Several questions about boolean complexes are suggested by this work and remain unanswered. These range from topological questions to more combinatorial ones. We highlight a selection of these problems here.

Question 1. What are the cycles representing the homology of the boolean complex of a graph? Even in the relatively simple case of type A_{n}, where one can enumerate the maximal cells explicitly, there is a rich combinatorial structure waiting to be uncovered.

Question 2. Is there a relationship between the boolean complex of a Coxeter system and its Coxeter complex and/or Tits building? The boolean complex is clearly a “coarser” construction, as it depends only on the unlabeled Coxeter graph, while knowing the Coxeter complex or a Tits building is equivalent to knowing the labeled Coxeter graph, yet there are many similarities. For instance, the Coxeter complex of a finite reflection group has the homotopy type of a wedge of spheres.

The value m(G), for a graph G, is clearly a graph invariant. Letting G_{n} be the class of graphs with n vertices, we have a function m_{n}: G_{n} → ℤ, G ↦ m(G). This prompts the next two questions.

Question 3. What can be said of the image of m_{n}? For example, the corollaries in the previous section show that 1 is in the image, and that the largest value is m(K_{n}). However, an easy example shows that the image is not equal to the interval [1, m(K_{n})]: there is no graph G on 4 vertices with m(G) equal to 4. Is there a way to decide which values are in the image, besides examining all graphs on n vertices? That is, is there another way to characterize the image of m_{n}?

Question 4. For graphs G and H on n vertices, can anything special be said if m(G) = m(H)? Note that there are non-isomorphic graphs with this property: let G be a path of 5 vertices, and let H be a triangle with two extra vertices adjacent to one corner. Then m(G) = m(H) = 3.

Question 5. By Corollary 7.6 and the subsequent comment, m(K_{n}) is equal to the number of derangements of [n]. Can this be proved directly by constructing a bijection between derangements of [n] and a set of generators for the homology of Δ(K_{n})?

Question 6. Are there other families of graphs (besides the complete graphs) that give rise to an interesting sequence? If so, is there a bijection between the homology generators for the boolean complexes of such a family and other interesting objects?

10. Acknowledgments

The authors are grateful to Patricia Hersh and Richard Ehrenborg for helpful discussions at the onset of this work. We also thank Raleigh’s in Berkeley, and Stephanie in particular, for providing the perfect setting for working on this project.

References

[1] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer, New York, 2005.

[2] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math. 118 (1994), 371–394.

[3] R. Ehrenborg and G. Hetyei, The topology of the independence complex, Europ. J. Combin. 27 (2006), 906–923.

[4] R. Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), 90–145.

[5] R. Forman, A user’s guide to discrete Morse theory, Séminaire Lotharingien de Combinatoire 48 (2002), B48c.

[6] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002.

[7] D. N. Kozlov, Complexes of directed trees, J. Combin. Theory, Ser. A 88 (1999), 112–122.

[8] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at

    http://www.research.att.com/~njas/sequences/.

[9] B. E. Tenner, Pattern avoidance and the Bruhat order, J. Combin. Theory, Ser. A 114 (2007), 888–905.

The Mathematical Sciences Research Institute, Berkeley, California

   E-mail address: karirag@msri.org

Department of Mathematical Sciences, DePaul University, Chicago, Illinois

   E-mail address: bridget@math.depaul.edu