A total ordering
$<$
of
$T$
is called a reflection ordering for
$W$
[
5,Section5.1]
if whenever
$\alpha ,{\alpha}_{1},{\alpha}_{2}\in {\Phi}^{+}$
are distinct roots and
$\alpha $
is a positive linear combination of
${\alpha}_{1}$
and
${\alpha}_{2}$
we have either
$${t}_{{\alpha}_{1}}<{t}_{\alpha}<{t}_{{\alpha}_{2}}$$
or
$${t}_{{\alpha}_{2}}<{t}_{\alpha}<{t}_{{\alpha}_{1}}.$$
An induced subsystem of
$\Phi $
of rank
$i$
is the intersection
${\Phi}^{\prime}$
of
$\Phi $
with the linear span of
$i$
linearly independent roots in
$\Phi $
. The set
${\Phi}^{\prime}$
is a root system on its own and
${\Phi}^{\prime}\cap {\Phi}^{+}$
is a choice of a positive system for
${\Phi}^{\prime}$
. The following is the main definition in this section.
Definition 3.1.
A reflection ordering
$<$
of
$T$
is compatible with a Coxeter element
$\gamma $
of
$W$
if for any irreducible rank 2 induced subsystem
${\Phi}^{\prime}\subseteq \Phi $
the following holds: if
$\alpha $
and
$\beta $
are the simple roots of
${\Phi}^{\prime}$
with respect to
${\Phi}^{\prime}\cap {\Phi}^{+}$
and
${t}_{\alpha}{t}_{\beta}\in N{C}_{W}\left(\gamma \right)$
then
${t}_{\alpha}<{t}_{\beta}$
.
Observe that a rank 2 subsystem
${\Phi}^{\prime}\subseteq \Phi $
is irreducible if and only if
${\Phi}^{\prime}\cap {\Phi}^{+}$
has at least three roots.
Example 3.2.
Let
$W$
be of rank 2, so that
$W$
is a dihedral group of order
$2m$
for some
$m\ge 2$
. Let
$\alpha $
and
$\beta $
be the two simple roots in
$\Phi $
. There are
$m$
reflections in
$W$
, namely
${t}_{1},{t}_{2},...,{t}_{m}$
where
${t}_{i}={t}_{\alpha}({t}_{\beta}{t}_{\alpha}{)}^{i1}$
(so
${t}_{1}={t}_{\alpha}$
and
${t}_{m}={t}_{\beta}$
) and two reflection orderings, namely
${t}_{1}<{t}_{2}<\cdots <{t}_{m}$
and its reverse. The reflection ordering
$<$
is compatible with the Coxeter element
$\gamma ={t}_{\alpha}{t}_{\beta}$
. The poset
$N{C}_{W}\left(\gamma \right)$
has
$m$
maximal chains corresponding to the
$m$
shortest factorizations
$\gamma ={t}_{1}{t}_{m}={t}_{2}{t}_{1}=\cdots ={t}_{m}{t}_{m1}$
of
$\gamma $
into reflections. Clearly the chain corresponding to the factorization
$\gamma ={t}_{1}{t}_{m}$
is the unique rising maximal chain and the lexicographically smallest maximal chain in the edge labeling of
$N{C}_{W}\left(\gamma \right)$
which assigns the label
$({t}_{i},{t}_{j})$
to the chain corresponding to a factorization
$\gamma ={t}_{i}{t}_{j}$
, when the label set
$T$
is totally ordered by
$<$
. □
Example 3.3.
Let
$W$
be of type
${A}_{n1}$
and
${\Phi}^{+}=\{{e}_{i}{e}_{j}:1\le i<j\le 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\le i<j\le n$
. If the
$n$
cycle
$\gamma =(1,2,...,n)$
is chosen as the Coxeter element for
$W$
then there is a canonical isomorphism of
$N{C}_{W}\left(\gamma \right)$
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\le i<j\le n$
, for which
$$(i,j)<(i,k)<(j,k)$$
for
$1\le i<j<k\le n$
(such as the lexicographic ordering) induces a reflection ordering for
$W$
which is compatible with
$\gamma $
. □
Example 3.4.
Let
$W$
be of type
${B}_{n}$
or
${D}_{n}$
and
${\Phi}^{+}=\{\begin{array}{cc}\{{e}_{i}:1\le i\le n\}\cup \{{e}_{i}\pm {e}_{j}:1\le i<j\le n\},& \text{for}W\text{of type}{B}_{n}\text{}\\ \{{e}_{i}\pm {e}_{j}:1\le i<j\le n\},& \text{for}W\text{of type}{D}_{n}\text{}\end{array}$
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
$\left(\right({i}_{1},{i}_{2},...,{i}_{k}\left)\right)$
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
$\gamma =\{\begin{array}{cc}[1,2,...,n],& \text{for}W\text{of type}{B}_{n}\text{}\\ [1,2,...,n1]\left[n\right],& \text{for}W\text{of type}{D}_{n}\text{}\end{array}$
is chosen as the Coxeter element of
$W$
then there is a canonical isomorphism of
$N{C}_{W}\left(\gamma \right)$
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}\left(\gamma \right)$
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
$\left(\right(i,j\left)\right)$
and
$\left(\right(i,j\left)\right)$
for
$1\le i<j\le n$
and
$\left[i\right]=(i,i)$
for
$1\le i\le n$
for which
$\left(\right(i,j\left)\right)<\left(\right(i,k\left)\right)<\left(\right(j,k\left)\right)$

for
$1\le i<j<k\le n$

$\left(\right(i,j\left)\right)<\left(\right(i,k\left)\right)<\left(\right(j,k\left)\right)$

for
$1\le i<j\le n$
and
$1\le k<i$
or
$j<k\le n$

$\left(\right(i,j\left)\right)<\left[i\right]<\left(\right(i,j\left)\right)<\left[j\right]$

for
$1\le i<j\le n$
,

such as the ordering
$\left(\right(1,2\left)\right)<\left(\right(1,3\left)\right)<\cdots <\left(\right(1,n\left)\right)<\left(\right(2,3\left)\right)<\cdots <\left(\right(n1,n\left)\right)<$

$\left[1\right]<\left(\right(1,2\left)\right)<\left(\right(1,3\left)\right)<\cdots <\left(\right(1,n\left)\right)<$

$<\left[2\right]<\left(\right(2,3\left)\right)<\cdots <\left(\right(2,n\left)\right)<$

$\cdots <[n1]<\left(\right(n1,n\left)\right)<\left[n\right]$
,

induces a reflection ordering for
$W$
which is compatible with
$\gamma $
. Similarly in the case of type
${D}_{n}$
any total ordering on the set of signed transpositions
$\left(\right(i,j\left)\right)$
and
$\left(\right(i,j\left)\right)$
for
$1\le i<j\le n$
for which
$\left(\right(i,j\left)\right)<\left(\right(i,k\left)\right)<\left(\right(j,k\left)\right)$

for
$1\le i<j<k\le n$

$\left(\right(i,j\left)\right)<\left(\right(i,k\left)\right)<\left(\right(j,k\left)\right)$

for
$1\le i<j\le n1$
and
$1\le k<i$
or
$j<k\le n$

$\left(\right(i,\pm n\left)\right)<\left(\right(i,j\left)\right)<\left(\right(j,\pm n\left)\right)$

for
$1\le i<j\le n1$
,

such as the ordering
$\left(\right(1,2\left)\right)<\left(\right(1,3\left)\right)<\cdots <\left(\right(1,n1\left)\right)<\left(\right(2,3\left)\right)<\cdots <\left(\right(n2,n1\left)\right)<$

$\left(\right(1,n\left)\right)<\left(\right(1,n\left)\right)<\left(\right(1,2\left)\right)<\left(\right(1,3\left)\right)<\cdots <\left(\right(1,(n1)\left)\right)<$

$\left(\right(2,n\left)\right)<\left(\right(2,n\left)\right)<\left(\right(2,3\left)\right)<\cdots <\left(\right(2,(n1)\left)\right)<$

$\cdots <\left(\right(n1,n\left)\right)<\left(\right(n1,n\left)\right)$
,

induces a reflection ordering for
$W$
which is compatible with
$\gamma $
. □
Let
$\gamma $
be a Coxeter element of
$W$
. Any covering relation in
$N{C}_{W}\left(\gamma \right)$
is of the form
$(u,v)$
with
${u}^{1}v\in T$
. Setting
$\lambda (u,v)={u}^{1}v$
for any such covering relation defines an edge labeling
$\lambda $
of
$N{C}_{W}\left(\gamma \right)$
with label set
$T$
which we call the natural edge labeling of
$N{C}_{W}\left(\gamma \right)$
. 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
$\gamma $
and let
$\lambda $
be the natural edge labeling of
$N{C}_{W}\left(\gamma \right)$
.

(i)
For any total ordering of
$T$
and any nonsingleton interval
$[u,v]$
in
$N{C}_{W}\left(\gamma \right)$
there is a unique lexicographically smallest maximal chain in
$[u,v]$
and this chain is rising with respect to
$\lambda $
.

(ii)
If
$T$
is totally ordered by a reflection ordering which is compatible with
$\gamma $
and
$W$
is a Weyl group then
$\lambda $
is an ELlabeling.
We first need to establish a few lemmas. For any interval
$[u,v]$
in
$N{C}_{W}\left(\gamma \right)$
we denote by
$\lambda \left(\right[u,v\left]\right)$
the set of natural labels of all maximal chains in
$[u,v]$
, with the convention that
$\lambda \left(\right[u,v\left]\right)=\{\varnothing \}$
if
$u=v$
, and abbreviate
$\lambda \left(\right[1,w\left]\right)$
as
$\lambda \left(w\right)$
.
Lemma 3.6.
Let
$[u,v]$
be a nonsingleton interval in
$N{C}_{W}\left(\gamma \right)$
.

(i)
If
$[u,v]$
has length two and
$(s,t)\in \lambda \left(\right[u,v\left]\right)$
then
$(t,{s}^{\prime})\in \lambda \left(\right[u,v\left]\right)$
for some
${s}^{\prime}\in T$
.

(ii)
It
$t\in T$
appears in some coordinate of an element of
$\lambda \left(\right[u,v\left]\right)$
then
$t=\lambda (u,{u}^{\prime})$
for some covering relation
$(u,{u}^{\prime})$
in
$[u,v]$
.

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

Proof.
Part (i) is clear since
$T$
is closed under conjugation, so that
${s}^{\prime}=tst$
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 nonsingleton interval in
$N{C}_{W}\left(\gamma \right)$
and let
$w={u}^{1}v$
. There is a poset isomorphism
$f:[1,w]\to [u,v]$
such that
$\lambda (x,y)=\lambda \left(f\right(x),f(y\left)\right)$
for all covering relations
$(x,y)$
in
$[1,w]$
.

Proof.
It follows immediately from the definitions that the map
$f:[1,w]\to [u,v]$
with
$f\left(x\right)=ux$
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\preccurlyeq w$
(see [
3,Corollary1.6.2]
).
Lemma 3.8.
([
3,Lemma1.4.3]
) Let
$w\in W$
. There exists a Coxeter element
$\gamma $
of
$W$
with
$w\preccurlyeq \gamma $
if and only if
$w$
is a parabolic Coxeter element. □
Lemma 3.9.
If
$w\preccurlyeq \gamma $
for some Coxeter element
$\gamma $
of
$W$
then any reflection ordering for
$W$
which is compatible with
$\gamma $
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}\left(\gamma \right)$
. Let
${\Phi}_{w}\subseteq \Phi $
be the root system corresponding to
${W}_{w}$
. We first check that if
${\Phi}_{w}^{\prime}$
is an induced rank 2 subsystem of
${\Phi}_{w}$
and
${\Phi}^{\prime}=\mathbb{R}{\Phi}_{w}^{\prime}\cap \Phi $
is the corresponding induced rank 2 subsystem of
$\Phi $
then
${\Phi}_{w}^{\prime}={\Phi}^{\prime}$
. Clearly
${\Phi}_{w}^{\prime}\subseteq {\Phi}^{\prime}$
. Let
$\alpha $
and
$\beta $
be the two simple roots of
${\Phi}_{w}^{\prime}$
and let
${\alpha}^{\prime}\in {\Phi}^{\prime}$
. To show that
${\alpha}^{\prime}\in {\Phi}_{w}^{\prime}$
note that
${H}_{\alpha}\cap {H}_{\beta}\subset {H}_{{\alpha}^{\prime}}$
and hence
$F\left(w\right)\subset {H}_{{\alpha}^{\prime}}$
. It follows from Lemma 2.4 (ii) that
${t}_{{\alpha}^{\prime}}\preccurlyeq w$
and hence that
${t}_{{\alpha}^{\prime}}\in {W}_{w}$
, in other words that
${\alpha}^{\prime}\in {\Phi}_{w}^{\prime}$
. To conclude the proof suppose that
${\Phi}_{w}^{\prime}$
is irreducible and that
${t}_{\alpha}{t}_{\beta}\preccurlyeq w$
. From
$w\preccurlyeq \gamma $
we conclude that
${t}_{\alpha}{t}_{\beta}\preccurlyeq \gamma $
. Since
${\Phi}_{w}^{\prime}={\Phi}^{\prime}$
and the reflection ordering on
$T$
is compatible with
$\gamma $
,
${t}_{\alpha}$
must preceed
${t}_{\beta}$
in this ordering. □
Recall also from [
3,Section1.5]
that the Artin group
${\mathcal{\mathcal{B}}}_{\ell}$
of type
${A}_{\ell 1}$
acts on the set of shortest factorizations of
$\gamma $
into reflections or, equivalently, on the set
$\lambda \left(\gamma \right)$
.
More precisely, the
$i$
th generator of
${\mathcal{\mathcal{B}}}_{\ell}$
acts on
$({t}_{1},{t}_{2},...,{t}_{\ell})\in \lambda \left(\gamma \right)$
by replacing the pair
$({t}_{i},{t}_{i+1})$
by
$({t}_{i}{t}_{i+1}{t}_{i},{t}_{i})$
while leaving other coordinates of
$\lambda \left(\gamma \right)$
fixed.
Lemma 3.10.
The action of
${\mathcal{\mathcal{B}}}_{\ell}$
on the set of shortest factorizations of
$\gamma $
into reflections is transitive.

Proof.
See Proposition 1.6.1 in [3] . □
Lemma 3.11.
Let
${t}_{{\alpha}_{1}}{t}_{{\alpha}_{2}}\cdots {t}_{{\alpha}_{\ell}}$
be a shortest factorization of a Coxeter element of
$W$
into reflections.

(i)
$\{{\alpha}_{1},{\alpha}_{2},...,{\alpha}_{\ell}\}$
is a linear basis of
$V$
.

(ii)
If
$W$
is a Weyl group then
$\{{\alpha}_{1},{\alpha}_{2},...,{\alpha}_{\ell}\}$
is a
$\mathbb{Z}$
basis of the root lattice
${Q}_{\Phi}$
.

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}_{{\alpha}_{1}}{t}_{{\alpha}_{2}}\cdots {t}_{{\alpha}_{\ell}}$
and
${t}_{{\beta}_{1}}{t}_{{\beta}_{2}}\cdots {t}_{{\beta}_{\ell}}$
are related by the action of a single generator of the Artin group
${\mathcal{\mathcal{B}}}_{\ell}$
then
$\{{\alpha}_{1},{\alpha}_{2},...,{\alpha}_{\ell}\}$
is a
$\mathbb{Z}$
basis of
${Q}_{\Phi}$
if and only if the same is true for
$\{{\beta}_{1},{\beta}_{2},...,{\beta}_{\ell}\}$
. We may thus assume that there exists an index
$1\le i<\ell $
such that
${\alpha}_{j}={\beta}_{j}$
for
$j\ne i,i+1$
,
${\beta}_{i+1}={\alpha}_{i}$
and
${t}_{{\beta}_{i}}={t}_{{\alpha}_{i}}{t}_{{\alpha}_{i+1}}{t}_{{\alpha}_{i}}$
. The last equality implies that
$$\pm {\beta}_{i}={t}_{{\alpha}_{i}}\left({\alpha}_{i+1}\right)={\alpha}_{i+1}\frac{2({\alpha}_{i},{\alpha}_{i+1})}{({\alpha}_{i},{\alpha}_{i})}{\alpha}_{i}$$
and the claim follows since
$2({\alpha}_{i},{\alpha}_{i+1})/({\alpha}_{i},{\alpha}_{i})\in \mathbb{Z}$
. □
Proof of Theorem 3.5 . In what follows we will write
$N{C}_{W}$
instead of
$N{C}_{W}\left(\gamma \right)$
.
(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}^{\prime})$
in
$[u,v]$
have distinct labels. Let
$(u,ut)$
be the one with the smallest label
$t$
. In view of the induction hypothesis applied to the interval
$[ut,v]$
it suffices to prove that all covering relations in
$[ut,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}^{\prime})$
in
$[u,v]$
.
(ii) Let
${<}_{\gamma}$
be the reflection ordering of
$T$
which is compatible with the Coxeter element
$\gamma $
of
$W$
. In view of part (i) it remains to show that there is at most one rising maximal chain in a nonsingleton interval
$[u,v]$
with respect to
$\lambda $
. In view of Lemma 3.7 it suffices to prove this for an interval of the form
$[1,w]$
in
$N{C}_{W}$
.
Since
$w\preccurlyeq \gamma $
, by Lemma 3.8
$w$
is a parabolic Coxeter element in
$W$
. By Lemma 3.9 the restriction of
${<}_{\gamma}$
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=\gamma $
, so that
$[1,w]$
is the entire poset
$N{C}_{W}=N{C}_{W}\left(\gamma \right)$
. 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$
in
$N{C}_{W}$
whose label
$\lambda \left(c\right)$
is not a permutation of
$S$
cannot be rising. Indeed, let
$c$
be such a maximal chain and let
$\lambda \left(c\right)=({t}_{{\alpha}_{1}},{t}_{{\alpha}_{2}},...,{t}_{{\alpha}_{\ell}})$
. By Lemmas 2.2 and 3.11 (ii) there exist indices
$i<j$
such that
${\alpha}_{i}{\alpha}_{j}\in \Phi $
. By repeated application of Lemma 3.6 (i) it follows that
${t}_{{\alpha}_{i}}{t}_{{\alpha}_{j}}\preccurlyeq \gamma $
. From
${\alpha}_{i}{\alpha}_{j}\in \Phi $
we conclude that
$\{{\alpha}_{i},{\alpha}_{j}\}$
cannot be the simple system in the rank two induced subsystem of
$\Phi $
spanned by
${\alpha}_{i}$
and
${\alpha}_{j}$
.
Since
${<}_{\gamma}$
is compatible with
$\gamma $
, Example 3.2 shows that
${t}_{{\alpha}_{i}}{>}_{\gamma}{t}_{{\alpha}_{j}}$
which implies that
$c$
is not rising. □
Corollary 3.12.
If
$W$
has type
${A}_{n1},{B}_{n}$
or
${D}_{n}$
then the natural edge labeling of
$N{C}_{W}\left(\gamma \right)$
is an ELlabeling 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
$\ell $
with set of reflections
$T$
, root system
$\Phi $
and fixed choice of a positive system
${\Phi}^{+}$
. Let
$\{{\sigma}_{1},{\sigma}_{2},...,{\sigma}_{\ell}\}$
be a choice of simple system for
$\Phi $
such that
$\{{\sigma}_{1},...,{\sigma}_{r}\}$
and
$\{{\sigma}_{r+1},...,{\sigma}_{\ell}\}$
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
${\Phi}^{+}=\{{\rho}_{1},{\rho}_{2},...,{\rho}_{\ell h/2}\}$
, where
${\rho}_{i}={t}_{{\sigma}_{1}}{t}_{{\sigma}_{2}}\cdots {t}_{{\sigma}_{i1}}\left({\sigma}_{i}\right)$
for
$1\le i\le \ell h/2$
and the
${\sigma}_{j}$
are indexed cyclically modulo
$\ell $
. Consider the total ordering
$$\begin{array}{c}{t}_{{\rho}_{1}}<{t}_{{\rho}_{2}}<\cdots <{t}_{{\rho}_{\ell h/2}}\end{array}$$ 
(1)

of
$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
$\gamma ={t}_{{\sigma}_{1}}{t}_{{\sigma}_{2}}\cdots {t}_{{\sigma}_{\ell}}$
.
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 casefree proof of the statement in Theorem 1.1 in the case of Weyl groups. Using other results from [
8]
we can give a different casefree proof that the ordering ( 1 ) yields an ELshelling of
$N{C}_{W}\left(\gamma \right)$
for any
$W$
as follows.
Theorem 4.2.
If
$T$
is totally ordered by ( 1 ) and
$\gamma ={t}_{{\sigma}_{1}}{t}_{{\sigma}_{2}}\cdots {t}_{{\sigma}_{\ell}}$
then the natural edge labeling of
$N{C}_{W}\left(\gamma \right)$
with label set
$T$
is an ELlabeling.

Proof.
We claim that there is at most one rising maximal chain with respect to the natural edge labeling
$\lambda $
in any nonsingleton interval
$[u,v]$
in
$N{C}_{W}\left(\gamma \right)$
. 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}_{{\tau}_{i}}$
for
$1\le i\le k$
, where
${\tau}_{i}\in {\Phi}^{+}$
. We will prove that
$\{{\tau}_{1},{\tau}_{2},...,{\tau}_{k}\}$
is the set of simple roots of the subsystem
${\Phi}_{w}\subseteq \Phi $
corresponding to the parabolic subgroup
${W}_{w}$
(see Lemma 3.9 ) with respect to the positive system
${\Phi}_{w}\cap {\Phi}^{+}$
. This clearly implies the claim. Let
$\tau $
be the largest positive root in
${\Phi}_{w}$
with respect to ( 1 ). By part (i) of Lemma 3.11 and Lemma 3.8 the set
$\{{\tau}_{1},{\tau}_{2},...,{\tau}_{k}\}$
is a basis of the real vector space spanned by
${\Phi}_{w}$
. Hence there is a unique expression of the form
$$\begin{array}{c}\tau ={a}_{1}{\tau}_{1}+{a}_{2}{\tau}_{2}+\cdots +{a}_{k}{\tau}_{k}\end{array}$$ 
(2)

with
${a}_{i}\in \mathbb{R}$
for all
$i$
. As in [
8,Lemma3.9]
let
$\mu \left(x\right)=2(\gamma I{)}^{1}x$
, where
$I$
is the identity map. For notational convenience we write
$x\cdot y$
instead of
$(x,y)$
. From
$\gamma ={t}_{1}{t}_{2}\cdots {t}_{k}$
and part (ii) of this lemma we have
$\mu \left({\tau}_{i}\right)\cdot {\tau}_{j}=0$
for
$i<j$
. Moreover [
8,Theorem3.7]
implies that
$\mu \left({\tau}_{j}\right)\cdot {\tau}_{i}\le 0$
for
$i<j$
and that
$\mu \left({\tau}_{i}\right)\cdot {\tau}_{i}=1$
and
$\mu \left({\tau}_{i}\right)\cdot \tau \ge 0$
for all
$i$
. Taking the inner product of ( 2 ) with
$\mu \left({\tau}_{i}\right)$
we get
$$\begin{array}{ccc}0& \le & \mu \left({\tau}_{i}\right)\cdot \tau \end{array}$$  
$$\begin{array}{ccc}& =& {a}_{1}\mu \left({\tau}_{i}\right)\cdot {\tau}_{1}+\cdots +{a}_{i1}\mu \left({\tau}_{i}\right)\cdot {\tau}_{i1}+{a}_{i}.\end{array}$$  
It follows by induction that
${a}_{i}\ge 0$
for all
$1\le i\le k$
. Thus
$\tau $
is in the positive cone of
$\{{\tau}_{1},{\tau}_{2},...,{\tau}_{k}\}$
. Corollary 3.8 in [
8]
gives
${\tau}_{k}=\tau $
. By induction on the length of
$w$
we may assume that
$\{{\tau}_{1},{\tau}_{2},...,{\tau}_{k1}\}$
is the simple system in
${\Phi}_{w{t}_{k}}\cap {\Phi}^{+}$
. Theorem 5.1 in [
8]
implies that
$\{{\tau}_{1},{\tau}_{2},...,{\tau}_{k}\}$
is the simple system of
${\Phi}_{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 ELshellable 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]$
in
$N{C}_{W}\left(\gamma \right)$
is equal to
$(1{)}^{{l}_{T}\left(v\right){l}_{T}\left(u\right)}$
times the number of falling maximal chains in
$[u,v]$
with respect to the natural edge labeling of
$N{C}_{W}\left(\gamma \right)$
. □
In particular the Möbius number of
$N{C}_{W}\left(\gamma \right)$
is equal to
$(1{)}^{\ell}$
times the number of falling maximal chains in
$N{C}_{W}\left(\gamma \right)$
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 MittagLeffler (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 CohenMacaulay 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, SpringerVerlag (to appear).

T. Brady, A partial order on the symmetric group and new K(
$\pi $
, 1)'s for the braid groups, Adv. Math. 161 (2001), 20–40.

T. Brady and C. Watt, K(
$\pi $
, 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 noncroisé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, Adnilpotent ideals of a Borel subalgebra: generators and duality, J. Algebra 274 (2004), 822–846.

V. Reiner, Noncrossing 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 Email address : caa@math.uoc.gr School of Mathematical Sciences, Dublin City University, Glasnevin, Dublin 9, Ireland Email address : tom.brady@dcu.ie School of Mathematics, Dublin Institute of Technology, Dublin 8, Ireland Email address : colum.watt@dit.ie