, , , February 28, 2005

Consider a finite real reflection group

W

and the partial order on

W

defined by letting

u ≼ v

if there exists a shortest factorization of

u

as a product of reflections in

W

which is a prefix of such a shortest factorization of

v

. This order turns

W

into a graded poset having the identity

1

as its unique minimal element, where the rank of

w

is the length of a shortest factorization of

w

into reflections. For any

w \in W

we denote by

N C_{W} (w)

the interval

[1, w]

in this partial order. We are primarily interested in the case that

w

is a Coxeter element

γ

W

, viewed as a finite Coxeter group. Since all Coxeter elements of

W

are conjugate to each other, the isomorphism type of the poset

N C_{W} (γ)

is independent of

γ

. We denote this poset by

N C_{W}

when the choice of the Coxeter element

γ

is irrelevant and call

N C_{W}

the noncrossing partition lattice associated to

W

The poset

N C_{W}

plays a crucial role in the construction of new monoid structures and

K (π, 1)

spaces for Artin groups associated with finite Coxeter groups; see for instance [3, 6, 7] and the survey articles [11, 12] . It is self-dual [3,Section2.3] , graded and has been verified case by case to be a lattice [3,Fact2.3.1] [7,Section4] . For Coxeter groups of types

A

and

B

in the Cartan-Killing classification it is isomorphic to the classical lattice of noncrossing partitions of an

n

-element set, defined and studied by Kreweras [10] , and to its type

B

analogue, defined by Reiner [14] , respectively.

The main purpose of the present article is to give a case-free proof of the following theorem.

Theorem 1.1. The poset

N C_{W}

is EL-shellable for any finite Coxeter group

W

EL-shellability (see Section 2 ) for a bounded graded poset

P

of rank

r

implies that the simplicial complex

Δ (\bar{P})

of chains in the proper part of

P

is shellable.

In particular it implies that the geometric realization of

Δ (\bar{P})

has the homotopy type of a wedge of

(r - 2)

-dimensional spheres, the number of which is determined by the EL-labeling, and that the Stanley-Reisner ring of

Δ (\bar{P})

is Cohen-Macaulay over an arbitrary field.

Theorem 1.1 was proved by Björner and Edelman [4,Example2.9] in the case of Coxeter groups of type

A

and by Reiner [14,Section6] in the case of type

B

while it was left open in [2,Section7] in that of type

D

and was conjectured by Reiner [15] for all finite Coxeter groups. After introducing basic definitions, notation and some preliminary lemmas related to real reflection groups, root systems and shellability (Section 2 ) we proceed as follows. We give sufficient conditions on a total ordering of the set of reflections

T

and a Coxeter element

γ

of a crystallographic group

W

for the natural edge labeling of

N C_{W} (γ)

with label set

T

to be an EL-labeling (Theorem 3.5 ). We exploit these conditions to describe explicit families of EL-labelings in the cases of the classical reflection groups (Examples 3.3 and 3.4 and Corollary 3.12 ). The existence of a total ordering and Coxeter element for any

W

which satisfy these sufficient conditions follows from recent work of the last two authors [8] , where a case-free proof of the lattice property of

N C_{W}

is given. The particular orderings and Coxeter elements considered there (see Section 4 ) were introduced by Steinberg [18] and play a crucial role in the constructions of [8] . It is shown in Section 4 (Theorem 4.2 ) that they provide EL-labelings of

N C_{W}

for any finite real reflection group (including the non-crystallographic ones). A result on the Möbius function of

N C_{W}

is deduced (Corollary 4.3 ).

2 Preliminaries

Reflection groups and root systems. Let

W

be a finite real reflection group of rank

ℓ

with a corresponding root system

Φ

, acting faithfully by orthogonal transformations on an

ℓ

-dimensional Euclidean space

V

with inner product

(,)

Thus

W

is generated by elements acting as orthogonal reflections in

V

while

Φ

is invariant under the action of

W

and consists of a pair

{α, - α}

of nonzero vectors for each reflection

t

W

, which are orthogonal to the reflecting hyperplane of

t

We denote by

T

the set of all reflections in

W

, by

H_{α}

the linear hyperplane in

V

orthogonal to

α

and by

t_{α}

the orthogonal reflection in

H_{α}

. We refer the reader to the texts by Björner and Brenti [5] and Humphreys [9] for any undefined terminology and background on reflection groups and root systems. In particular we assume the notions of a positive system, simple system and simple reflection. A Coxeter element of

W

is the product of the simple reflections in an arbitrary order for any choice of simple system for

Φ

. The order of any Coxeter element of

W

is the Coxeter number, denoted by

h

. The root lattice

Q_{Φ}

is the

Z

-span of

Φ

. The root system

Φ

is called crystallographic and

W

is called a Weyl group if

W

preserves

Q_{Φ}

The next lemma follows from the results of Sommers in [16,Section3] (see also [13,Lemma2.3] ).

Lemma 2.1. ([16] ) If

α_{1}, α_{2}, . . ., α_{r} \in Φ

and

α_{1} + α_{2} + \dots + α_{r} = α \in Φ

then

α_{1} = α

or there exists

i

with

2 \leq i \leq r

such that

α_{1} + α_{i} \in Φ \cup {0}

Proof. See [1,Lemma2.1(ii)] . □

Lemma 2.2. If

{α_{1}, α_{2}, . . ., α_{ℓ}} \subseteq Φ^{+}

is a

Z

-basis of the root lattice

Q_{Φ}

and

α_{i} - α_{j} / \in Φ

for all

i < j

then

{α_{1}, α_{2}, . . ., α_{ℓ}}

is the set of simple roots in

Φ^{+}

Proof. It suffices to prove that any positive root $α \in Φ^{+}$ can be written as a linear combination of $α_{1}, α_{2}, . . ., α_{ℓ}$ with nonnegative integer coefficients. Since ${α_{1}, α_{2}, . . ., α_{ℓ}}$ is a $Z$ -basis of the root lattice we can write uniquely $α = r_{1} α_{1} + r_{2} α_{2} + \dots + r_{ℓ} α_{ℓ}$ for some integers $r_{i}$ . Let us rewrite this expression as $α = β_{1} + β_{2} + \dots + β_{r}$ where there are $r_{i}$ copies of $α_{i}$ or $- r_{i}$ copies of $- α_{i}$ among the $β$ 's if $r_{i} \geq 0$ or $r_{i} < 0$ , respecively. To show that $r_{i} \geq 0$ for $1 \leq i \leq ℓ$ we must show that $β_{i} \in Φ^{+}$ for $1 \leq i \leq r$ . Suppose that $β_{i}$ is a negative root for some $i$ , say for $i = 1$ . Since $α \in Φ^{+}$ at least one of the $β$ 's is a positive root. By applying repeatedly Lemma 2.1 and reordering the $β$ 's if necessary we may assume that there exists an index $2 \leq j \leq r$ such that $β_{1} + β_{2} + \dots + β_{i} \in Φ$ for $1 \leq i < j$ , $β_{j} \in Φ^{+}$ , $β_{i} \in - Φ^{+}$ for $1 \leq i < j$ and $β_{1} + β_{2} + \dots + β_{j} \in Φ \cup {0}$ . Since the $α$ 's are linearly independent we must have $β_{1} + β_{2} + \dots + β_{j} \in Φ$ . Applying Lemma 2.1 once more we conclude that $β_{i} + β_{j} \in Φ$ for some $1 \leq i < j$ , which means that $α_{i} - α_{j} \in Φ$ for some $i < j$ , contrary to the hypothesis. □

EL-labelings and shellability. Let

(P, \leq)

be a finite bounded graded poset (short for partially ordered set). Thus

P

has a unique minimal and a unique maximal element, denoted

\hat{0}

and

\hat{1}

respectively, and all maximal (with respect to inclusion) chains in

P

have the same length (one less than their number of elements), called the rank of

P

and denoted

r a n k (P)

. Let

ℰ (P)

be the set of covering relations of

P

, meaning pairs

(x, y)

of elements of

P

such that

x < y

holds in

P

and

x < z \leq y

holds only for

z = y

, and let

Λ

be a totally ordered set. An edge labeling of

P

with label set

Λ

is a map

λ : ℰ (P) \to Λ

. Let

c

be an unrefinable chain

x_{0} < x_{1} < \dots < x_{r}

of elements of

P

, so that

(x_{i - 1}, x_{i}) \in ℰ (P)

for all

1 \leq i \leq r

. We let

λ (c) = (λ (x_{0}, x_{1}), λ (x_{1}, x_{2}), . . ., λ (x_{r - 1}, x_{r}))

be the label of

c

with respect to

λ

and call

c

rising or falling with respect to

λ

if the entries of

λ (c)

strictly increase or weakly decrease, respectively, in the total order of

Λ

. We say that

c

is lexicographically smaller than an unrefinable chain

c^{'}

P

of the same length (with respect to

λ

) if

λ (c)

precedes

λ (c^{'})

in the lexicographic order induced by the total order of

Λ

Definition 2.3. ([4] ) An edge labeling

λ

P

is called an EL-labeling if for every non-singleton interval

[u, v]

P

(i) there is a unique rising maximal chain in $[u, v]$ and
(ii) this chain is lexicographically smallest among all maximal chains in $[u, v]$

with respect to

λ

. The poset

P

is called EL-shellable if it has an EL-labeling for some label set

Λ

See [17,Chapter3] for more background on partially ordered sets and EL-shellability. If

P

is EL-shellable then the simplicial complex of chains (order complex)

Δ (\bar{P})

of the proper part

\bar{P} = P - {\hat{0}, \hat{1}}

P

has the homotopy type of a wedge of spheres of dimension

r a n k (P) - 2

. The number of these spheres is equal to the number of falling maximal chains of

P

with respect to the EL-labeling and is also equal to the Möbius number of

P

, up to the sign

(- 1)^{r a n k (P)}

; see [17,Section3.13] .

Reflection length and the poset

N C_{W} (w)

. For

w \in W

let

l_{T} (w)

denote the smallest

k

such that

w

can be written as a product of

k

reflections in

T

. The partial order

≼

W

is defined by letting

u ≼ v if and only if l_{T} (u) + l_{T} (u^{- 1} v) = l_{T} (v),

in other words if there exists a shortest factorization of

u

into reflections in

T

which is a prefix of such a shortest factorization of

v

. With this order

W

is a graded poset having the identity

1

as its unique minimal element and rank function

l_{T}

We denote by

F (w)

the subspace of

V

fixed by

w

. The next lemma follows from the results in [7,Section2] (see also [3,Lemma1.2.1] ).

Lemma 2.4. ([7] ) Let

w \in W

(i) $l_{T} (w) = ℓ - dim F (w)$ .
(ii) For $α \in Φ^{+}$ we have $t_{α} ≼ w$ if and only if $F (w) \subseteq H_{α}$ .

The interval

[1, w]

(W, ≼)

, denoted

N C_{W} (w)

, is also graded with rank function

l_{T}

and has rank

ℓ = dim V

w

is a Coxeter element of

W

3 Reflection Orderings, Coxeter elements and EL-Labelings

Let

W

be a finite real reflection group of rank

ℓ

with corresponding root system

Φ \subset V

and set of reflections

T

. Let

Φ^{+} \subset Φ

be a fixed choice of a positive system.

A total ordering

<

T

is called a reflection ordering for

W

[5,Section5.1] if whenever

α, α_{1}, α_{2} \in Φ^{+}

are distinct roots and

α

is a positive linear combination of

α_{1}

and

α_{2}

we have either

t_{α_{1}} < t_{α} < t_{α_{2}}

t_{α_{2}} < t_{α} < t_{α_{1}} .

An induced subsystem of

Φ

of rank

i

is the intersection

Φ^{'}

Φ

with the linear span of

i

linearly independent roots in

Φ

. The set

Φ^{'}

is a root system on its own and

Φ^{'} \cap Φ^{+}

is a choice of a positive system for

Φ^{'}

. The following is the main definition in this section.

Definition 3.1. A reflection ordering

<

T

is compatible with a Coxeter element

γ

W

if for any irreducible rank 2 induced subsystem

Φ^{'} \subseteq Φ

the following holds: if

α

and

β

are the simple roots of

Φ^{'}

with respect to

Φ^{'} \cap Φ^{+}

and

t_{α} t_{β} \in N C_{W} (γ)

then

t_{α} < t_{β}

Observe that a rank 2 subsystem

Φ^{'} \subseteq Φ

is irreducible if and only if

Φ^{'} \cap Φ^{+}

has at least three roots.

Example 3.2. Let

W

be of rank 2, so that

W

is a dihedral group of order

2 m

for some

m \geq 2

. Let

α

and

β

be the two simple roots in

Φ

. There are

m

reflections in

W

, namely

t_{1}, t_{2}, . . ., t_{m}

where

t_{i} = t_{α} (t_{β} t_{α})^{i - 1}

(so

t_{1} = t_{α}

and

t_{m} = t_{β}

) and two reflection orderings, namely

t_{1} < t_{2} < \dots < t_{m}

and its reverse. The reflection ordering

<

is compatible with the Coxeter element

γ = t_{α} t_{β}

. The poset

N C_{W} (γ)

has

m

maximal chains corresponding to the

m

shortest factorizations

γ = t_{1} t_{m} = t_{2} t_{1} = \dots = t_{m} t_{m - 1}

γ

into reflections. Clearly the chain corresponding to the factorization

γ = t_{1} t_{m}

is the unique rising maximal chain and the lexicographically smallest maximal chain in the edge labeling of

N C_{W} (γ)

which assigns the label

(t_{i}, t_{j})

to the chain corresponding to a factorization

γ = t_{i} t_{j}

, when the label set

T

is totally ordered by

<

. □

Example 3.3. Let

W

be of type

A_{n - 1}

and

Φ^{+} = {e_{i} - e_{j} : 1 \leq i < j \leq n}

be the set of positive roots. Thus

W

is isomorphic to the symmetric group of permutations of the set

{1, 2, . . ., n}

and the reflections correspond to the transpositions

(i, j)

for

1 \leq i < j \leq n

. If the

n

-cycle

γ = (1, 2, . . ., n)

is chosen as the Coxeter element for

W

then there is a canonical isomorphism of

N C_{W} (γ)

with the classical lattice of noncrossing partitions of

{1, 2, . . ., n}

(see for instance [3,Section4] or [6,Section3] ). One can easily check that any total ordering on the set of transpositions

(i, j)

, where

1 \leq i < j \leq n

, for which

(i, j) < (i, k) < (j, k)

for

1 \leq i < j < k \leq n

(such as the lexicographic ordering) induces a reflection ordering for

W

which is compatible with

γ

. □

Example 3.4. Let

W

be of type

B_{n}

D_{n}

and

Φ^{+} = {\begin{matrix} {e_{i} : 1 \leq i \leq n} \cup {e_{i} \pm e_{j} : 1 \leq i < j \leq n}, & for W of type B_{n} \\ {e_{i} \pm e_{j} : 1 \leq i < j \leq n}, & for W of type D_{n} \end{matrix}

be the set of positive roots. In what follows we use the notation of [7,Section3] (and [2,Section2] ) to represent elements of

W

as certain permutations of the set

{1, 2, . . ., n, - 1, - 2, . . ., - n}

, so that

((i_{1}, i_{2}, . . ., i_{k}))

stands for the product of cycles

(i_{1}, i_{2}, . . ., i_{k}) (- i_{1}, - i_{2}, . . ., - i_{k})

and

[i_{1}, i_{2}, . . ., i_{k}]

for the ballanced cycle

(i_{1}, i_{2}, . . ., i_{k}, - i_{1}, - i_{2}, . . ., - i_{k})

. If

γ = {\begin{matrix} [1, 2, . . ., n], & for W of type B_{n} \\ [1, 2, . . ., n - 1] [n], & for W of type D_{n} \end{matrix}

is chosen as the Coxeter element of

W

then there is a canonical isomorphism of

N C_{W} (γ)

with Reiner's

B_{n}

analogue [14] of the lattice of noncrossing partitions of

{1, 2, . . ., n}

(see [3,Section4] or [7,Section3] ) if

W

is of type

B_{n}

, and an explicit combinatorial description of

N C_{W} (γ)

in terms of planar noncrossing diagrams [2,Section3] if

W

is of type

D_{n}

. One can check directly that in the case of type

B_{n}

any total ordering on the set of signed transpositions

((i, j))

and

((i, - j))

for

1 \leq i < j \leq n

and

[i] = (i, - i)

for

1 \leq i \leq n

for which

$((i, j)) < ((i, k)) < ((j, k))$	for $1 \leq i < j < k \leq n$
$((i, j)) < ((i, - k)) < ((j, - k))$	for $1 \leq i < j \leq n$ and $1 \leq k < i$ or $j < k \leq n$
$((i, j)) < [i] < ((i, - j)) < [j]$	for $1 \leq i < j \leq n$ ,

such as the ordering

((1, 2)) < ((1, 3)) < \dots < ((1, n)) < ((2, 3)) < \dots < ((n - 1, n)) <

[1] < ((1, - 2)) < ((1, - 3)) < \dots < ((1, - n)) <

< [2] < ((2, - 3)) < \dots < ((2, - n)) <

\dots < [n - 1] < ((n - 1, - n)) < [n]

induces a reflection ordering for

W

which is compatible with

γ

. Similarly in the case of type

D_{n}

any total ordering on the set of signed transpositions

((i, j))

and

((i, - j))

for

1 \leq i < j \leq n

for which

$((i, j)) < ((i, k)) < ((j, k))$	for $1 \leq i < j < k \leq n$
$((i, j)) < ((i, - k)) < ((j, - k))$	for $1 \leq i < j \leq n - 1$ and $1 \leq k < i$ or $j < k \leq n$
$((i, \pm n)) < ((i, - j)) < ((j, \pm n))$	for $1 \leq i < j \leq n - 1$ ,

such as the ordering

((1, 2)) < ((1, 3)) < \dots < ((1, n - 1)) < ((2, 3)) < \dots < ((n - 2, n - 1)) <

((1, n)) < ((1, - n)) < ((1, - 2)) < ((1, - 3)) < \dots < ((1, - (n - 1))) <

((2, n)) < ((2, - n)) < ((2, - 3)) < \dots < ((2, - (n - 1))) <

\dots < ((n - 1, n)) < ((n - 1, - n))

induces a reflection ordering for

W

which is compatible with

γ

. □

Let

γ

be a Coxeter element of

W

. Any covering relation in

N C_{W} (γ)

is of the form

(u, v)

with

u^{- 1} v \in T

. Setting

λ (u, v) = u^{- 1} v

for any such covering relation defines an edge labeling

λ

N C_{W} (γ)

with label set

T

which we call the natural edge labeling of

N C_{W} (γ)

. Part (ii) of the following theorem is the main result of this section.

Theorem 3.5. Let

W

be a finite real reflection group with set of reflections

T

and Coxeter element

γ

and let

λ

be the natural edge labeling of

N C_{W} (γ)

(i) For any total ordering of $T$ and any non-singleton interval $[u, v]$ in $N C_{W} (γ)$ there is a unique lexicographically smallest maximal chain in $[u, v]$ and this chain is rising with respect to $λ$ .
(ii) If $T$ is totally ordered by a reflection ordering which is compatible with $γ$ and $W$ is a Weyl group then $λ$ is an EL-labeling.

We first need to establish a few lemmas. For any interval

[u, v]

N C_{W} (γ)

we denote by

λ ([u, v])

the set of natural labels of all maximal chains in

[u, v]

, with the convention that

λ ([u, v]) = {\emptyset}

u = v

, and abbreviate

λ ([1, w])

λ (w)

Lemma 3.6. Let

[u, v]

be a non-singleton interval in

N C_{W} (γ)

(i) If $[u, v]$ has length two and $(s, t) \in λ ([u, v])$ then $(t, s^{'}) \in λ ([u, v])$ for some $s^{'} \in T$ .
(ii) It $t \in T$ appears in some coordinate of an element of $λ ([u, v])$ then $t = λ (u, u^{'})$ for some covering relation $(u, u^{'})$ in $[u, v]$ .
(iii) The reflections appearing as the coordinates of an element of $λ ([u, v])$ are pairwise distinct.

Proof. Part (i) is clear since $T$ is closed under conjugation, so that $s^{'} = t s t$ is also an element of $T$ . Parts (ii) and (iii) follow from repeated application of part (i). □

Lemma 3.7. Let

[u, v]

be a non-singleton interval in

N C_{W} (γ)

and let

w = u^{- 1} v

. There is a poset isomorphism

f : [1, w] \to [u, v]

such that

λ (x, y) = λ (f (x), f (y))

for all covering relations

(x, y)

[1, w]

Proof. It follows immediately from the definitions that the map $f : [1, w] \to [u, v]$ with $f (x) = u x$ for $x \in [1, w]$ is well defined and has the desired properties. □

Recall that a parabolic Coxeter element in

W

is a Coxeter element

w

in a parabolic subgroup of

W

, meaning a subgroup generated by a subset of a set of Coxeter generators of

W

. This subgroup, denoted

W_{w}

, depends only on

w

and contains all reflections

t ≼ w

(see [3,Corollary1.6.2] ).

Lemma 3.8. ([3,Lemma1.4.3] ) Let

w \in W

. There exists a Coxeter element

γ

W

with

w ≼ γ

if and only if

w

is a parabolic Coxeter element. □

Lemma 3.9. If

w ≼ γ

for some Coxeter element

γ

W

then any reflection ordering for

W

which is compatible with

γ

restricts to a reflection ordering for

W_{w}

which is compatible with

w

Proof. We may assume that $w$ has rank at least two in $N C_{W} (γ)$ . Let $Φ_{w} \subseteq Φ$ be the root system corresponding to $W_{w}$ . We first check that if $Φ_{w}^{'}$ is an induced rank 2 subsystem of $Φ_{w}$ and $Φ^{'} = R Φ_{w}^{'} \cap Φ$ is the corresponding induced rank 2 subsystem of $Φ$ then $Φ_{w}^{'} = Φ^{'}$ . Clearly $Φ_{w}^{'} \subseteq Φ^{'}$ . Let $α$ and $β$ be the two simple roots of $Φ_{w}^{'}$ and let $α^{'} \in Φ^{'}$ . To show that $α^{'} \in Φ_{w}^{'}$ note that $H_{α} \cap H_{β} \subset H_{α^{'}}$ and hence $F (w) \subset H_{α^{'}}$ . It follows from Lemma 2.4 (ii) that $t_{α^{'}} ≼ w$ and hence that $t_{α^{'}} \in W_{w}$ , in other words that $α^{'} \in Φ_{w}^{'}$ . To conclude the proof suppose that $Φ_{w}^{'}$ is irreducible and that $t_{α} t_{β} ≼ w$ . From $w ≼ γ$ we conclude that $t_{α} t_{β} ≼ γ$ . Since $Φ_{w}^{'} = Φ^{'}$ and the reflection ordering on $T$ is compatible with $γ$ , $t_{α}$ must preceed $t_{β}$ in this ordering. □

Recall also from [3,Section1.5] that the Artin group

ℬ_{ℓ}

of type

A_{ℓ - 1}

acts on the set of shortest factorizations of

γ

into reflections or, equivalently, on the set

λ (γ)

More precisely, the

i

th generator of

ℬ_{ℓ}

acts on

(t_{1}, t_{2}, . . ., t_{ℓ}) \in λ (γ)

by replacing the pair

(t_{i}, t_{i + 1})

(t_{i} t_{i + 1} t_{i}, t_{i})

while leaving other coordinates of

λ (γ)

fixed.

Lemma 3.10. The action of

ℬ_{ℓ}

on the set of shortest factorizations of

γ

into reflections is transitive.

Proof. See Proposition 1.6.1 in [3] . □

Lemma 3.11. Let

t_{α_{1}} t_{α_{2}} \dots t_{α_{ℓ}}

be a shortest factorization of a Coxeter element of

W

into reflections.

(i) ${α_{1}, α_{2}, . . ., α_{ℓ}}$ is a linear basis of $V$ .
(ii) If $W$ is a Weyl group then ${α_{1}, α_{2}, . . ., α_{ℓ}}$ is a $Z$ -basis of the root lattice $Q_{Φ}$ .

Proof. Part (i) is follows from the fact that Coxeter elements have trivial fixed space in $V$ . The conclusion of part (ii) is clear for a shortest factorization of the Coxeter element into simple reflections. In view of Lemma 3.10 it suffices to show that if two shortest factorizations $t_{α_{1}} t_{α_{2}} \dots t_{α_{ℓ}}$ and $t_{β_{1}} t_{β_{2}} \dots t_{β_{ℓ}}$ are related by the action of a single generator of the Artin group $ℬ_{ℓ}$ then ${α_{1}, α_{2}, . . ., α_{ℓ}}$ is a $Z$ -basis of $Q_{Φ}$ if and only if the same is true for ${β_{1}, β_{2}, . . ., β_{ℓ}}$ . We may thus assume that there exists an index $1 \leq i < ℓ$ such that $α_{j} = β_{j}$ for $j \neq i, i + 1$ , $β_{i + 1} = α_{i}$ and $t_{β_{i}} = t_{α_{i}} t_{α_{i + 1}} t_{α_{i}}$ . The last equality implies that $\pm β_{i} = t_{α_{i}} (α_{i + 1}) = α_{i + 1} - \frac{2 (α_{i}, α_{i + 1})}{(α_{i}, α_{i})} α_{i}$ and the claim follows since $2 (α_{i}, α_{i + 1}) / (α_{i}, α_{i}) \in Z$ . □

Proof of Theorem 3.5 . In what follows we will write

N C_{W}

instead of

N C_{W} (γ)

(i) We proceed by induction on the length of the interval

[u, v]

, the claim being trivial if this is equal to one. Clearly all covering relations of the form

(u, u^{'})

[u, v]

have distinct labels. Let

(u, u t)

be the one with the smallest label

t

. In view of the induction hypothesis applied to the interval

[u t, v]

it suffices to prove that all covering relations in

[u t, v]

have labels greater than

t

. This follows from parts (ii) and (iii) of Lemma 3.6 which imply that any such label is different from

t

and equal to the label of a covering relation

(u, u^{'})

[u, v]

(ii) Let

<_{γ}

be the reflection ordering of

T

which is compatible with the Coxeter element

γ

W

. In view of part (i) it remains to show that there is at most one rising maximal chain in a non-singleton interval

[u, v]

with respect to

λ

. In view of Lemma 3.7 it suffices to prove this for an interval of the form

[1, w]

N C_{W}

Since

w ≼ γ

, by Lemma 3.8

w

is a parabolic Coxeter element in

W

. By Lemma 3.9 the restriction of

<_{γ}

on the set of reflections of the parabolic subgroup

W_{w}

is a reflection ordering which is compatible with

w

. Hence we may as well assume that

w = γ

, so that

[1, w]

is the entire poset

N C_{W} = N C_{W} (γ)

. Clearly there is at most one rising maximal chain in

N C_{W}

whose label is a permutation of the set

S

of simple reflections. Hence it suffices to show that a maximal chain

c

N C_{W}

whose label

λ (c)

is not a permutation of

S

cannot be rising. Indeed, let

c

be such a maximal chain and let

λ (c) = (t_{α_{1}}, t_{α_{2}}, . . ., t_{α_{ℓ}})

. By Lemmas 2.2 and 3.11 (ii) there exist indices

i < j

such that

α_{i} - α_{j} \in Φ

. By repeated application of Lemma 3.6 (i) it follows that

t_{α_{i}} t_{α_{j}} ≼ γ

. From

α_{i} - α_{j} \in Φ

we conclude that

{α_{i}, α_{j}}

cannot be the simple system in the rank two induced subsystem of

Φ

spanned by

α_{i}

and

α_{j}

Since

<_{γ}

is compatible with

γ

, Example 3.2 shows that

t_{α_{i}} >_{γ} t_{α_{j}}

which implies that

c

is not rising. □

Corollary 3.12. If

W

has type

A_{n - 1}, B_{n}

D_{n}

then the natural edge labeling of

N C_{W} (γ)

is an EL-labeling under the choices of Coxeter element and total ordering on

T

described in Examples 3.3 and 3.4 . □

4 Proof of Theorem 1.1

Let

W

be any finite real reflection group of rank

ℓ

with set of reflections

T

, root system

Φ

and fixed choice of a positive system

Φ^{+}

. Let

{σ_{1}, σ_{2}, . . ., σ_{ℓ}}

be a choice of simple system for

Φ

such that

{σ_{1}, . . ., σ_{r}}

and

{σ_{r + 1}, . . ., σ_{ℓ}}

are orthonormal sets for some

r

[9,Section3.17] [18] . It is proved in [18] (under the additional assumption that

W

is irreducible, which is acually not needed here) that

Φ^{+} = {ρ_{1}, ρ_{2}, . . ., ρ_{ℓ h / 2}}

, where

ρ_{i} = t_{σ_{1}} t_{σ_{2}} \dots t_{σ_{i - 1}} (σ_{i})

for

1 \leq i \leq ℓ h / 2

and the

σ_{j}

are indexed cyclically modulo

ℓ

. Consider the total ordering

\begin{matrix} t_{ρ_{1}} < t_{ρ_{2}} < \dots < t_{ρ_{ℓ h / 2}} \end{matrix}

(1)

T

. The next statement follows from Theorem 5.4 in [8] .

Theorem 4.1. ([8] ) The total ordering ( 1 ) of

T

is a reflection ordering for

W

which is compatible with the Coxeter element

γ = t_{σ_{1}} t_{σ_{2}} \dots t_{σ_{ℓ}}

The previous theorem establishes the existence of a reflection ordering which is compatible with some Coxeter element for any

W

. Combined with Theorem 3.5 (ii) it gives a case-free proof of the statement in Theorem 1.1 in the case of Weyl groups. Using other results from [8] we can give a different case-free proof that the ordering ( 1 ) yields an EL-shelling of

N C_{W} (γ)

for any

W

as follows.

Theorem 4.2. If

T

is totally ordered by ( 1 ) and

γ = t_{σ_{1}} t_{σ_{2}} \dots t_{σ_{ℓ}}

then the natural edge labeling of

N C_{W} (γ)

with label set

T

is an EL-labeling.

Proof. We claim that there is at most one rising maximal chain with respect to the natural edge labeling

λ

in any non-singleton interval

[u, v]

N C_{W} (γ)

. In view of part (i) of Theorem 3.5 it suffices to prove this claim. As in the proof of part (ii) of the same result, it suffices to treat the intervals of the form

[1, w]

Let

(t_{1}, t_{2}, . . ., t_{k})

be the label of a rising maximal chain in

[1, w]

and let

t_{i} = t_{τ_{i}}

for

1 \leq i \leq k

, where

τ_{i} \in Φ^{+}

. We will prove that

{τ_{1}, τ_{2}, . . ., τ_{k}}

is the set of simple roots of the subsystem

Φ_{w} \subseteq Φ

corresponding to the parabolic subgroup

W_{w}

(see Lemma 3.9 ) with respect to the positive system

Φ_{w} \cap Φ^{+}

. This clearly implies the claim. Let

τ

be the largest positive root in

Φ_{w}

with respect to ( 1 ). By part (i) of Lemma 3.11 and Lemma 3.8 the set

{τ_{1}, τ_{2}, . . ., τ_{k}}

is a basis of the real vector space spanned by

Φ_{w}

. Hence there is a unique expression of the form

\begin{matrix} τ = a_{1} τ_{1} + a_{2} τ_{2} + \dots + a_{k} τ_{k} \end{matrix}

(2)

with

a_{i} \in R

for all

i

. As in [8,Lemma3.9] let

μ (x) = - 2 (γ - I)^{- 1} x

, where

I

is the identity map. For notational convenience we write

x \cdot y

instead of

(x, y)

. From

γ = t_{1} t_{2} \dots t_{k}

and part (ii) of this lemma we have

μ (τ_{i}) \cdot τ_{j} = 0

for

i < j

. Moreover [8,Theorem3.7] implies that

μ (τ_{j}) \cdot τ_{i} \leq 0

for

i < j

and that

μ (τ_{i}) \cdot τ_{i} = 1

and

μ (τ_{i}) \cdot τ \geq 0

for all

i

. Taking the inner product of ( 2 ) with

μ (τ_{i})

we get

\begin{matrix} 0 & \leq & μ (τ_{i}) \cdot τ \end{matrix}

\begin{matrix} = & a_{1} μ (τ_{i}) \cdot τ_{1} + \dots + a_{i - 1} μ (τ_{i}) \cdot τ_{i - 1} + a_{i} . \end{matrix}

It follows by induction that

a_{i} \geq 0

for all

1 \leq i \leq k

. Thus

τ

is in the positive cone of

{τ_{1}, τ_{2}, . . ., τ_{k}}

. Corollary 3.8 in [8] gives

τ_{k} = τ

. By induction on the length of

w

we may assume that

{τ_{1}, τ_{2}, . . ., τ_{k - 1}}

is the simple system in

Φ_{w t_{k}} \cap Φ^{+}

. Theorem 5.1 in [8] implies that

{τ_{1}, τ_{2}, . . ., τ_{k}}

is the simple system of

Φ_{w}

, as desired. □

Proof of Theorem 1.1 . It follows from Theorem 4.2 . □ The next corollary follows from Theorem 4.2 and standard facts on Möbius functions of EL-shellable posets; see [17,Section3.13] . In view of Theorem 3.5 (ii) it applies to any Coxeter element and compatible reflection ordering in the case of Weyl groups.

Corollary 4.3. If

T

is totally ordered by ( 1 ) then the Möbius function on any interval

[u, v]

N C_{W} (γ)

is equal to

(- 1)^{l_{T} (v) - l_{T} (u)}

times the number of falling maximal chains in

[u, v]

with respect to the natural edge labeling of

N C_{W} (γ)

. □

In particular the Möbius number of

N C_{W} (γ)

is equal to

(- 1)^{ℓ}

times the number of falling maximal chains in

N C_{W} (γ)

with respect to this labeling. It can be deduced from the results of [8,Section8] that this number of falling chains is equal to the number of positive clusters of the generalized associahedron of corresponding type.

Acknowledgements. The first two authors thank Jon McCammond, Alexandru Nica and Victor Reiner for their invitation to the AIM workshop Braid groups, Clusters and Free Probability in January 2005, in which some of the present work was done, the Institute Mittag-Leffler (Stockholm) and the Centre de Recerca Matemàtica (Barcelona), respectively, where this work was completed and Hugh Thomas for interesting discussions. The hospitality, financial support and excellent working conditions offered by the above mentioned institutions are gratefully acknowledged.

References

C.A. Athanasiadis, On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Amer. Math. Soc. 357 (2005), 179–196.
C.A. Athanasiadis and V. Reiner, Noncrossing partitions for the group $D_{n}$ , SIAM J. Discrete Math. 18 (2004), 397–417.
D. Bessis, The dual braid monoid, Ann. Sci. Ecole Norm. Sup. 36 (2003), 647–683.
A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159–183.
A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, Springer-Verlag (to appear).
T. Brady, A partial order on the symmetric group and new K( $π$ , 1)'s for the braid groups, Adv. Math. 161 (2001), 20–40.
T. Brady and C. Watt, K( $π$ , 1)'s for Artin groups of finite type, in Proceedings of the Conference on Geometric and Combinatorial group theory, Part I (Haifa 2000), Geom. Dedicata 94 (2002), 225–250.
T. Brady and C. Watt, Lattices in finite real reflection groups, preprint, 2005, 29 pages (ArXiV preprint math.CO/0501502).
J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics 29, Cambridge University Press, Cambridge, England, 1990.
G. Kreweras, Sur les partitions non-croisées d'un cycle, Discrete Math. 1 (1972), 333–350.
J. McCammond, Noncrossing partitions in surprising locations, preprint, 2003, 14 pages.
J. McCammond, An introduction to Garside structures, preprint, 2004, 28 pages.
D.I. Panyushev, Ad-nilpotent ideals of a Borel subalgebra: generators and duality, J. Algebra 274 (2004), 822–846.
V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195–222.
V. Reiner, personal communication with the first author, 2002.
E. Sommers, $B$ -stable ideals in the nilradical of a Borel subalgebra, Canad. Math. Bull. (to appear).
R.P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge, 1997.
R. Steinberg, Finite reflection groups, Trans. Amer. Math. Soc. 91 (1959), 493–504.

Department of Mathematics, University of Crete, 71409 Heraklion, Crete, Greece E-mail address : caa@math.uoc.gr School of Mathematical Sciences, Dublin City University, Glasnevin, Dublin 9, Ireland E-mail address : tom.brady@dcu.ie School of Mathematics, Dublin Institute of Technology, Dublin 8, Ireland E-mail address : colum.watt@dit.ie

February 28, 2005

Christos A. Athanasiadis, Thomas Brady,

Colum Watt