# EL-Shellability of Generalized Noncrossing Partitions Associated to Well-Generated Complex Reflection Groups
(Extended Abstract)

## Henri Mühle

Fakultät für Mathematik, Universität Wien, Wien, Austria

**Abstract.** In this article we prove that the poset of *m*-divisible noncrossing partitions is EL-shellable for every well-generated complex reflection group. This was an open problem for type *G*(d, d, n) and for the exceptional types, for which a proof is given case-by-case.

**Résumé.** Dans cet article nous prouvons que l'ensemble ordonné des partitions non-croisées *m*-divisibles est EL-épluchable ("EL-shellable") pour tout groupe de réflexions complexe bien engendré. Il s'agissait d'un problème ouvert pour le type *G*(d, d, n) et pour les types exceptionnels, pour lesquels nous donnons une preuve au cas par cas.

**Keywords:** *m*-divisible Noncrossing Partitions, Generalized Noncrossing Partitions, Well-Generated Complex Reflection Groups, EL-Shellability

## 1 Introduction

In a seminal paper [17], Germain Kreweras investigated noncrossing set partitions under refinement order. They quickly developed into a popular research topic and many interesting connections to other mathematical branches, such as algebraic combinatorics, group theory and topology, have been found. For an overview of the relation of noncrossing partitions to other branches of mathematics, see for instance [20, 26]. Many of these connections were made possible by regarding noncrossing set partitions as elements of the intersection poset of the braid arrangement. This observation eventually allowed for associating similar structures, denoted by $NC_W$, to every well-generated complex reflection group $W$. Meanwhile, these structures have been generalized even further to *m*-divisible noncrossing partitions, denoted by $NC_W^{(m)}$ [1, 8]. Kreweras' initial objects are obtained as the special case where $W$ is the symmetric group and $m = 1$.

The main purpose of this paper is to prove that the poset of *m*-divisible noncrossing partitions possesses a certain order-theoretic property, namely EL-shellability (see Section 2.4). This is the statement of our main theorem.
**Theorem 1.1** Let $m \in \mathbb{N}$ and denote by $NC_W^{(m)}$ the poset of $m$-divisible noncrossing partitions associated to a well-generated complex reflection group $W$. Let $NC_W^{(m)} \cup \{\hat{0}\}$ be the lattice that arises from $NC_W^{(m)}$ by adding a unique smallest element $\hat{0}$. Then, $NC_W^{(m)} \cup \{\hat{0}\}$ is EL-shellable.

The fact that a poset is EL-shellable implies a number of algebraic, topological and combinatorial properties. For instance, the Stanley-Reisner ring associated to an EL-shellable poset is Cohen-Macaulay. For further implications of EL-shellability we refer to [9, 10].

In the case of real reflection groups, Theorem 1.1 was already proved in [3] for $m = 1$ and in [1] for general $m$, but it has never been generalized to well-generated complex reflection groups. We recall in Section 2.1 that there are two infinite families of well-generated complex reflection groups, namely $G(d, 1, n)$ and $G(d, d, n)$, $d \ge 1$, as well as 26 exceptional groups. It follows from an observation of Bessis and Corran [7, p. 42] that $NC_{G(d,1,n)} \cong NC_{G(2,1,n)}$ for $d \ge 2$, and since $G(2, 1, n)$ is known to be a real reflection group (namely the hyperoctahedral group of rank $n$), Theorem 1.1 follows in this case from [1, Theorem 3.7.2]. Since $G(2, 2, n)$ is a real reflection group as well (an index 2 subgroup of $G(2, 1, n)$), we only need to show Theorem 1.1 for the groups $G(d, d, n)$, $d \ge 3$, as well as for the 20 exceptional well-generated complex reflection groups that are no real reflection groups. In order to accomplish this, we first give an EL-labeling for $NC_W$ where $W$ is one of the aforementioned groups, and subsequently construct an EL-labeling for $NC_W^{(m)}$ out of it. Most of the proofs in the remainder of this article are omitted, but can be found in [21] along with more details and examples.

In Section 2 we give background information on complex reflection groups, noncrossing partitions and EL-shellability. In Section 3 we generalize the concept of reflection orderings compatible with a Coxeter element as introduced in [3] to the well-generated complex reflection groups $G(d, d, n)$, $d \ge 2$. We elaborate properties of shortest factorizations of a Coxeter element in Section 4, and use these properties for the proof of the EL-shellability for the case $G(d, d, n)$ (see Section 5). For the exceptional well-generated complex reflection groups we have explicitly constructed an EL-labeling with the help of a computer program in [21, Section 7]. We state this fact in Section 6. We conclude the proof of Theorem 1.1 in Section 7, and give some applications of our main result in Section 8.

# 2 Preliminaries

In this section we provide definitions and background for the concepts treated in this article. For a more detailed introduction to complex reflection groups, we refer to [19]. EL-shellability of partially ordered sets was introduced in [9]. More details and examples can be found there.

## 2.1 Complex Reflection Groups

Let $V$ be an $n$-dimensional complex vector space and $w \in U(V)$ a unitary transformation on $V$. Define the fixed space $\text{Fix}(w)$ of $w$ as the set of all vectors in $V$ that remain invariant under the action of $w$. A unitary transformation is called reflection if it has finite order and the corresponding fixed space has codimension 1. Hence, $\text{Fix}(w)$ is a hyperplane in $V$, the so-called reflecting hyperplane of $w$. A finite subgroup $W \le U(V)$ that is generated by reflections is called unitary reflection group or – as we say throughout the rest of the article – complex reflection group. A complex reflection group is called irreducible if it cannot be written as a direct product of two complex reflection groups of smaller dimensions.

According to Shephard and Todd's classification [25] of finite irreducible complex reflection groups there is one infinite family of such reflection groups, denoted by $G(d, e, n)$, with $d, e, n$ being positive
integers with $e | d$, as well as 34 exceptional groups, denoted by $G_4, G_5, \dots, G_{37}$. In case of $G(d, e, n)$,
the parameter $n$ corresponds to the dimension of the vector space $V$ on which the group acts. We call
an $(n \times n)$-matrix that has exactly one non-zero entry in each row and each column a *monomial matrix*.
The group $G(d, e, n)$ can be defined as the group of monomial matrices, in which each non-zero entry is
a primitive $d$-th root of unity and the product of all non-zero entries is a primitive $\frac{d}{e}$-th root of unity.

For every complex reflection group $W$ of rank $n$ there is a set of algebraically independent polynomials
$\sigma_1, \sigma_2, \dots, \sigma_n \in \mathbb{C}[X_1, X_2, \dots, X_n]$ that remain invariant under the group action. The degrees of these
polynomials are called *degrees of W*. They have a close connection to the structure of $W$. Namely,
the product of the degrees equals the group order and their sum equals the number of reflections of $W$
plus $n$. We can similarly define another set of invariants, the *codegrees of W*, on the dual space $V^*$ of
linear functionals on $V$ (see [19, Definition 10.27]). If $d_1 \le d_2 \le \dots \le d_n$ denote the degrees and
$d_1^* \ge d_2^* \ge \dots \ge d_n^*$ the codegrees, it follows from [22, Theorem 5.5] that a complex reflection group is
*well-generated* if it satisfies $d_i + d_i^* = d_n$ for all $1 \le i \le n$. We can conclude from Tables 1–4 in [14] that
there are two infinite families of irreducible well-generated complex reflection groups, namely $G(d, 1, n)$
and $G(d, d, n)$, $d \ge 1$. Among the 34 exceptional complex reflection groups, 26 are well-generated.

## 2.2 Regular Elements and Noncrossing Partitions

As already announced in the introduction, the objects of our concern are so-called noncrossing partitions.
This section is dedicated to the definition of these objects. Let $T = \{t_1, t_2, \dots, t_N\}$ be the set of all
reflections of $W$. Since $W$ is generated by $T$, we can write every element $w \in W$ as a product of
reflections. This gives rise to a length function $\ell_T$ that assigns to every $w \in W$ the least number of
reflections that are needed to form $w$. With the help of this length function, we can attach a poset structure
to $W$, by defining $u \le_T v$ if and only if $\ell_T(v) = \ell_T(u) + \ell_T(u^{-1}v)$.

Denote by $V$ the complex vector space on which $W$ acts. A vector $v \in V$ is called *regular* if it does not
lie in one of the reflecting hyperplanes of $W$. If the eigenspace to an eigenvalue $\zeta$ of $w \in W$ contains a
regular vector, $w$ is called *$\zeta$-regular*. It follows from [27, Theorem 4.2] that $\zeta$-regular elements that have
the same order are conjugate to each other. Let $d_n$ be the largest degree of $W$ and let $\zeta$ be a primitive
$d_n$-th root of unity. In this case, a $\zeta$-regular element $\gamma_\zeta \in W$ is called *Coxeter element* and by [27,
Theorem 4.2(i)] has order $d_n$. Consider some other primitive $d_n$-th root of unity $\xi$, and some Coxeter
element $\gamma_\xi \in W$ that is $\xi$-regular. Using a field isomorphism from $\mathbb{Q}[\zeta]$ to $\mathbb{Q}[\xi]$, we can establish a
bijection between the conjugacy class of $\gamma_\zeta$ and the conjugacy class of $\gamma_\xi$. Hence, the Coxeter elements
of a well-generated complex reflection group are conjugate up to isomorphism.

It is shown in [18] that Coxeter elements exist only in well-generated complex reflection groups. If $\varepsilon$
denotes the identity of $W$ and $\gamma$ is a Coxeter element of $W$, the interval $[\varepsilon, \gamma]$ of $(W, \le_T)$ is called *lattice of noncrossing partitions of W*, and we denote it by $NC_W$. Since Coxeter elements are conjugate up to isomorphism and the length function $\ell_T$ is invariant under conjugation, the lattice structure of $NC_W$ does not depend on a specific choice of a Coxeter element. The fact that $NC_W$ indeed is a lattice for every well-generated complex reflection group was shown in a series of papers [5, 6, 7, 11, 12, 13]. It was also shown that this lattice has a number of beautiful properties: it is for instance atomic, graded, self-dual and complemented. The lattice property of $NC_W$ also plays an important role in Bessis’ proof (see [6]) that the complement of the hyperplane arrangement induced by the reflecting hyperplanes in $W$ is $K(\pi, 1)$.

In [1], Drew Armstrong introduced a more general poset structure that he called *poset of m-divisible*
noncrossing partitions, where $m$ is some positive integer. For a Coxeter element $\gamma \in W$, this poset is

$$NC_{W}^{(m)} = \left\{ (w_0; w_1, \dots, w_m) \in NC_{W^{m+1}} \mid \gamma = w_0 w_1 \cdots w_m \text{ and } \sum_{i=0}^{m} \ell_{T}(w_i) = \ell_{T}(\gamma) \right\},$$

where the corresponding order relation is defined as

$$(u_0; u_1, \dots, u_m) \le (v_0; v_1, \dots, v_m) \quad \text{if and only if} \quad u_i \ge v_i \text{ for all } 1 \le i \le m.$$

It turns out that $(NC_W^{(m)}, \le)$ is graded with rank function rk$(w_0; w_1, \dots, w_m) = \ell_T(w_0)$ and has a unique maximal element $(\gamma; \varepsilon, \dots, \varepsilon)$. In general, however, this poset has no unique minimal element. Although Armstrong considered only real reflection groups$^{(i)}$, the same construction can be carried out in the general setting of well-generated complex reflection groups (see [8]). Not surprisingly, the case $m=1$ yields the lattice of noncrossing partitions as defined in the previous paragraph. By theorems of several authors [4, 6, 7, 15, 16, 23], it follows that for any irreducible well-generated complex reflection group $W$ and $m \in \mathbb{N}$ we have

$$|NC_{W}^{(m)}| = \prod_{i=1}^{n} \frac{md_{n} + d_{i}}{d_{i}}, \qquad (1)$$

where the $d_i$'s again denote the degrees of $W$ in increasing order. These quantities are called *Fuss-Catalan numbers*, which we denote by $\mathrm{Cat}^{(m)}(W)$.

## 2.3 Reduced Expressions and Inversions

Let $\hat{T} \subseteq T$ be a subset of the set of all reflections of $W$, and let $w \in W$. We write $\ell_{\hat{T}}$ for the length function that is defined on the subgroup of $W$ generated by $\hat{T}$. The sequence $(t_1, t_2, \dots, t_k) \in \hat{T}^k$ is called shortest factorization of $w$ or reduced $\hat{T}$-word for $w$ if $w = t_1 t_2 \cdots t_k$ and $\ell_{\hat{T}}(w) = k$. Moreover, if we have a partial order $\le$ on $\hat{T}$, we say that $(t_1, t_2, \dots, t_k)$ has a descent at $i$ if $t_i > t_{i+1}$, for some $1 \le i < k$. The set of all descents of $(t_1, t_2, \dots, t_k)$ is called the descent set of $(t_1, t_2, \dots, t_k)$. More generally, we say that $(t_1, t_2, \dots, t_k)$ has an inversion at $i$ if there is some $j > i$ such that $t_i > t_j$, and call the set of all inversions of $(t_1, t_2, \dots, t_k)$ the inversion set of $(t_1, t_2, \dots, t_k)$.

## 2.4 EL-Shellability of Graded Posets

Let $(P, \le)$ be a finite graded poset. We call $(P, \le)$ bounded if it has a unique minimal and a unique maximal element. A chain $c : x = p_0 < p_1 < \cdots < p_k = y$ in some interval $[x, y]$ of $(P, \le)$ is called maximal if there are no $q \in P$ and no $i \in \{0, 1, \dots, k-1\}$ such that $p_i < q < p_{i+1}$. Denote by $\mathcal{E}(P)$ the set of edges in the Hasse diagram of $(P, \le)$. Given a poset $\Lambda$, a function $\lambda : \mathcal{E}(P) \to \Lambda$ is called edge-labeling. Let $\lambda(c)$ denote the sequence of edge-labels $(\lambda(p_0, p_1), \lambda(p_1, p_2), \dots, \lambda(p_{k-1}, p_k))$ of $c$. A maximal chain $c$ is called rising if $\lambda(c)$ is a strictly increasing sequence. For some other maximal chain $c' : x = q_0 < q_1 < \cdots < q_k = y$ in the same interval, we say that $c$ is lexicographically smaller than $c'$ if $\lambda(c)$ is smaller than $\lambda(c')$ with respect to the lexicographic order on $\Lambda^k$. If $\lambda$ is an edge-labeling such that for every interval of $(P, \le)$ there exists exactly one rising maximal chain and this chain is lexicographically smaller than any other maximal chain in this interval, we call $\lambda$ an EL-labeling. A bounded, graded poset that admits an EL-labeling is called EL-shellable.

<footnote>(i) A real reflection group is a reflection group that can be realized in a real vector space.</footnote>
### 3 The Groups $G(d, d, n)$, $d \ge 2$

Remember that the elements of $G(d, d, n)$ are monomial matrices whose non-zero entries are primitive $d$-th roots of unity and the product of all non-zero elements is 1. Consider the set

$$ \{1^{(0)}, 2^{(0)}, \dots, n^{(0)}, 1^{(1)}, 2^{(1)}, \dots, n^{(1)}, \dots, 1^{(d-1)}, 2^{(d-1)}, \dots, n^{(d-1)}\} \quad (2) $$

of integers with $d$ colors. For all integers $1 \le i \le n$ and $0 \le s < d$, identify the colored integer $i^{(s)}$ with the vector $(0, 0, \dots, \zeta_d^s, \dots, 0)^T \in \mathbb{C}^n$, where $\zeta_d = e^{2\pi i \sqrt{-1}/d}$ is a primitive $d$-th root of unity and the non-zero entry appears in the $i$-th position. Hence, $G(d, d, n)$ is isomorphic to a subgroup of the group of permutations of the set (2). We introduce the abbreviations$^{(ii)}$

$$ \begin{aligned} \left[ \begin{pmatrix} i_1^{(t_1)} & \dots & i_k^{(t_k)} \end{pmatrix} \right] &:= \left( i_1^{(t_1)} \dots i_k^{(t_k)} \right) \left( i_1^{(t_1+1)} \dots i_k^{(t_k+1)} \right) \dots \left( i_1^{(t_1+d-1)} \dots i_k^{(t_k+d-1)} \right), \\ \left[ \begin{pmatrix} i_1^{(t_1)} & \dots & i_k^{(t_k)} \end{pmatrix} \right]_s &:= \left( i_1^{(t_1)} \dots i_k^{(t_k)} \right) \left( i_1^{(t_1+s)} \dots i_k^{(t_k+s)} \right) \dots \left( i_1^{(t_1+(d-1)s)} \dots i_k^{(t_k+(d-1)s)} \right). \end{aligned} $$

We can convince ourselves that every element of $G(d, d, n)$ can be uniquely decomposed into “cycles” of the above form. For a better readability, we write $\begin{bmatrix} i_1^{(t_1)} & \dots & i_k^{(t_k)} \end{bmatrix}$ instead of $\begin{bmatrix} i_1^{(t_1)} & \dots & i_k^{(t_k)} \end{bmatrix}_1$. For a detailed description of this group, see for instance [21, Section 3].

Since the reflections in $G(d, d, n)$ are those unitary transformations that have a fixed space of codimension 1, we can represent them as colored transpositions $((i^{(0)}j^{(s)})$, where $1 \le i < j \le n$ and $0 \le s < d$. Clearly, there are $d \cdot \binom{n}{2}$ reflections in $G(d, d, n)$. We will emphasize a certain subset of the set $T$ of all reflections, namely the reflections

$$ ((1^{(0)}2^{(0)}), ((2^{(0)}3^{(0)}), \dots, (((n-1)^{(0)}n^{(0)}), (((n-1)^{(0)}n^{(1)}), \quad (3) $$

call them simple reflections, and denote them by $s_1, s_2, \dots, s_n$ where we fix their order as given above. The product $\gamma = s_1s_2\dots s_n$ is the group element

$$ \gamma = [1^{(0)}2^{(0)} \dots (n-1)^{(0)}] [n^{(0)}]^{-1}, \quad (4) $$

for which we can show that it is a Coxeter element of $G(d, d, n)$. This will be the choice of Coxeter element to which we refer throughout the rest of the paper.

#### 3.1 Compatible Reflection Ordering

Athanasiadis, Brady and Watt introduced in [3] reflection orderings that are compatible with a Coxeter element for real reflection groups. In this section we generalize this concept to the well-generated complex reflection groups $G(d, d, n)$, $d \ge 3$. Before doing so, we make an observation. While in the case of real reflection groups, every $t \in T$ satisfies $t \le_T \gamma$ for a fixed Coxeter element $\gamma$, this is in general not true for complex reflection groups. Consider for instance the group $G(3, 3, 3)$. Equation (1) implies that $NC_{G(3,3,3)}$ has 18 elements. Since this lattice is graded of rank 3 and self-dual, only 8 of the 9 reflections of $G(3, 3, 3)$ are contained in this lattice. Thus, we need to characterize the reflections that are contained in $NC_{G(d,d,n)}$.

**Proposition 3.1** Let $\gamma$ be the Coxeter element of $G(d, d, n)$ as given in (4). A reflection $t = ((i^{(0)}j^{(s)})$ of $G(d, d, n)$ satisfies $t \not\le_T \gamma$ if and only if $j < n$ and $1 \le s < d-1$.

<footnote>(ii) The addition in the superscript is understood modulo $d$.</footnote>
For a Coxeter element $\gamma$ of $G(d, d, n)$, denote by $T_\gamma$ the set of all reflections $t \in T$ that satisfy $t \le_T \gamma$. Let $t_1, t_2 \in T_\gamma$ be non-commuting reflections and denote by $I(t_1, t_2)$ the interval of smallest rank in $NC_{G(d,d,n)}$ that contains $t_1$ and $t_2$. If $I(t_1, t_2)$ has rank 2, we know that either $t_1 t_2 \le_T \gamma$ or $t_2 t_1 \le_T \gamma$.

**Definition 3.2** Let $\gamma$ be a Coxeter element of $G(d, d, n)$. We call an ordering $\prec$ of $T_\gamma$ a $\gamma$-compatible reflection ordering if for all non-commuting reflections $t_1, t_2 \in T_\gamma$ such that $I(t_1, t_2)$ has rank 2, there are exactly two reflections $\tilde{t}_1, \tilde{t}_2 \in T_\gamma \cap I(t_1, t_2)$ such that $\tilde{t}_1 \tilde{t}_2 \le_T \gamma$ implies $\tilde{t}_1 \prec \tilde{t}_2$.

**Lemma 3.3** Let $\gamma$ be the Coxeter element as defined in (4). The following ordering of $T_\gamma$ is a $\gamma$-compatible reflection ordering for $G(d, d, n)$.

$$ ((1^{(0)}2^{(0)})) < ((1^{(0)}3^{(0)})) < \dots < ((1^{(0)}(n-1)^{(0)})) \\ < ((2^{(0)}3^{(0)})) < \dots < ((2^{(0)}(n-1)^{(0)})) \\ < ((3^{(0)}4^{(0)})) < \dots < (((n-2)^{(0)}(n-1)^{(0)})) \\ < ((1^{(0)}n^{(0)})) < ((1^{(0)}n^{(d-1)})) < \dots < ((1^{(0)}n^{(1)})) \\ < ((1^{(0)}2^{(d-1)})) < \dots < ((1^{(0)}(n-1)^{(d-1)})) \\ < ((2^{(0)}n^{(0)})) < ((2^{(0)}n^{(d-1)})) < \dots < ((2^{(0)}n^{(1)})) \\ < ((2^{(0)}3^{(d-1)})) < \dots < ((2^{(0)}(n-1)^{(d-1)})) \\ < ((3^{(0)}n^{(0)})) < ((3^{(0)}n^{(d-1)})) < \dots < (((n-1)^{(0)}n^{(1)})). \quad (5) $$

**Example 3.4** Consider the group $G(3, 3, 3)$. According to (5), we obtain a $\gamma$-compatible reflection ordering as

$$ ((1^{(0)}2^{(0)})) < ((1^{(0)}3^{(0)})) < ((1^{(0)}3^{(2)})) < ((1^{(0)}3^{(1)})) < ((1^{(0)}2^{(2)})) \\ < ((2^{(0)}3^{(0)})) < ((2^{(0)}3^{(2)})) < ((2^{(0)}3^{(1)})). \quad (6) $$

# 4 Auxiliary Results

This section contains some auxiliary results that help us proving Theorem 5.1. We first collect some results on the structure of $NC_{G(d,d,n)}$. Subsequently, we give some lemmas that explain how certain transformations of reduced $T_\gamma$-words of $\gamma$ affect the descent set of the respective words. For the proofs of these lemmas, see [21].

## 4.1 The Structure of $NC_{G(d,d,n)}$

Unless otherwise stated, the following results were first observed by Athanasiadis, Brady and Watt [3] in the case of real reflection groups. Note that we write $NC_{G(d,d,n)}(\gamma)$ if we want to point out a specific choice of Coxeter element $\gamma$ and that we consider the natural edge-labeling $\lambda : \mathcal{E}(NC_{G(d,d,n)}(\gamma)) \to T_\gamma$, $(u, v) \mapsto u^{-1}v$. Given a non-singleton interval $[u, v]$, we write $\lambda([u, v])$ for the set of label sequences of the maximal chains from $u$ to $v$.

**Lemma 4.1** Let $[u, v]$ be a non-singleton interval in $NC_{G(d,d,n)}(\gamma)$ and denote by $T_\gamma$ the set of all reflections in $NC_{G(d,d,n)}(\gamma)$.
(i) If $[u, v]$ has length two and $(s, t) \in \lambda([u, v])$, then $(t, s') \in \lambda([u, v])$ for some $s' \in T_\gamma$.

(ii) If $t \in T_\gamma$ appears in some coordinate of an element $\lambda([u, v])$, then $t = \lambda(u, u')$ for some covering relation $(u, u')$ in $[u, v]$.

(iii) The reflections appearing as the coordinates of an element of $\lambda([u, v])$ are pairwise distinct.

**Lemma 4.2** Let $[u, v]$ be a non-singleton interval in $NC_{G(d,d,n)}(\gamma)$ and let $w = u^{-1}v$. The poset isomorphism $f : [\epsilon, w] \to [u, v]$ given by $f(x) = ux$ satisfies $\lambda(x, y) = \lambda(f(x), f(y))$ for all covering relations $(x, y)$ in $[\epsilon, w]$.

With the help of the previous results, it is possible to prove the following theorem.

**Theorem 4.3** Let $\gamma$ be a Coxeter element of $G(d, d, n)$. For any total ordering of $T_\gamma$ and any non-singleton interval $[u, v]$ in $NC_{G(d,d,n)}(\gamma)$ the lexicographically smallest maximal chain in $[u, v]$ is rising with respect to $\lambda$.

Since EL-shellability is a property that needs to be satisfied by every interval of a poset, it is helpful to understand the nature of the intervals of $NC_W$, for a well-generated complex reflection group $W$. Denote by $V$ the complex vector space on which $W$ acts. We call the maximal subgroup of $W$ that fixes some $A \subseteq V$ pointwise parabolic subgroup of $W$. It follows from [28, Theorem 1.5] that the parabolic subgroup of $W$ which fixes $A \subseteq V$, is generated by the reflections $t \in W$ that satisfy $A \subseteq \text{Fix}(t)$. Moreover, it follows from [6, Lemma 2.7] that a parabolic subgroup of $W$ is again a well-generated complex reflection group. An analogous property holds for Coxeter elements.

**Proposition 4.4** ([24, Proposition 6.3(i),(ii)]) Let $W$ be a well-generated complex reflection group and $w \in W$. Let $T$ denote the set of all reflections of $W$. The following properties are equivalent:

(i) $w$ is a Coxeter element in a parabolic subgroup of $W$;

(ii) There is a Coxeter element $\gamma_w$ of $W$ such that $w \le_T \gamma_w$.

We call $w$ parabolic Coxeter element if it satisfies one of the properties stated in Proposition 4.4, and denote by $G(d, d, n)_w$ the parabolic subgroup of $G(d, d, n)$ in which $w$ is a Coxeter element.

**Lemma 4.5** Let $\gamma$ be a Coxeter element of $G(d, d, n)$. If $w \le_T \gamma$, then any $\gamma$-compatible reflection ordering for $G(d, d, n)$ restricts to a $w$-compatible reflection ordering for $G(d, d, n)_w$.

## 4.2 Shifting of Reduced Words

Since the reflections of $G(d, d, n)$ have order two, we can apply the results on shifted words that are generally valid for real reflection groups. Let us therefore recall the shifting lemma, as given in [1, Lemma 2.5.1].

**Lemma 4.6 (THE SHIFTING LEMMA)** Let $W$ be a complex reflection group, with the property that all reflections of $W$ have order 2. Let $(t_1, t_2, \dots, t_k)$ be a reduced $T$-word for $w \in W$, and let $1 < i < k$. Then the two sequences

$$ (t_1, t_2, \dots, t_{i-2}, t_i, t_i t_{i-1} t_i, t_{i+1}, \dots, t_k) \quad \text{and} \quad (t_1, t_2, \dots, t_{i-1}, t_i t_{i+1} t_i, t_i, t_{i+2}, \dots, t_k) $$

are also reduced $T$-words for $w$.
We call the new sequences in Lemma 4.6 left-shift respectively right-shift of $(t_1, t_2, \dots, t_k)$ at (position) $i$. Strictly speaking, Armstrong proved the shifting lemma for real reflection groups only. Since all reflections of a real reflection group have order 2, we can carry over the proof of [1, Lemma 2.5.1] word by word.

It follows from the definition of $\lambda$ that for any maximal chain $c$ of $NC_{G(d,d,n)}(\gamma)$ the sequence of edge-labels $\lambda(c)$ is a reduced $T_\gamma$-word for $\gamma$. Unless otherwise stated, the Coxeter element $\gamma$ which we consider in the remainder of this section is the one given in (4) and the descents (see Section 2.3) in the following lemmas refer to the ordering of $T_\gamma$ as given in (5).

**Lemma 4.7** Let $s_1, s_2, \dots, s_n$ be the simple reflections of $G(d, d, n)$ as given in (3). By definition, $(s_1, s_2, \dots, s_n)$ is a reduced $T_\gamma$-word for $\gamma$. For every $1 < k \le n$, the left-shift of $(s_1, s_2, \dots, s_n)$ at position $k$ has a descent at $k-1$.

**Lemma 4.8** Let $(t_1, t_2, \dots, t_n)$ be a reduced $T_\gamma$-word for $\gamma$ that has a descent at $k$. The left-shift $(t_1, \dots, t_k, t_{k+2}, t_{k+2}t_{k+1}t_{k+2}, t_{k+3}, \dots, t_n)$ at $k+2$ has a descent at $k$ or at $k+1$.

**Lemma 4.9** Let $(t_1, t_2, \dots, t_n)$ be a reduced $T_\gamma$-word for $\gamma$ that has a descent at $k$. The left-shift $(t_1, \dots, t_{k-1}, t_{k+1}, t_{k+1}t_k t_{k+1}, \dots, t_n)$ at $k+1$ has no descent at $k$ if and only if

$$t_k = ((i^{(0)}j^{(0)})), \quad t_{k+1} = ((i^{(0)}a^{(0)})), \quad \text{where } 1 \le i < a < j < n, \text{ or}$$

$$t_k = ((i^{(0)}j^{(-1)})), \quad t_{k+1} = ((i^{(0)}a^{(0)})), \quad \text{where } 1 \le i < a < j < n, \text{ or}$$

$$t_k = ((i^{(0)}n^{(s)})), \quad t_{k+1} = ((i^{(0)}j^{(0)})).$$

**Lemma 4.10** Let $\gamma$ be a Coxeter element of $G(d, d, n)$ and let $w \le_T \gamma$ with $\ell_T(w) = k$. Let $(u_1, u_2, \dots, u_k)$ be a reduced $T_w$-word for $w$. A sequence $(t_1, t_2, \dots, t_k)$ is a reduced $T_w$-word for $w$ if and only if it can be obtained from $(u_1, u_2, \dots, u_k)$ by a finite number of left-shifts.

# 5 EL-Shellability of $NC_{G(d,d,n)}$

We have stated in the previous section that left-shifting a given reduced $T_\gamma$-word for $\gamma$ reduces the number of descents only in a few cases. We use this fact to prove the EL-shellability of $NC_{G(d,d,n)}$.

**Theorem 5.1** Let $\gamma$ be the Coxeter element of $G(d, d, n)$ as defined in (4) and let $T_\gamma$ be the set of all reflections $t \in G(d, d, n)$ that satisfy $t \le_T \gamma$. Let $\lambda : \mathcal{E}(NC_{G(d,d,n)}) \to T_\gamma$ be the natural labeling function of $NC_{G(d,d,n)}$ that maps an edge $(u, v)$ to the reflection $u^{-1}v$. If $T_\gamma$ is ordered as in (5), $\lambda$ is an EL-labeling for $NC_{G(d,d,n)}$.

**Proof:** According to Theorem 4.3, the lexicographically smallest chain in every interval of $NC_{G(d,d,n)}$ is rising for any ordering of $T_\gamma$. Thus, it only remains to show that there is at most one rising chain in every interval. By Lemma 4.2, it is sufficient to consider intervals of the form $[\varepsilon, w]$. Proposition 4.4 states that $w$ is a Coxeter element in the parabolic subgroup $G(d, d, n)_w$. Theorem 1.5 in [28] implies that $G(d, d, n)_w$ is generated by a subset of the reflections of $G(d, d, n)$. By Lemma 4.5 we know that the restriction of the ordering in (5) to $G(d, d, n)_w$ yields a $w$-compatible reflection ordering. Hence, it is sufficient to consider the interval $[\varepsilon, \gamma]$. Let $s_1, s_2, \dots, s_n$ be the simple reflections of $G(d, d, n)$ as given in (3). The reduced $T_\gamma$-word $(s_1, s_2, \dots, s_n)$ is rising with respect to the ordering given in (5). At the same time we notice that any other permutation of the simple reflections cannot yield a rising labeling.
(Any other permutation of $s_1, s_2, \dots, s_n$ does not even yield a reduced $T_\gamma$-word for $\gamma$.) So the remaining task is to show that a maximal chain $c$ cannot be rising if its label sequence $\lambda(c) = (t_1, t_2, \dots, t_n)$ is not a permutation of simple reflections.

It follows from Lemma 4.10 that every reduced $T_\gamma$-word of $\gamma$ can be obtained from $(s_1, s_2, \dots, s_n)$ by a finite number of left-shifts. If the reduced $T_\gamma$-word $(t_1, \dots, t_{k-1}, t_k, t_{k+1}, \dots, t_n)$ has a descent at position $k$, then the corresponding left-shift at $k$ has an inversion at $k-1$ and hence a descent at $k-1$ or $k$. Lemma 4.8 shows that a left-shift at $k+2$ does not reduce the number of descents. In view of Lemma 4.9, we notice that there are only three cases in which a left-shift at $k+1$ removes the descent at $k$.

(i) $t_k = ((i^{(0)}j^{(0)})), t_{k+1} = ((i^{(0)}a^{(0)})$, where $1 \le i < a < j < n$. Let $\tilde{a}$ be the colored integer that is sent to $a^{(0)}$ by $t_{k+2}t_{k+3}\cdots t_n$. Clearly, $t_k t_{k+1} \cdots t_n$ sends $\tilde{a}$ to $j^{(0)}$. If $\tilde{a} = n^{(s)}$, there must be reflections among $t_1, \dots, t_{k-1}$ forming the cycle $((j^{(0)} \dots n^{(t)}))$. One of these reflections must be larger than $t_{k+1}$. Now consider $\tilde{a} = (j-1)^{(0)}$. Hence, there must be reflections forming the cycle $((a^{(0)} \dots (j-1)^{(s)}))$ among $t_{k+2}, \dots, t_n$. At least one of these reflections is smaller than $t_{k+1}t_k t_{k+1} = ((a^{(0)}j^{(0)}))$. Only the case $\tilde{a} = b^{(s)}$ remains, where $1 \le b < n$ is not considered above. Hence, there must be a cycle $((j^{(0)} \dots (b+1)^{(s)}))$, formed by some reflections among $t_1, \dots, t_{k-1}$. At least one of the reflections forming this cycle must be larger than $t_k$. So in each case there is (at least) one inversion in the left-shift.

(ii) $t_k = ((i^{(0)}j^{(-1)})), t_{k+1} = ((i^{(0)}a^{(0)})$, where $1 \le i < a < j < n$. This case works analogously to (i).

(iii) $t_k = ((i^{(0)}n^{(s)})), t_{k+1} = ((i^{(0)}j^{(0)})$. Let $\tilde{a}$ be the colored integer that is sent to $n^{(t)}$ by $t_{k+2}t_{k+3}\cdots t_n$. Analogously to (i), we notice that there must be at least one inversion in the respective left-shift.

The previous paragraphs show that any left-shift of a reduced $T_\gamma$-word for $\gamma$ that already contains a descent, has at least one inversion and thus at least one descent. (The only case, where this reasoning fails, is the case where the left-shift is the reduced $T_\gamma$-word $(s_1, s_2, \dots, s_n)$.) Finally, Lemma 4.7 concludes the proof by implying that any left-shift of $(s_1, s_2, \dots, s_n)$ creates a descent. $\square$

**Example 5.2** Figure 1 shows the lattice $NC_{G(3,3,3)}$. The given integer labeling is derived from the natural labeling $\lambda$ by mapping every reflection to its position in the reflection ordering given in (6). We notice that this is an EL-labeling, where the unique rising chain in the interval $[\varepsilon, \gamma]$ is indicated with thick lines.

# 6 EL-Shellability of $NC_W$ for the Exceptional Groups $W$

In this section, we state the EL-shellability of $NC_W$ where $W$ is an exceptional well-generated complex reflection group. It turns out that the noncrossing partition lattice of most of these groups is isomorphic to the noncrossing partition lattice of some real reflection group. Only five groups, namely $G_{24}, G_{27}, G_{29}, G_{33}$ and $G_{34}$, remain unrelated to any known case. For these cases we have derived an EL-labeling with a computer program$^{(iii)}$. The details can be found in [21, Section 7].

**Theorem 6.1** Let $W$ be an exceptional well-generated complex reflection group. Then, $NC_W$ is EL-shellable.

**Proof:** See [21, Theorem 7.1]. $\square$

<footnote>(iii) This tool is called LINS and can be found at http:// homepage.univie.ac.at/henri.muehle/misc.php.</footnote>
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** The lattice of noncrossing partitions of $G(3, 3, 3)$ with its natural edge-labeling. The integer labels correspond to the position of the reflections in (6).</figcaption></figure>

# 7 EL-Shellability of $m$-Divisible Noncrossing Partitions

Up to now, we have shown that the lattices of noncrossing partitions are EL-shellable for all well-generated complex reflection groups. Bearing this result in mind, we are able to finally prove Theorem 1.1.

**Proof of Theorem 1.1:** It follows from Theorem 5.1 and Theorem 6.1 as well as [3, Theorem 1.1] that $NC_W$ is EL-shellable, for every well-generated complex reflection group $W$. Hence, we can construct an EL-labeling for $NC_W^{(m)} \cup \{\hat{0}\}$ in the same way as described in [1, Theorem 3.7.2]. □

# 8 Applications

EL-shellability of a partially ordered set implies a certain structure of the associated order complex. In the present case, this structure was already conjectured in [2] and can now be proved. Recall that the Fuss-Catalan numbers $Cat^{(m)}(W)$, see (1), count the $m$-divisible noncrossing partitions associated to a well-generated complex reflection group $W$ for some $m \in \mathbb{N}$.

**Corollary 8.1** Let $W$ be a well-generated complex reflection group of rank $n$ and let $m$ be a positive integer. The order complex of the poset $NC_W^{(m)}$ with maximal and minimal elements removed is homotopy equivalent to a wedge of $(Cat^{(-m-1)}(W) - Cat^{(-m)}(W))$-many $(n-2)$-spheres.

The previous result has consequences for the Möbius function of $NC_W^{(m)}$ as conjectured in [29].

**Corollary 8.2** Let $W$ be a well-generated complex reflection group of rank $n$ and let $\gamma$ be a Coxeter element of $W$. Denote by $M$ the set of minimal elements of $NC_W^{(m)}(\gamma)$. Consider the lattice $(NC_W^{(m)}(\gamma) \setminus M) \cup \{\hat{0}\}$ that arises from $NC_W^{(m)}(\gamma) \setminus M$ by adding a unique minimal element $\hat{0}$. For all positive integers $m$, we have $\mu(\hat{0}, \gamma) = (-1)^n (Cat^{(-m-1)}(W) - Cat^{(-m)}(W))$.
References

[1] D. Armstrong. Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups. *Mem. Amer. Math. Soc.*, 202, 2009.

[2] D. Armstrong and C. Krattenthaler. Euler Characteristic of the Truncated Order Complex of Generalized Noncrossing Partitions. *Elec. J. Combin.*, 16, 2009.

[3] C. A. Athanasiadis, T. Brady, and C. Watt. Shellability of Noncrossing Partition Lattices. *Proc. Amer. Math. Soc.*, 135:939–949, 2007.

[4] C. A. Athanasiadis and V. Reiner. Noncrossing Partitions for the Group $D_n$. *SIAM J. Discrete Math.*, 18:397–417, 2004.

[5] D. Bessis. The Dual Braid Monoid. *Ann. Sci. École Norm. Sup.*, 36:647–683, 2003.

[6] D. Bessis. Finite Complex Reflection Arrangements are $K(\pi, 1)$. *arXiv:0610.777*, 2007.

[7] D. Bessis and R. Corran. Non-crossing Partitions of Type $(e, e, r)$. *Adv. Math.*, 202:1–49, 2006.

[8] D. Bessis and V. Reiner. Cyclic Sieving of Noncrossing Partitions for Complex Reflection Groups. *Ann. of Comb.*, 15:197–222, 2011.

[9] A. Björner. Shellable and Cohen-Macaulay Partially Ordered Sets. *Trans. Amer. Math. Soc.*, 260:159–183, 1980.

[10] A. Björner and M. L. Wachs. On Lexicographically Shellable Posets. *Trans. Amer. Math. Soc.*, 277:323–341, 1983.

[11] T. Brady. A Partial Order on the Symmetric Group and new $K(\pi, 1)$'s for the Braid Groups. *Adv. Math.*, 161:20–40, 2001.

[12] T. Brady and C. Watt. $K(\pi, 1)$'s for Artin Groups of Finite Type. *Geom. Dedicata*, 94:225–250, 2002.

[13] T. Brady and C. Watt. Lattices in Finite Real Reflection Groups. *arXiv:0501502*, 2005.

[14] M. Broué, G. Malle, and R. Rouquier. Complex Reflection Groups, Braid Groups, Hecke Algebras. *Journal für die reine und angewandte Mathematik*, 500:127–190, 1998.

[15] F. Chapoton. Enumerative Properties of Generalized Associahedra. *Séminaire Lotharingien de Combinatoriore*, 51, 2004.

[16] P. H. Edelman. Chain Enumeration and Non-Crossing Partitions. *Discrete Math.*, 31:171–180, 1980.

[17] G. Kreweras. Sur les partitions non croisées d'un cycle. *Discrete Math.*, 1:333–350, 1972.

[18] G. I. Lehrer and J. Michel. Invariant Theory and Eigenspaces for Unitary Reflection Groups. *C. R. Math. Acad. Sci. Paris*, 336:795–800, 2003.
[19] G. I. Lehrer and D. E. Taylor. *Unitary Reflection Groups*. Cambridge University Press, Cambridge, 2009.

[20] J. McCammond. Noncrossing Partitions in Surprising Locations. *Amer. Math. Monthly*, 113:598–610, 2006.

[21] H. Mühle. EL-Shellability of Generalized Noncrossing Partitions Associated to Well-Generated Complex Reflection Groups. *arXiv:1111.7172*, 2011.

[22] P. Orlik and L. Solomon. Unitary Reflection Groups and Cohomology. *Invent. Math.*, 59:77–94, 1980.

[23] V. Reiner. Non-Crossing Partitions for Classical Reflection Groups. *Discrete Math.*, 177:195–222, 1997.

[24] V. Ripoll. Orbites d'Hurwitz des factorisations primitives d'un élément de Coxeter. *J. Algebra*, 323:1432–1453, 2010.

[25] G. C. Shephard and J. A. Todd. Finite Unitary Reflection Groups. *Canad. J. Math.*, 6:274–304, 1954.

[26] R. Simion. Noncrossing Partitions. *Discrete Math.*, 217:397–409, 2000.

[27] T. A. Springer. Regular Elements of Finite Reflection Groups. *Invent. Math.*, 25:159–198, 1974.

[28] R. Steinberg. Differential Equations Invariant under Finite Reflection Groups. *Trans. Amer. Math. Soc.*, 112:392–400, 1964.

[29] M. Tomie. Möbius Numbers of Some Modified Generalized Noncrossing Partitions. *arXiv:0905.1660*, 2009.