Shellability of noncrossing partition lattices

SHELLABILITY OF NONCROSSING PARTITION LATTICES CHRISTOS A. ATHANASIADIS, THOMAS BRADY, AND COLUM WATT Abstract. We give a case-free proof that the lattice of noncrossing partitions associated to any finite real reflection group is EL-shellable. Shellability of these lattices was open for the groups of type Dnand those of exceptional type and rank at least three. 1. Introduction Consider a finite real reflection group Wand the partial order on W defined by letting u¹vif there exists a shortest factorization of uas a product of reflections in Wwhich is a prefix of such a shortest factorization of v. This order turns Winto a graded poset having the identity 1 as its unique minimal element, where the rank of wis the length of a shortest factorization of winto reflections. For any w∈Wwe denote by NCW(w) the interval [1, w] in this partial order. We are primarily interested in the case that wis a Coxeter element γof W, viewed as a finite Coxeter group. Since all Coxeter elements of Ware conjugate to each other, the isomorphism type of the poset NCW(γ) is independent of γ. We denote this poset by NCWwhen the choice of the Coxeter element γis irrelevant and call NCW the noncrossing partition lattice associated to W. The poset NCWplays a crucial role in the construction of new monoid structures and K(π, 1) spaces for Artin groups associated with finite Coxeter groups; see for instance [3, 6, 7] and the survey articles [11, 12]. It is selfdual [3, Section 2.3], graded and has been verified case by case to be a lattice [3, Fact 2.3.1] [7, Section 4]. For Coxeter groups of types Aand B in the Cartan-Killing classification it is isomorphic to the classical lattice of noncrossing partitions of an n-element set, defined and studied by Kreweras [10], and to its type Banalogue, defined by Reiner [14], respectively. The Date: February 28, 2005. 1991 Mathematics Subject Classification. Primary 20F55; Secondary 05E15, 05E99, 06A07. Supported in part by the American Institute of Mathematics (AIM) and the NSF. 1 2 CHRISTOS A. ATHANASIADIS, THOMAS BRADY, AND COLUM WATT main purpose of the present article is to give a case-free proof of the following theorem. Theorem 1.1. The poset NCWis EL-shellable for any finite Coxeter group W. EL-shellability (see Section 2) for a bounded graded poset Pof rank r implies that the simplicial complex ∆( ¯ P) of chains in the proper part of Pis shellable. In particular it implies that the geometric realization of ∆( ¯ P) has the homotopy type of a wedge of (r−2)-dimensional spheres, the number of which is determined by the EL-labeling, and that the Stanley-Reisner ring of ∆( ¯ P) is Cohen-Macaulay over an arbitrary field. Theorem 1.1 was proved by Bj¨orner and Edelman [4, Example 2.9] in the case of Coxeter groups of type Aand by Reiner [14, Section 6] in the case of type Bwhile it was left open in [2, Section 7] in that of type D and was conjectured by Reiner [15] for all finite Coxeter groups. After introducing basic definitions, notation and some preliminary lemmas related to real reflection groups, root systems and shellability (Section 2) we proceed as follows. We give sufficient conditions on a total ordering of the set of reflections Tand a Coxeter element γof a crystallographic group Wfor the natural edge labeling of NCW(γ) with label set Tto be an EL-labeling (Theorem 3.5). We exploit these conditions to describe explicit families of EL-labelings in the cases of the classical reflection groups (Examples 3.3 and 3.4 and Corollary 3.12). The existence of a total ordering and Coxeter element for any Wwhich satisfy these sufficient conditions follows from recent work of the last two authors [8], where a case-free proof of the lattice property of NCWis given. The particular orderings and Coxeter elements considered there (see Section 4) were introduced by Steinberg [18] and play a crucial role in the constructions of [8]. It is shown in Section 4 (Theorem 4.2) that they provide EL-labelings of NCWfor any finite real reflection group (including the non-crystallographic ones). A result on the M¨obius function of NCWis deduced (Corollary 4.3). 2. Preliminaries Reflection groups and root systems. Let Wbe a finite real reflection group of rank `with a corresponding root system Φ, acting faithfully by orthogonal transformations on an `-dimensional Euclidean space Vwith inner product ( ,). Thus Wis generated by elements acting as orthogonal reflections in Vwhile Φ is invariant under the action of Wand consists of a pair {α, −α}of nonzero vectors for each reflection tin W, which are orthogonal to the reflecting hyperplane of t. We denote by Tthe set of all reflections in W, by Hαthe linear hyperplane in Vorthogonal to αand SHELLABILITY OF NONCROSSING PARTITION LATTICES 3 by tαthe orthogonal reflection in Hα. We refer the reader to the texts by Bj¨orner and Brenti [5] and Humphreys [9] for any undefined terminology and background on reflection groups and root systems. In particular we assume the notions of a positive system, simple system and simple reflection. A Coxeter element of Wis the product of the simple reflections in an arbitrary order for any choice of simple system for Φ. The order of any Coxeter element of Wis the Coxeter number, denoted by h. The root lattice QΦ is the Z-span of Φ. The root system Φ is called crystallographic and Wis called a Weyl group if Wpreserves QΦ. The next lemma follows from the results of Sommers in [16, Section 3] (see also [13, Lemma 2.3]). Lemma 2.1. ([16]) If α1, α2, . . . , αr∈Φand α1+α2+· · · +αr=α∈Φ then α1=αor there exists iwith 2≤i≤rsuch that α1+αi∈Φ∪ {0}. Proof. See [1, Lemma 2.1 (ii)]. ¤ Lemma 2.2. If {α1, α2, . . . , α`} ⊆ Φ+is a Z-basis of the root lattice QΦ and αi−αj/∈Φfor all i < j then {α1, α2, . . . , α`}is the set of simple roots in Φ+. Proof. It suffices to prove that any positive root α∈Φ+can be written as a linear combination of α1, α2, . . . , α`with nonnegative integer coefficients. Since {α1, α2, . . . , α`}is a Z-basis of the root lattice we can write uniquely α=r1α1+r2α2+···+r`α`for some integers ri. Let us rewrite this expression as α=β1+β2+· · · +βr where there are ricopies of αior −ricopies of −αiamong the β’s if ri≥0 or ri<0, respecively. To show that ri≥0 for 1 ≤i≤`we must show that βi∈Φ+for 1 ≤i≤r. Suppose that βiis a negative root for some i, say for i= 1. Since α∈Φ+at least one of the β’s is a positive root. By applying repeatedly Lemma 2.1 and reordering the β’s if necessary we may assume that there exists an index 2 ≤j≤rsuch that β1+β2+· · · +βi∈Φ for 1≤i < j,βj∈Φ+,βi∈ −Φ+for 1 ≤i < j and β1+β2+· · ·+βj∈Φ∪{0}. Since the α’s are linearly independent we must have β1+β2+· · · +βj∈Φ. Applying Lemma 2.1 once more we conclude that βi+βj∈Φ for some 1≤i<j, which means that αi−αj∈Φ for some i<j, contrary to the hypothesis. ¤ EL-labelings and shellability. Let (P, ≤) be a finite bounded graded poset (short for partially ordered set). Thus Phas a unique minimal and a unique maximal element, denoted ˆ 0 and ˆ 1 respectively, and all maximal (with respect to inclusion) chains in Phave the same length (one less than 4 CHRISTOS A. ATHANASIADIS, THOMAS BRADY, AND COLUM WATT their number of elements), called the rank of Pand denoted rank(P). Let E(P) be the set of covering relations of P, meaning pairs (x, y) of elements of Psuch that x<yholds in Pand x<z≤yholds only for z=y, and let Λ be a totally ordered set. An edge labeling of Pwith label set Λ is a map λ:E(P)→Λ. Let cbe an unrefinable chain x0< x1<··· < xr of elements of P, so that (xi−1, xi)∈ E(P) for all 1 ≤i≤r. We let λ(c)=(λ(x0, x1), λ(x1, x2), . . . , λ(xr−1, xr)) be the label of cwith respect to λand call crising or falling with respect to λif the entries of λ(c) strictly increase or weakly decrease, respectively, in the total order of Λ. We say that cis lexicographically smaller than an unrefinable chain c0in Pof the same length (with respect to λ) if λ(c) precedes λ(c0) in the lexicographic order induced by the total order of Λ. Definition 2.3. ([4]) An edge labeling λof Pis called an EL-labeling if for every non-singleton interval [u, v]in P (i) there is a unique rising maximal chain in [u, v]and (ii) this chain is lexicographically smallest among all maximal chains in [u, v] with respect to λ. The poset Pis called EL-shellable if it has an EL-labeling for some label set Λ. See [17, Chapter 3] for more background on partially ordered sets and EL- shellability. If Pis EL-shellable then the simplicial complex of chains (order complex) ∆( ¯ P) of the proper part ¯ P=P− {ˆ 0,ˆ 1}of Phas the homotopy type of a wedge of spheres of dimension rank(P)−2. The number of these spheres is equal to the number of falling maximal chains of Pwith respect to the EL-labeling and is also equal to the M¨obius number of P, up to the sign (−1)rank(P); see [17, Section 3.13]. Reflection length and the poset NCW(w).For w∈Wlet lT(w) denote the smallest ksuch that wcan be written as a product of kreflections in T. The partial order ¹on Wis defined by letting u¹vif and only if lT(u) + lT(u−1v) = lT(v), in other words if there exists a shortest factorization of uinto reflections in Twhich is a prefix of such a shortest factorization of v. With this order W is a graded poset having the identity 1 as its unique minimal element and rank function lT. We denote by F(w) the subspace of Vfixed by w. The next lemma follows from the results in [7, Section 2] (see also [3, Lemma 1.2.1]). Lemma 2.4. ([7]) Let w∈W. (i) lT(w) = `−dim F(w). SHELLABILITY OF NONCROSSING PARTITION LATTICES 5 (ii) For α∈Φ+we have tα¹wif and only if F(w)⊆Hα. The interval [1, w] in (W, ¹), denoted NCW(w), is also graded with rank function lTand has rank `= dim Vif wis a Coxeter element of W. 3. Reflection Orderings, Coxeter elements and EL-Labelings Let Wbe a finite real reflection group of rank `with corresponding root system Φ ⊂Vand set of reflections T. Let Φ+⊂Φ be a fixed choice of a positive system. A total ordering <of Tis called a reflection ordering for W[5, Section 5.1] if whenever α, α1, α2∈Φ+are distinct roots and αis a positive linear combination of α1and α2we have either tα1< tα< tα2 or tα2< tα< tα1. An induced subsystem of Φ of rank iis the intersection Φ0of Φ with the linear span of ilinearly independent roots in Φ. The set Φ0is a root system on its own and Φ0∩Φ+is a choice of a positive system for Φ0. The following is the main definition in this section. Definition 3.1. A reflection ordering <of Tis compatible with a Coxeter element γof Wif for any irreducible rank 2 induced subsystem Φ0⊆Φthe following holds: if αand βare the simple roots of Φ0with respect to Φ0∩Φ+ and tαtβ∈NCW(γ)then tα< tβ. Observe that a rank 2 subsystem Φ0⊆Φ is irreducible if and only if Φ0∩Φ+has at least three roots. Example 3.2. Let Wbe of rank 2, so that Wis a dihedral group of order 2mfor some m≥2. Let αand βbe the two simple roots in Φ. There are mreflections in W, namely t1, t2, . . . , tmwhere ti=tα(tβtα)i−1(so t1=tα and tm=tβ) and two reflection orderings, namely t1< t2<· · · < tm and its reverse. The reflection ordering <is compatible with the Coxeter element γ=tαtβ. The poset NCW(γ) has mmaximal chains corresponding to the mshortest factorizations γ=t1tm=t2t1=· · · =tmtm−1of γinto reflections. Clearly the chain corresponding to the factorization γ=t1tmis the unique rising maximal chain and the lexicographically smallest maximal chain in the edge labeling of NCW(γ) which assigns the label (ti, tj) to the chain corresponding to a factorization γ=titj, when the label set Tis totally ordered by <.¤ Example 3.3. Let Wbe of type An−1and Φ+={ei−ej: 1 ≤i < j ≤n} be the set of positive roots. Thus Wis isomorphic to the symmetric group 6 CHRISTOS A. ATHANASIADIS, THOMAS BRADY, AND COLUM WATT of permutations of the set {1,2, . . . , n}and the reflections correspond to the transpositions (i, j) for 1 ≤i < j ≤n. If the n-cycle γ= (1,2, . . . , n) is chosen as the Coxeter element for Wthen there is a canonical isomorphism of NCW(γ) with the classical lattice of noncrossing partitions of {1,2, . . . , n} (see for instance [3, Section 4] or [6, Section 3]). One can easily check that any total ordering on the set of transpositions (i, j), where 1 ≤i < j ≤n, for which (i, j)<(i, k)<(j, k) for 1 ≤i < j < k ≤n(such as the lexicographic ordering) induces a reflection ordering for Wwhich is compatible with γ.¤ Example 3.4. Let Wbe of type Bnor Dnand Φ+=({ei: 1 ≤i≤n} ∪ {ei±ej: 1 ≤i < j ≤n},for Wof type Bn {ei±ej: 1 ≤i < j ≤n},for Wof type Dn be the set of positive roots. In what follows we use the notation of [7, Section 3] (and [2, Section 2]) to represent elements of Was certain permutations of the set {1,2, . . . , n, −1,−2, . . . , −n}, so that ((i1, i2, . . . , ik)) stands for the product of cycles (i1, i2, . . . , ik)(−i1,−i2, . . . , −ik) and [i1, i2, . . . , ik] for the ballanced cycle (i1, i2, . . . , ik,−i1,−i2, . . . , −ik). If γ=([1,2, . . . , n],for Wof type Bn [1,2, . . . , n −1] [n],for Wof type Dn is chosen as the Coxeter element of Wthen there is a canonical isomorphism of NCW(γ) with Reiner’s Bnanalogue [14] of the lattice of noncrossing partitions of {1,2, . . . , n}(see [3, Section 4] or [7, Section 3]) if Wis of type Bn, and an explicit combinatorial description of NCW(γ) in terms of planar noncrossing diagrams [2, Section 3] if Wis of type Dn. One can check directly that in the case of type Bnany total ordering on the set of signed transpositions ((i, j)) and ((i, −j)) for 1 ≤i < j ≤nand [i] = (i, −i) for 1 ≤i≤nfor which ((i, j)) <((i, k)) <((j, k)) for 1 ≤i < j < k ≤n ((i, j)) <((i, −k)) <((j, −k)) for 1 ≤i < j ≤nand 1≤k<i or j <k≤n ((i, j)) <[i]<((i, −j)) <[j] for 1 ≤i < j ≤n, such as the ordering ((1,2)) <((1,3)) <···<((1, n)) <((2,3)) <· · · <((n−1, n)) < [1] <((1,−2)) <((1,−3)) <· · · <((1,−n)) < <[2] <((2,−3)) <· · · <((2,−n)) < · · · <[n−1] <((n−1,−n)) <[n], SHELLABILITY OF NONCROSSING PARTITION LATTICES 7 induces a reflection ordering for Wwhich is compatible with γ. Similarly in the case of type Dnany total ordering on the set of signed transpositions ((i, j)) and ((i, −j)) for 1 ≤i < j ≤nfor which ((i, j)) <((i, k)) <((j, k)) for 1 ≤i < j < k ≤n ((i, j)) <((i, −k)) <((j, −k)) for 1 ≤i < j ≤n−1 and 1 ≤k < i or j < k ≤n ((i, ±n)) <((i, −j)) <((j, ±n)) for 1 ≤i < j ≤n−1, such as the ordering ((1,2)) <((1,3)) <· · · <((1, n −1)) <((2,3)) <· · · <((n−2, n −1)) < ((1, n)) <((1,−n)) <((1,−2)) <((1,−3)) <···<((1,−(n−1))) < ((2, n)) <((2,−n)) <((2,−3)) <···<((2,−(n−1))) < · · · <((n−1, n)) <((n−1,−n)), induces a reflection ordering for Wwhich is compatible with γ.¤ Let γbe a Coxeter element of W. Any covering relation in NCW(γ) is of the form (u, v) with u−1v∈T. Setting λ(u, v) = u−1vfor any such covering relation defines an edge labeling λof NCW(γ) with label set Twhich we call the natural edge labeling of NCW(γ). Part (ii) of the following theorem is the main result of this section. Theorem 3.5. Let Wbe a finite real reflection group with set of reflections Tand Coxeter element γand let λbe the natural edge labeling of NCW(γ). (i) For any total ordering of Tand any non-singleton interval [u, v]in NCW(γ)there is a unique lexicographically smallest maximal chain in [u, v]and this chain is rising with respect to λ. (ii) If Tis totally ordered by a reflection ordering which is compatible with γand Wis a Weyl group then λis an EL-labeling. We first need to establish a few lemmas. For any interval [u, v] in NCW(γ) we denote by λ([u, v]) the set of natural labels of all maximal chains in [u, v], with the convention that λ([u, v]) = {∅} if u=v, and abbreviate λ([1, w]) as λ(w). Lemma 3.6. Let [u, v]be a non-singleton interval in NCW(γ). (i) If [u, v]has length two and (s, t)∈λ([u, v]) then (t, s0)∈λ([u, v]) for some s0∈T. (ii) It t∈Tappears in some coordinate of an element of λ([u, v]) then t=λ(u, u0)for some covering relation (u, u0)in [u, v]. (iii) The reflections appearing as the coordinates of an element of λ([u, v]) are pairwise distinct. 8 CHRISTOS A. ATHANASIADIS, THOMAS BRADY, AND COLUM WATT Proof. Part (i) is clear since Tis closed under conjugation, so that s0=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 non-singleton interval in NCW(γ)and let w= u−1v. There is a poset isomorphism f: [1, w]→[u, v]such that λ(x, y) = λ(f(x), f(y)) for all covering relations (x, y)in [1, w]. Proof. It follows immediately from the definitions that the map f: [1, w]→ [u, v] with f(x) = ux for x∈[1, w] is well defined and has the desired properties. ¤ Recall that a parabolic Coxeter element in Wis a Coxeter element win a parabolic subgroup of W, meaning a subgroup generated by a subset of a set of Coxeter generators of W. This subgroup, denoted Ww, depends only on wand contains all reflections t¹w(see [3, Corollary 1.6.2]). Lemma 3.8. ([3, Lemma 1.4.3]) Let w∈W. There exists a Coxeter element γof Wwith w¹γif and only if wis a parabolic Coxeter element. ¤ Lemma 3.9. If w¹γfor some Coxeter element γof Wthen any reflection ordering for Wwhich is compatible with γrestricts to a reflection ordering for Wwwhich is compatible with w. Proof. We may assume that whas rank at least two in NCW(γ). Let Φw⊆ Φ be the root system corresponding to Ww. We first check that if Φ0 wis an induced rank 2 subsystem of Φwand Φ0=RΦ0 w∩Φ is the corresponding induced rank 2 subsystem of Φ then Φ0 w= Φ0. Clearly Φ0 w⊆Φ0. Let αand βbe the two simple roots of Φ0 wand let α0∈Φ0. To show that α0∈Φ0 w note that Hα∩Hβ⊂Hα0and hence F(w)⊂Hα0. It follows from Lemma 2.4 (ii) that tα0¹wand hence that tα0∈Ww, in other words that α0∈Φ0 w. To conclude the proof suppose that Φ0 wis irreducible and that tαtβ¹w. From w¹γwe conclude that tαtβ¹γ. Since Φ0 w= Φ0and the reflection ordering on Tis compatible with γ,tαmust preceed tβin this ordering. ¤ Recall also from [3, Section 1.5] that the Artin group B`of type A`−1 acts on the set of shortest factorizations of γinto reflections or, equivalently, on the set λ(γ). More precisely, the ith generator of B`acts on (t1, t2, . . . , t`)∈λ(γ) by replacing the pair (ti, ti+1) by (titi+1ti, ti) while leaving other coordinates of λ(γ) fixed. Lemma 3.10. The action of B`on the set of shortest factorizations of γ into reflections is transitive. Proof. See Proposition 1.6.1 in [3]. ¤ SHELLABILITY OF NONCROSSING PARTITION LATTICES 9 Lemma 3.11. Let tα1tα2· · · tα`be a shortest factorization of a Coxeter element of Winto reflections. (i) {α1, α2, . . . , α`}is a linear basis of V. (ii) If Wis a Weyl group then {α1, α2, . . . , α`}is a Z-basis of the root lattice QΦ. Proof. Part (i) is follows from the fact that Coxeter elements have trivial fixed space in V. The conclusion of part (ii) is clear for a shortest factorization of the Coxeter element into simple reflections. In view of Lemma 3.10 it suffices to show that if two shortest factorizations tα1tα2· · · tα`and tβ1tβ2· · · tβ`are related by the action of a single generator of the Artin group B`then {α1, α2, . . . , α`}is a Z-basis of QΦif and only if the same is true for {β1, β2, . . . , β`}. We may thus assume that there exists an index 1≤i < ` such that αj=βjfor j6=i, i + 1, βi+1 =αiand tβi=tαitαi+1 tαi. The last equality implies that ±βi=tαi(αi+1) = αi+1 −2(αi, αi+1) (αi, αi)αi and the claim follows since 2(αi, αi+1)/(αi, αi)∈Z.¤ Proof of Theorem 3.5. In what follows we will write NCWinstead of NCW(γ). (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, u0) 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 tand equal to the label of a covering relation (u, u0) in [u, v]. (ii) Let <γbe the reflection ordering of Twhich is compatible with the Coxeter element γof W. In view of part (i) it remains to show that there is at most one rising maximal chain in a non-singleton interval [u, v] with respect to λ. In view of Lemma 3.7 it suffices to prove this for an interval of the form [1, w] in NCW. Since w¹γ, by Lemma 3.8 wis a parabolic Coxeter element in W. By Lemma 3.9 the restriction of <γon the set of reflections of the parabolic subgroup Wwis a reflection ordering which is compatible with w. Hence we may as well assume that w=γ, so that [1, w] is the entire poset NCW= NCW(γ). Clearly there is at most one rising maximal chain in NCWwhose label is a permutation of the set Sof simple reflections. Hence it suffices to show that a maximal chain cin NCW