On the Fully Commutative Elements of Coxeter Groups.
Let W be a Coxeter group. We define an element w  W to be fully commutative if any reduced expression for w can be obtained from any other by means of braid relations that only involve commuting generators. We give several combinatorial characterizations of this property, classify the Coxeter groups with finitely many fully commutative elements, and classify the parabolic quotients whose members are all fully commutative. As applications of the latter, we classify all parabolic quotients with the property that (1) the Bruhat ordering is a lattice, (2) the Bruhat ordering is a distributive lattice, (3) the weak ordering is a distributive lattice, and (4) the weak ordering and Bruhat ordering coincide.
Introduction
Let W be an arbitrary Coxeter group. This paper is concerned with the elements
with the property that any reduced word for w can be obtained from any other by using
only the Coxeter relations that involve commuting generators. We say that such elements
are fully commutative.
Our motivation for studying full commutativity arose from some applications we discovered
that involve the symmetric functions associated with the Weyl groups of type B
and D studied by Billey and Haiman [BH], Fomin and Kirillov [FK], and T. K. Lam [L].
(These applications are discussed in [Ste].) A second (related) motivation arose from the
interesting combinatorial properties of full commutativity in the symmetric group case.
For example (quoting [BJS]), the fully commutative members of Sn are the permutations
w that avoid the pattern 321 (in one-line notation). The number of these is the Catalan
number Cn , and there is a skew Young diagram ' naturally associated to each fully
commutative w with the property that the standard Young tableaux of shape ' are in
one-to-one correspondence with the reduced words for w.
A third motivation, valid in any Coxeter group, is the fact that full commutativity is
equivalent to several other natural combinatorial properties. For example (Theorem 2.2
below), w 2 W is fully commutative if any only if the set of reduced words for w is
order-theoretic, by which we mean that there is a labeled partially ordered set whose
linear extensions are the reduced words for w. Also, one can show (again Theorem 2.2)
that knowledge of the fully commutative elements of W is equivalent to knowledge of the
subintervals of the weak ordering of W that are distributive lattices. (By a theorem of
Bj-orner [Bj], one knows that every subinterval of the weak order is at least a lattice.)
In his recent Ph. D. thesis [F] (see also [F2]), C. K. Fan has independently studied the
fully commutative elements of simply-laced 1 Coxeter groups with an entirely different set
of motivations in mind. Fan proves that the fully commutative elements index a basis
for a quotient of the associated Iwahori-Hecke algebra. In the symmetric group case, this
quotient is the Temperley-Lieb algebra. In the (simply-laced) Weyl group case, Fan gives
the following characterization of full commutativity: If \Phi(w) is the set of positive roots
sent to negative roots by w, then w is fully commutative if and only if the root spaces
indexed by \Phi(w) generate an abelian subalgebra of the associated Lie algebra. Fan also
uses this characterization as the definition for commutative elements of non simply-laced
Weyl groups, but this is not equivalent to full commutativity as we define it.
The outline of the paper is as follows. In Section 2, we prove several characterizations
of full commutativity, including the ones mentioned above. Of central importance is the
Coxeter group is simply-laced if the product of any pair of noncommuting generators has order 3.
"heap" associated to a fully commutative element w-this is a labeled partial order whose
linear extensions are the reduced words for w. In Section 3, we prove that every fully
commutative heap occurs as a convex subset of a heap with unique maximal and minimal
elements; these are the heaps of fully commutative double coset representatives of W
relative to pairs of maximal parabolic subgroups. We also prove (Theorem 3.4) that a
fully commutative element that is maximal with respect to multiplication on the right
has a heap with a "top tree" that amounts to a rooted version of the Coxeter graph.
In particular, there are no such elements unless the Coxeter graph is acyclic. We then
characterize (Theorem 3.5) the rooted trees that arise in this fashion.
In Section 4, we classify the Coxeter groups that are FC-finite (i.e., contain finitely
many fully commutative elements). This generalizes the work in [F], where Fan treats the
simply-laced case. It is interesting to note that the proof we give is self-contained, purely
combinatorial, and close to being a proof of the classification theorem for finite Coxeter
groups. (However, there do exist infinite Coxeter groups that are FC-finite.)
In Section 5, we classify the parabolic quotients of Coxeter groups whose members
are all fully commutative. The result is that aside from a few exceptional cases, the
irreducible quotients with this property arise from orbits of minuscule weights in finite Weyl
groups and Coxeter groups in which every edge of the Coxeter graph has infinite weight.
Among the finite Weyl groups, this classification coincides with Proctor's classification
of the parabolic quotients of Weyl groups whose Bruhat ordering is a lattice [P]. In the
final section, we extend Proctor's result by classifying all parabolic quotients of arbitrary
Coxeter groups such that (1) the Bruhat ordering is a lattice, (2) the Bruhat ordering
is a distributive lattice, (3) the weak ordering is a distributive lattice, and (4) the weak
ordering and Bruhat ordering coincide. Interestingly, one finds that all four classification
problems have the same answer.
1. Preliminaries
Throughout this paper, W shall denote a Coxeter group with finite generating set S
and Coxeter matrix is the order of st in W (possibly
denote the Coxeter graph of (W; S); i.e., the simple graph with
vertex set S and edges between pairs of non-commuting generators. By the Coxeter
diagram, we mean the pair (\Gamma; M ), regarding M as a weight function on the edges of \Gamma.
1.1 Commutativity classes.
Let S   denote the free monoid generated by S. We will represent the members of S
as sequences, so that would be typical. By a subword of s, we shall mean
a subsequence of s occupying consecutive positions, such as
integers us define
For w 2 W , let '(w) denote the minimum length of any expression
S. Any such minimum-length expression for w is said to be reduced. It will be
convenient more generally to declare any expression of the form
to be reduced if denote the set of all words
l and the expression is reduced.
Let - denote the congruence on S   generated by the braid relations
for all s; t 2 S such that m(s; t) ! 1. Of central importance for this paper is the fact that
if s is any particular reduced word for w, then R(w) is the equivalence class of s relative
to -; i.e., any reduced word for w can be obtained from any other by means of the braid
relations [B, xIV.1.5].
Now consider the weaker congruence - on S   generated by the braid relations corresponding
to pairs of commuting generators (i.e., the relations (s;
such that m(s; We remark that the quotient monoids S   =-, known in the literature
abelian monoids, or commutation monoids, were first studied in a
systematic way by Cartier and Foata [CF]. (See also the survey in [V].)
The equivalence class C of a given reduced word s (relative to -) consists of the words
obtainable from s by transposing adjacent commuting pairs. We call C the commutativity
class of s. Since - is weaker than -, it is clear that there is a decomposition
of R(w) into commutativity classes. If R(w) consists of just one commutativity class, we
say that w is fully commutative.
Proposition 1.1. An element w 2 W is fully commutative if and only if for all s; t 2 S
such that 3 - m(s; there is no member of R(w) that contains hs; ti m(s;t) as a
subword.
Proof. Given the fact that any reduced word can be obtained from any other via the
braid relations, the sufficiency of the stated condition is clear. To prove that it is also
necessary, suppose that s is a reduced word for some w 2 W , and that s; t 2 S are such
that 3 - m(s; t) ! 1. Every member of the commutativity class of s can be obtained
by exchanging adjacent pairs of letters not including the pair s; t. It follows that the
subsequence of s formed by the occurrences of s and t is an invariant of the commutativity
class of s. Therefore, if s contains hs; ti m as a subword (where then the
reduced word s 0 obtained by applying the braid relation hs; ti m - ht; si m belongs to a
different commutativity class, and hence w could not be fully commutative.
1.2 Heaps.
be an arbitrary (i.e., not necessarily reduced) word in S   . Define a
partial ordering 4 on [ l via the transitive closure of the relations
2:
In particular, i OE j if . The triple P can be regarded as a
labeled poset (i.e., a partial order in which the elements have special labels), the label of
the ith vertex being s i . Following the terminology of [V], we call P s the heap of s.
Let P be any partial ordering of [ l ]. By a linear extension of P , we mean a total
ordering
We let L(P ) denote the set of all linear extensions of P . Regarding s as a labeling of P
(i.e., the element i has label s i ), it is convenient to define
In the case of a heap, the elements with the same label are totally ordered, so there is
at most one linear extension corresponding to any given word in S   . We will refer to the
members of L(P; s) as labeled linear extensions of P .
The following result is a standard part of the theory of heaps (e.g., see Lemma 3.2 of [V]
or Exercise 3.48(b) of [St]).
Proposition 1.2. For s is the commutativity class of s.
Proof. Suppose that s
l
) is the corresponding
linear extension. Since adjacent elements in a linear extension must either be incomparable
or a covering pair, it follows that for every k ! l, either -(k) and -(k+1) are incomparable
in P s
, or else s 0
k and s 0
k+1 do not commute. Therefore, the interchange of any pair of
adjacent commuting generators in s 0 corresponds to the interchange of a pair of adjacent
incomparable elements in -, and hence yields another (labeled) linear extension of P s
it follows that L(P s
contains the commutativity class of s.
Conversely, to prove that L(P s
only contains elements from the commutativity class
of s, we proceed by induction on the length of s. Suppose that - and s 0 are as above.
is a maximal element of P s
must commute with s j for all j ? i, so
labeled linear extension
of the heap of (s induction we obtain s and the result
follows.
We remark that P s
is an invariant of the commutativity class of s in the sense that
there exists a poset isomorphism
'(i) .
In particular, if w is fully commutative, the heaps of the reduced words for w are all
equivalent, so we may speak of the heap of w without ambiguity.
1.3 The weak order.
The (right) weak ordering of (W; S), denoted -R , is defined to be the transitive closure
of the relations w !R ws for all w 2 W , s 2 S such that '(w) ! '(ws). Equivalently, for
all one has x -R xy if and only if xy is reduced (i.e., '(y)). The
left weak ordering is defined similarly-one has y -L xy if and only if xy is reduced. We
remark that the map w 7! w \Gamma1 provides an isomorphism between the left and right weak
orderings of W . Apart from the special case of symmetric groups, the weak ordering of
Coxeter groups seems to have been first studied by Bj-orner [Bj].
Proposition 1.3. For all x; y 2 W such that x -R y, we have
as subposets of (W; -R ).
Proof. The map w 7! x \Gamma1 w is easily shown to be an isomorphism.
Note that an immediate consequence of Proposition 1.1 is the fact that if w is fully
commutative and w 0 -R w, then w 0 is also fully commutative; i.e.,
Proposition 1.4. The set of fully commutative elements of W forms an order ideal
with respect to the right (or left) weak order.
For
denote the right and left descent sets for w, respectively. It is well-known (e.g., [H, x1.10])
that for all J ae S,
are, respectively, left and right coset representatives for the parabolic subgroup W J generated
by J . Let us also note that for I; J ae S,
I W
forms a set of double coset representatives for W I nW=W J .
Proposition 1.5. For J ae S, J W (resp., W J ) is an order ideal of the right (resp.,
left) weak ordering of W .
Proof. Let w 2 J W . If w 0 -R w, then there exists a reduced expression
some x 2 W . Hence for any s 2 J , reduced, so sw 0 is reduced. In other
words,
It should be noted that W J need not be an order ideal of the right weak order.
We remark that if W is finite, with w 0 2 W being the longest element, the fact that
shows that w 0 is the unique
maximal element of W with respect to -R and -L . More generally, if w J
the left coset representative for w 0 , we have the following.
Proposition 1.6. For J ae S, w J
0 is the unique maximal element of (W J ; -L ).
Proof. Let x 0 denote the longest element of W J . Given w 2 W J , the expression wx 0
must be reduced (otherwise by the deletion property [H, x5.8], w would not be the shortest
member of its coset). Similarly, the expression w
must be reduced. Therefore
2. Characterizations of full commutativity
For any partial order P , let J(P ) denote the distributive lattice of order ideals of P .
Lemma 2.1. Let w 2 W be of length l. If P is a partial order of [ l ] and s 2 S   is a
labeling such that posets.
Proof. We claim that for s 2 S, C s := totally ordered subset of P .
Indeed, if i and j were incomparable and s s, then there would exist a linear
extension of P in which i and j appear consecutively. However, the corresponding word in
would have two consecutive occurrences of s, and hence could not be a reduced word
for w, proving the claim.
Now let s (i) denote the ith smallest member of the chain C s , relative to P . For any
to be the number of occurrences of s in s 0 .
Suppose that s 0 is a reduced word for some x -R w. Since any reduced word for x
can be completed to a reduced word for w, it follows that s 0 is an initial segment of some
labeled linear extension of P , and hence
is an order ideal of P . Furthermore, we claim that if s 00 is another reduced word for x,
then would be necessary that -(s; s 0 )
the suffix of any completion of s 0 to a reduced word for w can also be used as
the suffix for a completion of s 00 , it follows that there exist reduced words for w in which
the multiplicity of s varies. However by assumption, so every reduced
word for w must be a permutation of s.
We can thus use I(x) to denote the common value of I(s 0 ) for s 0 2 R(x). We claim that
the map x 7! I(x) defines an order-isomorphism between fx
To prove this, we first note that the map is order-preserving. Indeed, given any covering
relation x !R xs, we can choose a reduced word for x and complete it to a reduced word
for xs by appending s, and therefore I(x) ae I(xs).
To prove that the map is surjective, let I be an order ideal of P . One can find s
so that some initial segment of s 0 , say s 00 , is a labeled linear extension of I. However by
hypothesis, s 0 must be a reduced word for w. Hence s 00 must be a reduced word for some
To prove that the map is injective, suppose that
In that case, there must exist a labeled linear extension of I belonging to R(x). Any
completion of this to a labeled linear extension of P (thus yielding a reduced word for w)
must be a reduced word for x \Gamma1 w. On the other hand, since I, the same argument
proves that it must also be a reduced word for y y.
Let us declare a subset R of S   to be order-theoretic if there exists a partial ordering
of [ l ] for some integer l - 0 and a labeling s 2 S   of P so that
Theorem 2.2. For w 2 W , the following are equivalent:
(a) w is fully commutative.
as a subposet of (W; -R ), is a distributive lattice.
(c) fx (equivalently, every) s 2 R(w).
(d) R(w) is order-theoretic.
(equivalently, every) s 2 R(w).
Proof. The implications (c))(b) and (e))(d) are immediate, (e))(c) and (d))(b) are
special cases of Lemma 2.1, and (a))(e) follows from Proposition 1.2. To complete the
stst=tsts stst=tsts
sts
st
s
tst
ts
sts
st
s
tst
ts

Figure

1(a). Figure 1(b).
proof, it therefore suffices to establish (b))(a). For this, assume towards a contradiction
that fx 2 W : x -R wg is a distributive lattice, but that w is not fully commutative.
Among all such counterexamples, assume that w is one that minimizes length. By Proposition
1.1, there must exist a reduced word s 2 R(w) and a pair s; t 2 S such that
occurs as a subword of s, where
1.3 shows that if w 0 2 W has a reduced word that occurs as a subword of s, then
is order-isomorphic to a subinterval of fx
subintervals of distributive lattices are also distributive, the minimality of '(w) forces
must be the longest element of the dihedral Coxeter group generated
by fs; tg. Since the weak ordering of such Coxeter groups is transparently not distributive
Figure 1(a) for the case we obtain a contradiction.
A subset C of a partial order P is said to be convex if
implies k 2 C. The following result provides an intrinsic characterization of the heaps of
fully commutative elements.
Proposition 2.3. The heap P of a word s 2 S   is the heap of some fully commutative
only if
(a) There is no convex chain in P such that s i 1
(b) There is no covering relation in P such that s
Proof. For any convex chain (or covering relation) of a poset P , there exist linear
extensions in which the members of the chain appear consecutively. Thus if s is a reduced
word for some fully commutative w 2 W , Proposition 1.1 implies the necessity of (a). Since
no reduced word can have two equal adjacent terms, (b) is also necessary. Conversely,
given (a), Proposition 1.2 implies that the commutativity class of s has no members that
contain hs; ti m as a subword, for all s; t 2 S such that 3. Therefore, the
equivalence class of s relative to the braid relations is the same as its commutativity class.
If follows that P is the heap of some fully commutative member of W , provided that s is
a reduced word. However, this additional property is a consequence of (b).
3. Special properties
Suppose that P is the heap of (a reduced word for) some fully commutative w 2 W .
Recall that for each s 2 S, the members of P with label s form a chain. It will be
convenient for what follows to let s (i) denote the ith greatest member of this chain with
respect to P . (This is dual to the notation used in the proof of Lemma 2.1, but should
not cause confusion.)
Lemma 3.1. Let s 2 S, and let w 2 W be fully commutative with heap P . If ws is not
fully commutative, then ws is reduced and there is a unique t 2 S such that m(s; t) - 3
and s (1) ! t (1) in P . Moreover, m(s;
is a convex chain in P .
Proof. Since the fully commutative part of W is an order ideal with respect to -R
(Proposition 1.4), it follows that if ws is not fully commutative, then ws is reduced. Now
let P 0 be the heap obtained from P by appending s at the end of a reduced word for w,
and let s (0) denote the new vertex. For ws to not be fully commutative, it is necessary by
Proposition 2.3 that for some generator t 2 S such that 3 - m(s;
occurring as a convex chain in P 0 . If there were another
then we would have s (1)
the above chain would not be convex.
3.1 Reduction to maximal quotients.
For fsg. Note that the maximal quotient W hsi consists of the
identity element, together with those w 2 W with the property that every s 2 R(w) ends
with s. The fully commutative elements with this property are characterized by the fact
that their heaps have a maximum element with label s.
Theorem 3.2. If W is irreducible and w 2 W is fully commutative, then there exists
a fully commutative w 0 -R w such that w 0 2 W hsi for some s 2 S.
Proof. Let s be a reduced word for w and
the heap of w. We may assume that
every s 2 S appears in s, since if s does not appear, then ws ?R w and ws is still fully
commutative.
denote the right descent set of w. Thus s 2 D if and only if s (1)
is maximal in P . If fsg is a singleton, then w 2 W hsi and there is nothing more to
prove. Otherwise, let us define the separation of D to be the minimum distance in the
Coxeter graph \Gamma among all pairs of elements in D. (Note that \Gamma is connected since W is
assumed to be irreducible.) We claim that there exists a fully commutative w 0 ?R w such
that either jDR (w 0 )j ! jDR (w)j, or else jDR (w 0 smaller
separation than DR (w). By iteration, this result would establish the existence of a fully
commutative w 0 ?R w such that jDR (w 0 completing the proof.
To prove the claim, consider a pair s; t 2 D whose distance in \Gamma is minimal, and let
be a shortest path from s to t. It is necessary that m(s
the path is not minimal), and l - 2
(otherwise, s (1) and t (1) would be comparable in P and hence could not both be maximal).
In particular, since s i\Gamma1 and s i do not commute, s (1)
i must be comparable in P .
Bearing in mind that s (1) and t (1) are both maximal in P , it follows that there must exist
an index i such that
s (1)
In particular, there are (at least) two elements greater than s (1)
in P whose labels do not
commute with s i . Thus ws i is reduced and (by Lemma 3.1) fully commutative. Further-
more, in the heap of ws i , we have
s (1)
Hence by similar reasoning, ws i s i\Gamma1 is reduced and fully commutative. Iterating this
reasoning, we obtain that w 0 := ws i s reduced and fully commutative. Moreover,
we have there is only one element (namely, s 1 ) of DR (w 0 ) not in
DR (w), so jDR (w 0 )j - jDR (w)j. If equality occurs, then we have s and the
separation of DR (w 0 ) is at most l \Gamma 1.
Let -LR denote the partial order on W generated by the union of the left and right
i.e., the transitive closure of the relations x !LR xy and y !LR xy for all
such that xy is reduced. It is clear that the fully commutative elements of W
form an order ideal with respect to !LR . The following result shows that this order ideal
is generated by members of the maximal two-sided quotients of W .
Corollary 3.3. If W is irreducible and w 2 W is fully commutative, then there exists
a fully commutative w 0 -LR w such that w 0 2 hsi W hti for some s; t 2 S.
Proof. By Theorem 3.2, there is a fully commutative w 0 -R w such that w 0 2 W hsi for
some s 2 S. It follows that s (1) is the unique maximal element of the heap of w 0 . Without
loss of generality, we can assume that every member of S occurs in some (equivalently,
reduced word for w 0 , so that adding elements at the bottom of the heap will not
change the fact that s (1) is the unique maximal element of the heap. In other words, for
every fully commutative w 00 -L w 0 , we have w 00 2 W hsi . However, by the dual version of
Theorem 3.2, we can find a fully commutative w 00 -L w 0 such that w 00 2 hti W for some
3.2 The top tree of a maximal element.
By an ordering of a tree T with vertex set S, we mean a partial ordering of S obtained
by choosing a special vertex s 0 2 S, and declaring s ! t if t is on the unique path from s
to s 0 . The Hasse diagram of such an ordering is the tree T , rooted at s 0 .
Let w 2 W be fully commutative with heap P . We will say that w is right-maximal
left-maximal) if for every s 2 S, ws (resp., sw) is either not reduced or not fully
commutative. In other words, w is maximal in the right (resp., left) weak order with
respect to full commutativity. In case w is right-maximal, it will be convenient to define
a subposet of P . (We will sometimes abuse this notation and regard
P (1) as a partial order on S.) It should be noted that every generator must occur in any
reduced word for a right-maximal element, so s (1) is indeed defined for all s 2 S.
The following result explains why we refer to P (1) as the top tree. 2
Theorem 3.4. Assume that W is irreducible. If w 2 W is fully commutative and
right-maximal with heap P , then the Coxeter graph \Gamma is a tree, P (1) is an order filter of
P , and P (1) is an ordering of the tree \Gamma.
Proof. Choose s 2 S, and suppose that t (i) covers s (1) in P for some t 2 S and i - 1. It
follows that s (1) ! t (i) - t (1) in P and m(s; t) - 3. Since ws cannot be fully commutative,
Lemma 3.1 implies that the two-element chain s (1) ! t (1) must be convex (i.e., a covering
in P , and therefore In other words, the only members of P that cover s (1)
are members of P (1) ; thus P (1) is an order filter of P .
We thank R. Proctor for suggesting this terminology.
A second consequence of Lemma 3.1 is that there can be at most one element covering
s (1) in P . Since Theorem 3.2 implies that the heap of a right-maximal w has a unique
maximal element, it follows that P (1) is an ordering of some tree. Hence to complete the
proof, we must show that this tree is \Gamma. Certainly it is true that every covering relation of
must involve a pair of elements whose labels are non-commuting generators-these are
the adjacent pairs in \Gamma. Conversely, given a pair of non-commuting generators s; t 2 S, it
must be the case that s (1) and t (1) are comparable in P ; say s . In that case, since
ws cannot be fully commutative, Lemma 3.1 implies that t (1) must be the only element
greater than s (1) in P whose label does not commute with s, so it must cover s (1) .
3.3. The classification of top trees.
If Q is an ordering of a tree on the vertex set S, we will use the notation t / s to
indicate the covering relation of Q; i.e., t ! s in Q and s; t are adjacent in the tree.
The following result describes the irreducible Coxeter groups that contain right-maximal
fully commutative elements, as well as the top trees of all such elements. Of course by
the previous result, we know that W cannot contain any left- or right-maximal elements
unless the Coxeter graph \Gamma is a tree, but this is far from sufficient.
Theorem 3.5. Assume that \Gamma is a tree, and let Q be an ordering of \Gamma. There exists a
fully commutative right-maximal w 2 W with top tree Q (i.e., P
of w) if and only if the following conditions are satisfied for all s; t; u 2 S:
(a) m(s; t) ! 1.
(b) If t / s, u / s and t 6= u, then m(s;
(c) If u / t / s, then m(s;
(d) If u / t / s and m(s;
Proof. We first prove that conditions (a)-(d) are necessarily satisfied by any right-
maximal w 2 W with heap P such that
(a) If s; t 2 S are such that m(s; t) - 3, then either s (1) ! t (1) or t (1) ! s (1) . Assuming
the latter, wt must be reduced and therefore cannot be fully commutative. However by
Lemma 3.1, this is possible only if m(s; t) ! 1.
(b) Assume towards a contradiction that t / s, u / s, t 6= u, and m(s; In
that case, wt is reduced and therefore cannot be fully commutative. Thus by Lemma 3.1,
must occur as a convex chain in P . However, u / s implies that
covering relation of P . Since u (1) and s (2) must be comparable, we therefore
have s (2) ! u so the chain s (2) ! t (1) ! s (1) is not convex, a contradiction.
(c) Assume towards a contradiction that u / t / s and m(s; t) - 5. As in the previous
case, it follows that wt is reduced and therefore cannot be fully commutative. Thus by
must occur as a convex chain in P . However, u / t
implies that u (1) ! t (1) is a covering relation of P . Since u (1) and t (2) must be comparable,
it follows that t (2) ! u so the chain t (2) not convex, a
contradiction.
(d) Assume towards a contradiction that u / t / s, m(s; In
this case, both wt and wu are reduced and hence neither can be fully commutative. By
Lemma 3.1, it follows that both s (2) must occur as
convex chains in P . In particular, s (2) must be a covering relation. However, s (2)
and t (2) must be comparable, so t (2) contradicting the convexity of the chain
For the converse, we assume (a)-(d) and construct a right-maximal w 2 W with top
tree Q, by induction on jSj. If the nonidentity member of W suffices. If
then (a) implies that W is a finite dihedral group, and it is straightforward to construct a
suitable element w in this case.
Otherwise, we have jSj - 3. Let s 2 S denote the root of Q, and let Q
the ordered subtrees obtained by deleting the root from Q. Each subtree has a root s i 2 S.
Furthermore, the parabolic subgroups W i generated by each Q i commute with each other.
By induction, we can find a fully commutative right-maximal element w i (relative to W i
with top tree Q i , for each i.
Case 1: k - 2, or does
not occur in any reduced expression for w i , it is clear that w is fully commutative. To
prove that w is right-maximal, choose t 2 S and consider wt. If then wt is not
reduced. If t is an internal vertex of Q reduced and hence cannot be fully
commutative, since w i is right-maximal for W i . Hence,
be fully commutative. The remaining possibility is that
(b) implies m(s hypothesis.
Since s i is the root of Q i , every reduced word for w i ends with s i , so w i ss i is not fully
commutative, so fully commutative. Thus w is indeed right-maximal, and
it is clear that Q is the top tree of w.
Case 2: has two or more elements, (c) implies
that this is the only remaining possibility.) Since s 1 is the root of Q 1 , there is a reduced
expression for w 1 of the form w
1 s is reduced (s does not occur in w 0
1 is the
shortest representative of its left coset, relative to the parabolic subgroup generated by
g. In particular, the expression w
We claim that w is fully commutative. To see this, we argue incrementally as follows.
First, w 0
1 s is fully commutative, since s 62 W 1 . Second, w 0
ss 1 is fully commutative, since
otherwise Lemma 3.1 (and the fact that m(s would imply that some reduced
expression for w 0
must involve s. Finally, it follows that
fully commutative,
since otherwise by Lemma 3.1, s (2)
1 must be a convex chain in the heap of
ss 1 . Hence there would be a reduced expression for w 0
ending with s 1 , contradicting
the fact that w 0
Finally, we claim that w is right-maximal. For this, choose t 2 S and consider wt. If
then wt is not reduced. If
ss 1 ss 1 is transparently not fully
commutative. Otherwise, t is an internal vertex of Q 1 . In particular, it commutes with s,
and by maximality of w
is not fully commutative. If t also commutes
with
must also not be fully commutative, and hence
s is not fully
commutative. Otherwise, by (d) we have m(s 3.1 implies that there
is a reduced expression for w 0
ending with t. Therefore, there is a reduced expression for
wt ending with tss 1 st = sts 1 ts, which is not fully commutative.
4. The classification of FC-finite Coxeter groups
We will say that W is FC-finite if the number of fully commutative w 2 W is finite.
The simply-laced FC-finite Coxeter groups were classified by Fan in his thesis [F]; in the
following, we treat the general case. It is interesting to note that there are no "exceptional"
FC-finite Coxeter groups, in the sense that the irreducible ones occur in seven naturally
identifiable infinite families. (See Figure 2.)
Theorem 4.1. The irreducible FC-finite Coxeter groups are An (n - 1), Bn (n - 2),
Before beginning the proof, let us outline the strategy. First, we derive a list of necessary
conditions that collectively eliminate all Coxeter groups not named in the above list. For
the converse, it is well known and easy to show that the groups An , Bn , Dn and I 2 (m)
are finite (and hence, FC-finite), so we confine our attention to proving that the
groups En , Fn and Hn are FC-finite.
Proof. Assume that W is irreducible and FC-finite.
must be acyclic. Indeed, suppose that s a circuit of \Gamma, so that
s i and s i+1 do not commute for 1 - i - n (subscripts taken modulo n). It follows that
any initial segment of the word
F
I

Figure

2: The FC-finite Coxeter groups.
has no subwords of the form hs; ti m with Hence, any such word is not merely
reduced, it is also rigid; i.e., it is the unique reduced word for some w 2 W . In particular,
any such w is fully commutative, so W could not be FC-finite.
(2) Every edge of \Gamma has finite weight. If m(s; initial segment of the
infinite word (s; t; s; t; s;
\Gamma has at most one edge of weight -4. Otherwise, there exists a path s
\Gamma such that n - 3, m(s However in that case, any initial
segment of the following infinite word is rigid:
We remark that an alternative proof of (1) and (2) is provided by the fact that any FC-
finite Coxeter group must contain right-maximal fully commutative elements, and hence
must satisfy the conditions of Theorems 3.4 and 3.5. We also remark that it is not hard
to show that properties (1)-(3) characterize the (irreducible) Coxeter groups with finitely
many rigid elements.
no vertex of degree -4, and at most one vertex of degree 3. Otherwise, \Gamma
contains an induced subgraph isomorphic to the one indicated in Figure 3(a); the existence
(a)
(b)

Figure

3.

Figure

4.
of a vertex of degree 4 corresponds to the case 5. Now consider the infinite word
The only subwords of the form hs; ti m with that occur in this word involve
the commuting pairs this property is preserved when any of
these pairs are transposed, it follows that every initial segment of this word is reduced and
fully commutative.
have both a vertex of degree 3 and an edge of weight -4. Otherwise,
contains an induced subgraph isomorphic to the one indicated in Figure 3(b), with
4. In this case, consider the infinite word
The only subwords of the form hs; ti m with that occur in this word involve
the commuting pair (s this property is preserved when any of these pairs
are transposed, it follows that every initial segment of this word is reduced and fully
commutative.
Assuming W 6= A 1 , properties (1)-(5) imply that the Coxeter diagram (\Gamma; M ) must be
isomorphic to a member of one of the families Y (p; q; r) or I(p; q; m) indicated in Figure 4,
with 1. Note that in the former case, every edge has weight 3; in the latter case,
one edge has weight m for some (finite) m - 3, and the remainder have weight 3.
m) is not FC-finite. Indeed, if the generators
are labeled so that m(s then the infinite word
has the property that the only subwords of the form hs; ti m with that occur involve
the commuting pair Furthermore, when any of these pairs are interchanged,
the longest alternating length 5, and the occurrences of (s
disjoint. Hence, any initial segment of this word is reduced and fully com-
mutative. It follows that if \Gamma has an edge of weight - 6, then W must be one of the (finite)
dihedral groups I 2 (m).
(7) If p; q -2, then I(p; q;5) is not FC-finite. We can assume that the generators are
labeled so that m(s
forming the two "branches" of
the Coxeter graph. Again we claim that there is an infinite word whose initial segments
are reduced words for fully commutative members of W . However in this case, it is more
helpful to describe the heap of this infinite word: See Figure 5. (Note that the vertices
of the heap have been assigned the labels of the corresponding generators.) One merely
needs to check that this poset satisfies the criterion of Proposition 2.3. Once this is done,
it follows that every (finite) order ideal of this poset is the heap of some fully commutative
element. Thus if the group FC-finite, it is necessary that min(p;
however in that case, W
(8) If p; q -3, then I(p; q;4) is not FC-finite. Let us continue the labeling of the
generators established in (7), except that we now have m(s
4. In this case, the
infinite heap of Figure 6 satisfies the conditions of Proposition 2.3, and hence proves that
the group in question is not FC-finite. It follows that if
2. However in that case, W is isomorphic to B p+q or F p+q .
The only remaining groups of the form I(p; q; m) are those for which
these are Coxeter groups of type A.
r) is not FC-finite. Let us suppose that the generators
are labeled so that s 0 is the vertex of degree 3, with s
forming the three branches of \Gamma. In this case, the infinite heap of Figure 7 proves that
these groups cannot be FC-finite.
r) is not FC-finite. Continuing the labeling used
in (9), the infinite heap of Figure 8 proves that these groups cannot be FC-finite.
Properties prove that if
then (q; 1). However in these respective cases, one has W
and

Figure

5.

Figure

6.
Figure

7.

Figure

8.
To complete the proof of Theorem 4.1, it remains to be shown that the groups En , Fn ,
and Hn are FC-finite. Continuing the notation of Section 3, given a heap P and s 2 S,
let s (i) denote the ith greatest vertex of P with label s, relative to the partial order.
Lemma 4.2. Let If s has degree one in \Gamma (or 1), then there is
at most one occurrence of s in any reduced word for any fully commutative w 2 W .
Proof. Let P be the heap of some fully commutative w 2 W in which two or more
vertices are labeled s. Clearly n - 2, so there is a unique t 2 S such that m(s; It
follows that the convex subposet of P is the heap of some
fully commutative member w 0 of the parabolic subgroup of type A generated by S \Gamma fsg.
Since Q is nonempty (Proposition 2.3(b)), it follows that at least one member of Q covers
s (2) and at least one is covered by s (1) . The labels of such elements cannot commute
with s, and hence must be t. However by induction with respect to n, every reduced word
for w 0 has at most one occurrence of t. Thus in fact Q must consist of a single vertex with
label t; given that w is fully commutative, this contradicts Proposition 2.3(a).
Suppose that the parabolic subgroup of W generated by some J ae S is of type A. If
there is a unique s 2 J and a unique t 2 S \Gamma J such that m(s; t) - 3, and if moreover s is
an "end node" (i.e., jJ or s has degree one relative to J), then we will say that J is
a branch of S, with s and t being the points of contact. If m(s; the branch will be
said to be simple.
Lemma 4.3. Let J be a branch of S with points of contact s 2 J and t
the heap of some fully commutative w 2 W , then for each i ? 1 such that t (i) is defined,
there is at most one vertex j of P with label s such that t (i) in P . In that
case, the chain t (i)
Proof. Let t be an unrefinable chain of P with at least
one member having label s. The label sequence corresponding to j must form a
path in \Gamma from t to t with no intermediate vertex of label t and at least one vertex with
label s. Given that J is a branch of S, this is possible only if j 1 and j m both have label s.
It follows that Q is the heap of some fully commutative
member of W J , a Coxeter group of type A. However by Lemma 4.2, any such heap can
have at most one vertex with label s, so
Lemma 4.4. Let J be a simple branch of S with points of contact s 2 J and t
If P is the heap of some fully commutative w 2 W and there is an unrefinable chain
in P such that
have label s, then m - jJ j.
Proof. Proceed by induction on m, the case being trivial. We note that J \Gamma fsg
is also a simple branch of S, with the points of contact being s and some s
By Proposition 2.3, the chain cannot be convex, so there must exist some
other vertex k of P such that covering j 1 . Since J is a branch, the
only generators not commuting with s are t and s 0 , so this is possible only if the label of k
is s 0 . However in that case, Lemma 4.3 implies that the chain
Iterating this argument, we obtain an unrefinable chain
P such that k Hence by the induction hypothesis, we must have
Proof that Hn is FC-finite. For exist generators s; t 2 S such that
is a branch, with the points of contact being s and t. Now suppose
that P is the heap of some fully commutative w 2 Hn , and let be the
vertices of P with label t. Since s is the only generator that does not commute with t,
Lemma 4.3 implies that there is an unrefinable chain
P such that have label s. Now by Proposition 2.3,
cannot be a convex chain in P . On the other hand, there is a unique s 0
does not commute with s and there is no such vertex that does not commute with t. It
follows that there must be some vertex k 2 P with label s 0 such . Iterating this
argument, we obtain the existence of a chain in P in which
label s 0 . By Lemma 4.3, this chain must be unrefinable. Furthermore,
since is a simple branch of S of size 2.
In other words, every fully commutative w 2 Hn uses the generator t at most n times.
Thus any such element can be expressed in the form w
each w i belongs to the (finite) parabolic subgroup generated by S \Gamma ftg.
Proof that Fn is FC-finite. Let s; t 2 S denote the two generators of
denote the end node with m(t; t 0 and the property that
is a branch of S. Now suppose that P is the heap of some fully commutative w 2 Fn .
We first claim that for each i such that t (i+1) occurs in P , there must exist a vertex labeled
s in the convex subposet g. Otherwise, Q i is the heap of
some fully commutative w 0 in the parabolic subgroup generated by S \Gamma fs; tg. However,
the only member of S \Gamma fs; tg that does not commute with t is t 0 , so by Lemma 4.3, Q i
must consist of a singleton vertex with label t 0 . This contradicts Proposition 2.3, so the
claim follows.
Secondly, we claim that Q i and Q i+1 cannot both contain vertices with label t 0 . Oth-
erwise, there would exist a chain t necessarily unrefinable
(Lemma 4.3), in which k 1 and k 2 both have label t 0 . However, ft 0 g is a simple branch of S,
so this contradicts Lemma 4.4.
denote the vertices of P with label t. By the first claim, there is
a chain in P such that have label s. By
Lemma 4.3, this chain must be unrefinable. By the second claim, there is either no vertex
k of P with label t 0 such that else no such vertex with . If the
former holds, consider the chain if the latter, consider
By Proposition 2.3, neither chain can be convex. Since every generator commutes with
either s or t, and we have eliminated the possibility of a vertex labeled t 0 between i 1 and i 2
(the former case) or between i 2 and i 3 (the latter case), the only remaining possibility is
that there is a vertex k such that with the label of k being a generator
not commuting with s, other than t. Note there is a unique generator, say s
property. Note also that S \Gamma fs; t; t 0 g is a simple branch of S, with the points of contact
being s and s 0 .
By iterating this argument, we obtain a chain
with the property that k Lemma 4.3, this chain must be
unrefinable. Furthermore, since S \Gamma fs; t; t 0 g is a simple branch, Lemma 4.4 implies that
In other words, every fully commutative w 2 Fn uses the generator t at most
times. Thus any such element can be expressed in the form w
and each w i belongs to the (finite) parabolic subgroup generated by S \Gamma ftg.
Proof that En is FC-finite. We can label the generators of that t has degree 3
in \Gamma, and s; s are the generators adjacent to t. We can arrange the labels so that there
are (simple) branches of sizes with points of contact t and (respectively) s,
s 0 and s 00 . Now suppose that P is the heap of some fully commutative w 2 En . Assuming
that t (i+1) occurs in P , consider the convex subposet
of P . The possible labels of elements covering t (i+1) are s; s Since each of them is a
point of contact for a branch at t, Lemma 4.3 implies that each such element must also
be covered by t (i) . Since Proposition 2.3 implies that Q i cannot be a singleton, there are
three remaining possibilities:
(a) Q i is a tripleton, with vertices labeled s; s 0 , and s 00 .
(b) Q i is a doubleton, with vertices labeled s and s 0 .
(c) Q i is a doubleton, with vertices labeled s and s 00 .
(d) Q i is a doubleton, with vertices labeled s 0 and s 00 .
Note that the members of Q i are incomparable in P .
Given that there are m occurrences of the label t in P , we can construct a word ff
of length in the alphabet fa; b; c; dg, according to the type of each subinterval
is a simple branch of S, Lemma 4.4 implies that there can
be no subword of ff of the form xy, where x; y 2 fa; c; dg. Furthermore, we claim that
the letter d can appear only at the beginning or end of ff. Otherwise, the only possible
subword of the form xdy that avoids the previously forbidden subwords of length 2 is bdb.
However if this occurs, then for some i, each of Q vertices labeled s 0 ,
contradicting Lemma 4.4 and the fact that there is a simple branch of size 2 connecting
s 0 and t.
Since d is the only interval-type omitting vertices labeled s, it follows that Q
must each contain a vertex labeled s. Since there is a simple branch of size connecting
s and t, Lemma 4.4 implies that In other words, the generator t can appear
at most n \Gamma 1 times in any fully commutative w 2 En . Thus any such w can be expressed
in the form w and each w i belongs to the (finite) parabolic
subgroup generated by S \Gamma ftg.
5. Fully commutative quotients
By Theorem 3.2, we know that the order ideal (with respect to -R ) of fully commutative
elements of W is generated by the fully commutative parts of the maximal parabolic
quotients W hsi for s 2 S. Thus to a large extent, the task of determining all fully commutative
elements of W reduces to the corresponding question for maximal quotients. In the
case of the symmetric groups, the situation is particularly simple, since it is known (and it
also follows from what will be demonstrated below) that every member of every maximal
quotient is fully commutative. This raises the question: Which parabolic quotients of
Coxeter groups (not necessarily maximal) have the property that every member is fully
commutative? As we shall see, apart from degenerate cases, the answer to this question
also turns out to be the answer to several very natural order-theoretic questions about
parabolic quotients.
Let J ae S. The quotient W J will be said to be minuscule if W is (isomorphic to)
a finite Weyl group and the subgroup W J is the stabilizer of a minuscule weight -.
nonzero weight - is minuscule if there is a representation of a semisimple Lie algebra with
Weyl group W whose set of weights is the W -orbit of -.) The classification of minuscule
weights is well-known and can be found in Exercise VI.4.15 of [B], for example. Assuming
that W is irreducible, the pairs (W; W J ) such that the quotient W J is minuscule are as
follows:
1.
2.
3.
4. (W; W J
Note that all irreducible minuscule quotients are also maximal quotients.
Theorem 5.1. Assume that W is irreducible. If J is a proper subset of S, then every
member of W J is fully commutative if and only if one of the following is true:
(a) Every edge of \Gamma has infinite weight (i.e., m(s;
(b) W J is minuscule.
(c) (W; W J
Proof. First, we show that properties (a)-(c) are each sufficient to imply that every
member of W J is fully commutative. Indeed, if (a) holds, then the only braid relations
involve pairs of commuting generators, and hence every member of W is fully commutative.
(m), then there is only one member of W that is not fully commutative; namely,
the longest element w 0 . It has (right) descent set S, and hence does not belong to W J
unless
In case W label the generators s
Also, set so that W J (5). Now consider the heap P of
depicted in Figure 9. Using only Proposition 2.3, it is clear that P is the heap of some fully
commutative w 2 W . Furthermore, since the unique maximal element of P has label 3, we
have w 2 W J . Bearing in mind that the longest elements of H 3 and I 2 (5) have respective
lengths 15 and 5, it follows that w must be w J
(the longest element of W J ), since it has
length
0 is the unique maximal element of W J with respect to
-L (Proposition 1.6), so every member of W J is fully commutative (Proposition 1.5).
Now consider (b); i.e., we suppose that W is a finite Weyl group with a crystallographic
root system \Phi embedded in some real Euclidean space E with inner product
roots lattice   ae E, and W J is the stabilizer of some minuscule weight
. For each ff 2 \Phi, let s ff 2 W denote the reflection on E fixing the hyperplane
perpendicular to ff, so that \Deltag.
Temporarily, let us discard the hypothesis that - is minuscule, and instead merely
assume that - 2 E belongs to the closure of the fundamental chamber (i.e., (-; ff) - 0 for
all ff 2 \Delta). In this case, one knows (e.g., [H, x1.12]) that the stabilizer of - is W J , where
0g.
Lemma 5.2. Given w 2 W J and ff 2 \Delta, we have s ff w !L w if and only if (w-; ff) ! 0.
Proof. If s ff w !L w, then it is necessarily the case that s ff w- 6= w-; otherwise, s ff w
would be a member of wW J , contradicting the fact that w is the shortest member of its
coset. Hence, (w-; ff) 6= 0. However since '(s ff w) ! '(w), it follows that w \Gamma1 ff must be a
negative root (e.g., [H, x1.6]). On the other hand, - is in the closure of the fundamental
chamber, so we must have (w-; Conversely, if (-; w
negative root, so '(s ff w) ! '(w) (again [H, x1.6]), so s ff w !L w.
Now suppose that w 2 W J is not fully commutative. By replacing w with some w 0 !L w
if necessary (cf. Propositions 1.1 and 1.5), we can assume that w has a reduced expression
of the form x 0 y, where x 0 is the element of length m(s; t) in the parabolic subgroup
generated by some fs; tg ae S such that m(s; t) - 3. Now let ff; fi 2 \Delta denote the simple
roots corresponding to s and t, so that
it follows that sw; tw !L w, and hence by Lemma 5.2, (w-;
For denote the corresponding co-root. Since \Phi is assumed to
be crystallographic, it follows that (w-; ff - ) and (w-; fi - ) are negative integers. Further-
more, since s and t generate an irreducible Weyl group of rank 2, it follows that there is
at least one root in the positive integral span of ff and fi, and the same is true of ff - and
relative to the co-root system \Phi - . That is, there exist integers c
such that . Thus we obtain
However, by Exercise VI.1.24 of Bourbaki [B], one knows that if - is minuscule, then
This contradicts the hypothesis that W J
contains elements that are not fully commutative.
We remark that in Proposition 10 of [F], Fan gives a different proof that every member
of a simply-laced minuscule quotient is fully commutative.
Turning to the converse, we derive a series of conditions that are necessary for every
member of W J to be fully commutative, and we show that these conditions collectively
eliminate all parabolic quotients other than those listed in (a)-(c). To begin with, we will
assume that \Gamma has at least one edge of finite weight (since otherwise (a) applies).
(1) Every edge of \Gamma has finite weight. Otherwise, given s are three
possibilities: (i) there is a pair t; u 2 S such that m(s;
there is a path s
or (iii) m(s In these respective cases, we claim that
the following are reduced words for some member of W J that is not fully commutative:
Figure


Figure

10.
In each case, it is straightforward to check that s is indeed a reduced word for some w 2 W .
In fact, one finds that R(w) has either two or three members, depending on whether t and
(case (i)) or s 1 and s 3 commute (cases (ii) and (iii)). It is also transparent
that w is not fully commutative. Since each of the two or three members of the braid
equivalence class of s ends with s, it follows that w 2 W J and the claim follows.
(2) W J is a maximal quotient. Otherwise, let be a path in \Gamma that
connects s; t consider the word
by (1).) It is easy to see that s is a
reduced word for some w 2 W that is not fully commutative. Furthermore, every member
of the braid equivalence class of s ends with either and the latter occurs
if and only if s 1 commutes with s Hence DR (w) ae fs; tg and w 2 W J .
Henceforth, we may assume that fixed s 2 S. In this situation, we
have w 2 W J if and only if DR 1. Thus we can reformulate our objective
as one of identifying conditions that force the existence of w 2 W with DR
are not fully commutative.
Lemma 5.3. Let I ae S \Gamma fsg, and suppose there is a path in \Gamma from some t 2 I to s that
meets I only at t. If there is some w 2 W I with DR that is not fully commutative,
then there is some w 0 2 W with DR (w 0 that is not fully commutative.
Proof. Let s be the given path in \Gamma, and suppose that w 2 W I is not
fully commutative and DR Every reduced word for
w ends with t. Furthermore, since s do not appear in w and s i does not commute
with s i+1 , it follows that the expression ws reduced, and every reduced word
for w 0 consists of a reduced word for w followed by (s fully
commutative and DR (w 0
not, then by Lemma 5.3 we can assume that there is a circuit of \Gamma
through s. Assuming that s are the vertices of a minimal circuit, so that s i
and s i+1 do not commute for 1 - i - n (subscripts taken modulo n), consider the word s
of ( ) and the corresponding w 2 W . In (2), we noted that DR (w) ae fs 1 ; s n g, and that
However in this case, s 1 and s n
do not commute, so DR fsg.
no vertex of degree -4, and at most one vertex of degree 3. Otherwise, by
following a path from s to a vertex of degree - 3, we can use Lemma 5.3 to reduce to
a configuration in which there are generators s that induce a subgraph of \Gamma
isomorphic to the one in Figure 3(b), with occurs when there is
a vertex of degree - 4.) In that case, consider
examining the heap of s and the equivalent word obtained by
applying the braid relation hs can see that s is a reduced word for
some w 2 W that is not fully commutative. Both heaps have a maximum element with
label fsg.
(5) Either W is of type A, or s is an end node. If \Gamma has a vertex of degree 3 and s has
degree - 2, then there is a configuration in \Gamma isomorphic to the one in (4). Otherwise,
\Gamma is a path. Assuming W 6= An and that s has degree 2, it follows that there is a path
In that case, consider
reasoning similar to (4), s is a reduced word for some w 2 W hsi
that is not fully commutative.
Since every maximal quotient of An is minuscule, for the remainder of the proof
we may assume that W is not of type A, and hence also that s is an end node of \Gamma.
have both a vertex of degree 3 and an edge of weight -4. Otherwise, by
following a path from s we will reach either a vertex of degree 3 or an edge of weight - 4.
If the former occurs first, then by Lemma 5.3, we can reduce to a configuration of the
type that was eliminated in (5). If the latter occurs, we can use Lemma 5.3 to reduce to a
configuration of generators s that induce a subgraph of \Gamma isomorphic to the
one in

Figure

3(b), with However in that case,
is a suitable reduced word for some w 2 W hsi that is not fully commutative.
\Gamma has at most one edge of weight -4. If \Gamma has two or more edges of weight - 4,
must be a path and s must be an end node, thanks to (5) and (6). By following
the path from s, we can use Lemma 5.3 to reduce to the case of a path
in \Gamma such that However in that case,
is a suitable reduced word for some w 2 W hsi that is not fully commutative.
In the following, we will continue to construct explicit reduced words for members of
W that are not fully commutative; however, in most of the remaining cases, the structure
of the commutativity and braid equivalence classes are sufficiently complex that it is
easier to deduce what is needed by examining heaps. More specifically, in (most of) the
remaining constructions, we present a pair of heaps, and it is left to the reader to check
the following: (i) Each heap has exactly one convex chain with alternating labels
of cardinality some pair of generators s (ii) The braid relation
applied to a linear extension of each heap, interchanges the
two heaps. (iii) Both heaps have a maximum element, and the label of this element
corresponds to s. These properties collectively imply that some w 2 W hsi has exactly two
commutativity classes and hence cannot be fully commutative.
An edge of weight -4 must be adjacent to an end node. Otherwise, by Lemma 5.3 we
can reduce to a case in which there is a path
we may also assume that m(s 3. However in that case, the pair of braid-related
heaps in Figure 10 prove the existence of some w 2 W hsi that is not fully commutative.
Suppose now that \Gamma is a path, say s . By (5), (7) and (8), we may assume
that weights are 3, and
W is a dihedral group (a case covered by (c)), so assume n - 3. We may also assume
nodes correspond to minuscule
quotients. If a member of W hsi that
is not fully commutative, so we can assume
and W case covered by (c)). If
is a member of W hsi that is not fully commutative. With Lemma 5.3, this eliminates all

Figure

11.

Figure

12.
cases with n - 3 and m - 6. Finally, if
the pair of braid-related heaps in Figure 11 prove the existence of some w 2 W hsi that is
not fully commutative. With Lemma 5.3, this eliminates all cases with n - 4 and
The only remaining possibility is that Figure 4), and that s is the
end node of (say) the branch of length p. Continuing the labeling established in Section 4,
we let s 0 denote the vertex of degree 3, and let s
r denote the
generators along the three branches of \Gamma. If
On the other hand, if q; r - 2, then the braid-related heaps in Figure 12 provide a member
of W J that is not fully commutative for the case hence we may also eliminate
5.3). For what remains, we may thus assume q - 2 and r = 1. Now if
then so we may further assume that p - 2. If q - 3,
then the heaps in Figure 13 provide a member of W J that is not fully commutative for
the case hence we may also eliminate p - 3 (again Lemma 5.3). Thus 2.
both of
which yield minuscule quotients. All that remains is p - 4, however in
that case, Lemma 5.3 and the heaps in Figure 14 prove that W J has members that are
not fully commutative.

Figure

13.

Figure

14.
6. Consequences for the Bruhat order
denote the set of (abstract) reflections in W . The
Bruhat order (e.g., [Bj], [H]) may be defined as the partial ordering -B on W generated
by the transitive closure of the relations
for all w We note that there is no distinction between a "left" and "right"
Bruhat order, since only if '(tw) ? '(w). It is also clear that
the Bruhat order refines both the left and right weak orders; i.e., x -LR y
all However, unlike the weak ordering, the fully commutative part of W and
the parabolic quotients W J need not be order ideals of (W; -B ).
In [P], Proctor classifies the parabolic quotients of finite Weyl groups whose Bruhat
orderings are lattices; aside from the minuscule quotients, the only other examples occur
in the case Also, it is implicit in [P] and explicit for the symmetric group
case in [Bj, (4.9)] that the Bruhat ordering and weak ordering of a minuscule quotient are
3 However in [P], Proctor also remarks without proof that among the finite Coxeter groups, the Bruhat
order on W J with (W; W J a lattice. Theorem 6.1 shows that this is incorrect.
identical. The following result characterizes the parabolic quotients of arbitrary Coxeter
groups with these properties.
Theorem 6.1. If W is irreducible and J is a proper subset of S, then the following
are equivalent.
(a) (W J ; -B ) is a lattice.
(b) (W J ; -B ) is a distributive lattice.
(c) (W J ; -L ) is a distributive lattice.
W J is minuscule, or (W; W J
Proof. First we show that each of the quotients listed in (e) satisfies properties (a)-(d).
In case W is a (possibly infinite) dihedral group and J is a singleton, it is easy to check
that (W J ; -L ) is a total order. In particular, it is a distributive lattice. Since the Bruhat
order refines the weak order, it follows that the two orders must coincide. Otherwise, in
the remaining cases W J is a quotient of a finite group, and thus (Proposition 1.6) has a
unique maximal element with respect to -L . By Theorem 5.1, every member (including
the top element) of W J is fully commutative, so by Theorem 2.2 it follows that (W J
is a distributive lattice. To prove that the remaining properties hold, it thus suffices to
show that the Bruhat order and weak order coincide on W J .
In case Theorem 2.2 implies that (W J ; -L ) is isomorphic to
the lattice of order ideals of the heap in Figure 9. One can see directly that this lattice has
exactly two incomparable elements; namely, w (using
the labels for generators introduced in Section 5). Since these two elements have the same
length, they must also be incomparable in the Bruhat order. Thus the two orders coincide
in this case.
Now consider the minuscule case. Continuing our previous notation, let E, \Delta, and \Phi
be as they were defined in Section 5, and let - be a minuscule weight with stabilizer W J .
Define r to be the linear functional on E satisfying
Lemma 6.2. For w 2 W J , we have
Proof. The case choose ff 2 \Delta so that
s ff w !L w. By Lemma 5.2, it follows that (w-; ff) ! 0, so by Exercise VI.1.24 in [B], we
have (w-; ff - and the result
follows by induction with respect to '(w).
Now let t 2 T , w 2 W be such that tw !B w is a covering relation. We have
some (positive) ff 2 \Phi. It is necessary that tw- 6= w-; otherwise, tw would be a shorter
member of the coset containing w. Therefore (w-; ff) 6= 0, and hence by the Bourbaki
exercise (ibid.), (w-; ff - It follows that
Lemma 6.2. However, the Bruhat order is graded by the length function (e.g., [H, x5.11]),
so the only covering relations involve pairs with a length difference of one. It follows that
so ff is a simple root and tw !L w. Thus every covering relation of the Bruhat
order is also a covering relation of the weak order, so the two coincide.
Turning to the converse, we show that if W J is any of the quotients not listed in (e),
then none of the properties (a)-(d) hold. By Theorem 5.1, there are two possibilities:
either W J contains elements that are not fully commutative, or W has rank - 3 and every
edge-weight of \Gamma is infinite.
Suppose that w 2 W J is not fully commutative. By replacing w with some w 0 !L w
if necessary, we can assume that there is a reduced expression of the form y,
where x 0 is the element of length m(s; t) in the parabolic subgroup generated by some
fs; tg ae S such that m(s; t) - 3. Consider the subinterval of (W J ; -L ) from y to w. By
Proposition 1.3, this interval is order-isomorphic to the weak ordering of the parabolic
subgroup generated by fs; tg (cf. Figure 1(a)). This interval is not a distributive lattice,
so (c) does not hold. (This fact is also an immediate consequence of Theorem 2.2, given
that W J contains elements that are not fully commutative.) Furthermore, with respect
to the Bruhat order, this interval contains additional relations, such as sy !B sty and
ty !B tsy (cf. Figure 1(b)), so (d) does not hold. Since we also have sy !B tsy and
ty !B sty, it follows that sy and ty have no least upper bound relative to the Bruhat
order, so and (a) and (b) do not hold.
The remaining possibility is that W has rank - 3 and every edge of \Gamma has infinite
weight. It follows that there must exist generators s; t; u 2 S such that s 62 J , and either
In case (1), consider the
elements uts, sts, suts, and usts. It is easy to see that every reduced word for these
elements ends with s, so they all belong to W J . Secondly, it is not hard to show, using
the subword property (e.g., [H, x5.10]) or otherwise, that the two elements of length four
are both upper bounds for the two elements of length three with respect to the Bruhat
order, so (a) and (b) do not hold. The fact that sts and suts are unrelated with respect
to the weak order shows that (d) does not hold. We also claim that the elements sts and
uts have no upper bounds relative to -L . By definition, the upper bounds for sts are the
reduced expressions of the form wsts. Since the only braid relations in W involve pairs
of commuting generators, it follows that every reduced word for wsts must have at least
two occurrences of s following any occurrence of u. In particular, no such reduced word
can end with (u; t; s), so wsts cannot be an upper bound for uts. Hence (W J ; -L ) is not
a lattice and (c) fails.
In case (2), consider the elements tuts, suts, tsuts, and stuts. Again, it is easy to see
that every reduced word for these elements ends with s, so they all belong to W J . Using
the subword property, one sees that both elements of length five are upper bounds for both
elements of length four with respect to the Bruhat order, so (a) and (b) fail. Also, tuts
and tsuts are unrelated with respect to -L , so (d) fails. Finally, we argue that tuts and
suts have no upper bounds relative to -L . Indeed, if wsuts is reduced, then every
reduced word for x must have exactly one t occurring between the last two occurrences
of s. In particular, no such reduced word can end with (t; u; t; s), so x cannot be an upper
bound for tuts. Hence (W J ; -L ) is not a lattice and (c) fails.



--R

Schubert polynomials for the classical groups
Some combinatorial properties of Schubert polynomials
Orderings of Coxeter groups
"Groupes et Alg'ebres de Lie, Chp. IV-VI,"
"Probl'emes Combinatoires de Commutation et R'ear- rangements,"
"Commutative Elements of a Weyl Group,"
A Hecke algebra quotient and some combinatorial applications
Combinatorial Bn
"Reflection Groups and Coxeter Groups,"
"B and D Analogues of Stable Schubert Polynomials and Related Insertion Algorithms,"
plane partition generating functions
"Enumerative Combinatorics, Vol. I,"
Some combinatorial aspects of reduced words in finite Coxeter groups
Heaps of pieces I: Basic definitions and combinatorial lemmas
--TR

--CTR
Debra J. Waugh, On quotients of Coxeter groups under the weak order, Advances in Applied Mathematics, v.30 n.1/2, p.369-384, January
R. M. Green, On rank functions for heaps, Journal of Combinatorial Theory Series A, v.102 n.2, p.411-424, May
Paola Cellini , Paolo Papi, A Root System Criterion for Fully Commutative and Short Braid-Avoiding Elements in Affine Weyl Groups, Journal of Algebraic Combinatorics: An International Journal, v.11 n.1, p.5-16, Jan. 2000
N. J. Wildberger, Minuscule posets from neighbourly graph sequences, European Journal of Combinatorics, v.24 n.6, p.741-757, August
John R. Stembridge, The Enumeration of Fully Commutative Elements of Coxeter Groups, Journal of Algebraic Combinatorics: An International Journal, v.7 n.3, p.291-320, May 1, 1998
John R. Stembridge, Quasi-Minuscule Quotients and Reduced Words for Reflections, Journal of Algebraic Combinatorics: An International Journal, v.13 n.3, p.275-293, May 2001
Robert A. Proctor, Dynkin Diagram Classification of -Minuscule Bruhat Latticesand of d-Complete Posets, Journal of Algebraic Combinatorics: An International Journal, v.9 n.1, p.61-94, Jan. 1999
R. M. Green, Acyclic Heaps of Pieces, I, Journal of Algebraic Combinatorics: An International Journal, v.19 n.2, p.173-196, March 2004
Jian-Yi Shi, Left cells containing a fully commutative element, Journal of Combinatorial Theory Series A, v.113 n.3, p.556-565, April 2006
R. M. Green, On 321-Avoiding Permutations in Affine Weyl Groups, Journal of Algebraic Combinatorics: An International Journal, v.15 n.3, p.241-252, May 2002
Sara C. Billey , Gregory S. Warrington, Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations, Journal of Algebraic Combinatorics: An International Journal, v.13 n.2, p.111-136, March 2001
coxeter group;weak order;reduced word;bruhat order