Printer Friendly

On the topology of the Cambrian semilattices (extended abstract).

1 Introduction

In [6, Theorem 9.6] Anders Bjorner and Michelle Wachs showed that the Tamari lattice [T.sub.n], introduced in [17], can be regarded as the subposet of the weak-order lattice on the symmetric group [G.sub.n], consisting of 312-avoiding permutations. More precisely, there exists a lattice homomorphism [sigma]: [G.sub.n] [right arrow] [T.sub.n] such that [T.sub.n] is isomorphic to the subposet of the weak-order lattice on [G.sub.n] consisting of the bottom elements in the fibers of [sigma]. In [13], the map a was realized as a map from [G.sub.n] to the triangulations of an (n + 2)-gon, where the partial order on the latter is given by diagonal flips. It was shown that the fibers of a induce a congruence relation on the weak-order lattice on [G.sub.n], and that the Tamari lattice is isomorphic to the lattice quotient induced by this congruence. Moreover, it was observed that different embeddings of the (n + 2)-gon in the plane yield different lattice quotients of the weak-order lattice on [G.sub.n]. The realization of [G.sub.n] as the Coxeter group [A.sub.n-1] was then used to connect the embedding of the (n + 2)-gon in the plane with a Coxeter element of [A.sub.n-1]. This connection eventually led to the definition of Cambrian lattices, which can analogously be defined for an arbitrary finite Coxeter group W as lattice quotients of the weak-order lattice on W with respect to certain lattice congruences induced by orientations of the Coxeter diagram of W, see [14].

In [15], Nathan Reading and David Speyer generalized the idea of Cambrian lattices to infinite Coxeter groups. Since there exists no longest element in an infinite Coxeter group, the weak order constitutes only a (meet)-semilattice. Using the realization of the Cambrian lattices in terms of Coxeter-sortable elements, which was first described in [14] and later extended in [15], the analogous construction as in the finite case yields a quotient semilattice of the weak-order semilattice, the so-called Cambrian semilattice.

This article is dedicated to the investigation of the topological properties of the order complex of the proper part of closed intervals in a Cambrian semilattice. One (order-theoretic) tool to investigate these properties is EL-shellability, which was introduced in [1], and further developed in [4, 5, 6]. The fact that a poset is EL-shellable implies a number of properties of the associated order complex: this order complex is Cohen-Macaulay, it is homotopy equivalent to a wedge of spheres and the dimensions of its homology groups can be computed from the labeling. The main results of the present article are the following.

Theorem 1.1 Every closed interval in [C.sub.[gamma]] is EL-shellable for every (possibly infinite) Coxeter group W and every Coxeter element [gamma] [member of] W.

We prove this result uniformly using the realization of CY in terms of Coxeter- sortable elements, and thus our proof does not require W to be finite or even crystallographic. For finite crystallographic Coxeter groups, Theorem 1.1 is implied by [9, Theorem 4.17]. Colin Ingalls and Hugh Thomas considered in [9] the category of finite dimensional representations of an orientation of the Coxeter diagram of a finite crystallographic Coxeter group W. However, their approach cannot be applied to non-crystallographic or to infinite Coxeter groups. Recently, Vincent Pilaud and Christian Stump gave a proof of Theorem 1.1 for finite Coxeter groups, by investigating increasing flip posets of certain subword complexes, see [11].

Finally, using the fact that every closed interval of [C.sub.[gamma]] is EL- shellable, we are able to determine the homotopy type of the proper parts of these intervals by counting the number of falling chains with respect to our labeling. It turns out that every open interval is either contractible or spherical, i.e. homotopy equivalent to a sphere. We can further characterize which intervals of [C.sub.[gamma]] are contractible and which are spherical, as our second main result shows. Recall that a closed interval [x, y] in a lattice is called nuclear if y is the join of atoms of [x, y].

Theorem 1.2 Let W be a (possibly infinite) Coxeter group and let [gamma] [member of] W be a Coxeter element. Every finite open interval in the Cambrian semilattice [C.sub.[gamma]] is either contractible or spherical. Furthermore, a finite open interval [(x, y).sub.[gamma]] is spherical if and only if the corresponding closed interval [x, y][gamma] is nuclear.

For finite Coxeter groups, Theorem 1.2 is implied by concatenating [12, Theorem 1.1] and [12, Propositions 5.6 and 5.7]. Nathan Reading's approach in the cited article was to investigate fan posets of central hyperplane arrangements. He then showed that for a finite Coxeter group W the Cambrian lattices can be viewed as fan posets of a fan induced by certain regions of the Coxeter arrangement of W which are determined by orientations of the Coxeter diagram of W. The tools Nathan Reading developed in [12] apply to a much larger class of fan posets, but cannot be applied directly to infinite Coxeter groups.

The proofs of Theorems 1.1 and 1.2 are obtained completely within the framework of Coxeter-sortable elements and thus have the advantage that they are uniform and direct.

This article is organized as follows. In Section 2, we recall the necessary order-theoretic concepts, as well as the definition of EL-shellability. Furthermore, we recall the definition of Coxeter groups, and the construction of the Cambrian semilattices. In Section 3, we define a labeling of the Hasse diagram of a Cambrian semilattice and give a case-free proof that this labeling is indeed an EL-labeling for every closed interval of this semilattice, thus proving Theorem 1.1. In Section 4, we prove Theorem 1.2, by counting the falling maximal chains with respect to our labeling and by applying [5, Theorem 5.9] which relates the number of falling maximal chains in a poset to the homotopy type of the corresponding order complex. The characterization of the spherical intervals of [C.sub.[gamma]] follows from Theorem 4.3.

The present article is an extended abstract of [10], and we have thus omitted most of the proofs and some illustrating examples. They can be found at the corresponding places in the original article.

2 Preliminaries

In this section, we recall the necessary definitions, which are used throughout the article. For further background on posets, we refer to [7] or to [16] where in addition some background on lattices and lattice congruences is provided. An introduction to poset topology can be found in either [2] or [18]. For more background on Coxeter groups, we refer to [3] and [8].

2.1 Posets and EL-Shellability

Let (P, [[less than or equal to].sub.P]) be a finite partially ordered set (poset for short). We say that P is bounded if it has a unique minimal and a unique maximal element, which we usually denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. For x, y G P, we say that y covers x (and write x [[??].sub.P] y)if x [[less than or equal to].sub.P] y and there is no z [member of] P such that x [<.sub.P] z [<.sub.P] y. We denote the set of all covering relations of P by E(P). For x, y [member of] P with x [[less than or equal to].sub.P] y, we define the closed interval [x, y] to be the set {z [member of] P | x [[less than or equal to] .sub.P] z [[less than or equal to].sub.P] y}. Similarly, we define the open interval (x, y) = {z [member of] P | x [<.sub.P] z [<.sub.P] y}. A chain c : x = [p.sub.0] [[less than or equal to].sub.P] [p.sub.1] [[less than or equal to].sub.P] ... [[less than or equal to].sub.P] [p.sub.s] = y is called maximal if ([p.sub.i], [p.sub.i+1]) [member of] E(P) for every 0 [less than or equal to] i [less than or equal to] s - 1. Let (P, [[less than or equal to].sub.P]) be a bounded poset and let c : [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a maximal chain of P. Given another poset ([LAMBDA], [[less than or equal to].sub.[LAMBDA]]), a map [lambda]: E(P) [right arrow] [LAMBDA] is called edge-labeling of P. We denote the sequence ([lambda]([p.sub.0], [p.sub.1]), [lambda]([p.sub.1], [p.sub.2]), ..., [lambda]([p.sub.s-1], [p.sub.s])) of edge-labels of c by [lambda](c). The chain c is called rising (respectively falling) if [lambda](c) is a strictly increasing (respectively weakly decreasing) sequence. For two words ([p.sub.1], [p.sub.2], ..., [p.sub.s]) and ([q.sub.1], [q.sub.2], ..., [q.sub.t]) in the alphabet A, we write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if either

[p.sub.i] = [q.sub.i], for 1 [less than or equal to] i [less than or equal to] s and s [less than or equal to] t, or

[p.sub.i] [<.sub.[LAMBDA]] [q.sub.i], for the least i such that [p.sub.i] [not equal to] [q.sub.i].

A maximal chain c of P is called lexicographically first among all maximal chains of P if for every other maximal chain c' of P we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. An edge-labeling of P is called EL-labeling if for every closed interval [x, y] in P there exists a unique rising maximal chain which is lexicographically first among all maximal chains in [x, y]. A bounded poset that admits an EL-labeling is called EL-shellable. Finally, we recall that the Mobius function [mu] of P is the map [mu]: P x P [right arrow] Z defined recursively by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A remarkable property of EL-shellable posets is that we can compute the value of the Mobius function for every closed interval of P from the labeling, as is stated in the following proposition (i).

Proposition 2.1 ([5, Proposition 5.7]) Let (P, [[less than or equal to].sub.P]) be an EL-shellable poset, and let x, y [member of] P with x [[less than or equal to].sub.P] y. Then,

[mu](x, y) = number of even length falling maximal chains in [x, y]

- number of odd length falling maximal chains in [x, y].

2.2 Coxeter Groups and Weak Order

Let W be a (possibly infinite) group, which is generated by the finite set S = {[s.sub.1], [s.sub.2], ..., [s.sub.n]}. Let m = [([m.sub.i,j]).sub.1[less than or equal to]i,j[less than or equal to]n] be a symmetric (n x n)-matrix, where the entries are either positive integers or the formal symbol [infinity], and which satisfies [m.sub.i,i] = 1 for all 1 [less than or equal to] i [less than or equal to] n, and [m.sub.i,j] [greater than or equal to] 2 otherwise. (We use the convention that [infinity] is formally larger than any natural number.) We call W a Coxeter group if it has the presentation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [epsilon] [member of] W denotes the identity. We interpret the case [m.sub.i,j] = [infinity] as stating that there is no relation between the generators [s.sub.i] and [s.sub.j], and we call the matrix m the Coxeter matrix of W. The Coxeter diagram of W is the graph G = (V, E), with V = S and E = {{[s.sub.i], [s.sub.j]} | [m.sub.i,j] [greater than or equal to] 3}. In addition, an edge {[s.sub.i], [s.sub.j]} of G is labeled by the value miij if and only if miij > 4.

Since S is a generating set of W, we can write every element w [member of] W as a product of the elements in S, and we call such a word a reduced word for w if it has minimal length. More precisely, define the word length on W (with respect to S) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [l.sub.S](w) = k, then every product of k generators which yields w is a reduced word for w. Define the (right) weak order of W by

u [[less than or equal to].sub.S] [upsilon] if and only if [l.sub.S]([upsilon]) = [l.sub.S](u) + [l.sub.S]([u.sup.-1][upsilon]).

The poset (W, [[less than or equal to].sub.S]) is a graded meet-semilattice, the so-called weak-order semilattice of W, and [l.sub.S] is its rank function. Further, (W, [[less than or equal to].sub.S]) is finitary meaning that every closed interval of (W, [[less than or equal to].sub.S]) is finite. In the case where the group W is finite, there exists a unique longest word [w.sub.o] of W, and (W, [[less than or equal to].sub.S]) is a lattice.

2.3 Coxeter-Sortable Words

Let [gamma] = [s.sub.1][s.sub.2] ... [s.sub.n] [member of] W be a Coxeter element, and define the half-infinite word

[[gamma].sup.[infinity]] = [s.sub.1][s.sub.2] ... [s.sub.n] [absolute value of [s.sub.1][s.sub.2] ... [s.sub.n]] ...

The vertical bars in the representation of [[gamma].sup.[infinity]] are "dividers", which have no influence on the structure of the word, but shall serve for a better readability. Clearly, every reduced word for w [member of] W can be considered as a subword of [[gamma].sup.[infinity]]. Among all reduced words for w, there is a unique reduced word, which is lexicographically first as a subword of [[gamma].sup.[infinity]]. This reduced word is called the [gamma]-sorting word of w.

Example 2.2 Consider the Coxeter group W = [G.sub.5], generated by S = {[s.sub.1], [s.sub.2], [s.sub.3], [s.sub.4]}, where si corresponds to the transposition (i, i + 1) for all i [member of] {1, 2, 3, 4} and let [gamma] = [s.sub.1][s.sub.2][s.sub.3][s.sub.4]. Clearly, [s.sub.1] and [s.sub.4] commute. Hence, [w.sub.1] = [s.sub.1][s.sub.2][absolute value of [s.sub.1][s.sub.4] and [w.sub.2] = [s.sub.1][s.sub.2] [s.sub.4]][s.sub.1] are reduced words for the same element w [member of] W. Considering [w.sub.1] and [w.sub.2] as subwords of [[gamma].sup.[infinity]], we find that [w.sub.2] is a lexicographically smaller subword of 700 than wi is. There are six other reduced words for w, namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is easy to see that among these [w.sub.2] is the lexicographically first subword of [[gamma].sup.[infinity]], and hence [w.sub.2] is the [gamma]-sorting word of w.

In the following, we consider only [gamma]-sorting words, and write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)

where [[delta].sub.i,j] [member of] {0, 1} for 1 [less than or equal to] i [less than or equal to] l and 1 [less than or equal to] j [less than or equal to] n. For each i [member of] {1, 2, ..., l}, we say that

[b.sub.i] = {[s.sub.j] | [[delta].sub.i,j] = 1} [subset or equal to] S

is the i-th block of w. We consider the blocks of w sometimes as sets and sometimes as subwords of [gamma], depending on how much structure we need. We say that w is [gamma]- sortable if and only if [b.sub.1] [contains or equal to] [b.sub.2] [contains or equal to] ... [contains or equal to] [b.sub.l]. In the previous example, we have seen that [w.sub.2] = [s.sub.1][s.sub.2][s.sub.4] | [s.sub.1] is a [gamma]-sorting word in W with [b.sub.1] = {[s.sub.1], [s.sub.2], [s.sub.4]} and [b.sub.2] = {[s.sub.1]}. Since [b.sub.2] [subset or equal to] [b.sub.1], we see that [w.sub.2] is indeed [gamma]-sortable.

By definition, the set of [gamma]-sortable words of W does not depend on the choice of the reduced word for [gamma]. Furthermore, the [gamma]-sortable words of W are characterized by a recursive property which we will describe next. A generator s [member of] S is called initial in [gamma] if it is the first letter in some reduced word for [gamma]. For some subset J [subset or equal to] S, we denote by [W.sub.J] the parabolic subgroup of W generated by the set J, and for s [member of] S we abbreviate <s> = S\{s}. For w [member of] W, and J [subset or equal to] S, we denote by [w.sub.J] the restriction of w to the parabolic subgroup [W.sub.J].

Proposition 2.3 ([15, Proposition 2.29]) Let W be a Coxeter group, [gamma] a Coxeter element and let s be initial in [gamma]. Then an element w [member of] W is [gamma]-sortable if and only if

(i) s [[less than or equal to].sub.S] w and sw is s[gamma]s-sortable, or

(ii) s [[not less than or equal to].sub.S] w and w is an s[gamma]-sortable word of [W.sub.<s>].

2.4 Cambrian Semilattices

In [15, Section 7] the Cambrian semilattice [C.sub.[gamma]] was defined as the sub-semilattice of the weak order on W consisting of all [gamma]-sortable elements. That [C.sub.[gamma]] is well- defined follows from [15, Theorem 7.1]. It turns out that [C.sub.[gamma]] is not only a sub-semilattice of the weak order, but also a quotient semilattice. The key role in the proof of this property is played by the projection [[pi].sup.[gamma].sub.[down arrow]] which maps every word w [member of] W to the unique largest [gamma]-sortable element below w. More precisely if s is initial in [gamma], then define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)

and set [[pi].sup.[gamma].sub.[down arrow]]([epsilon]) = [epsilon], see [15, Section 6].

Theorem 7.3 in [15] implies that [[pi].sup.[gamma].sub.[down arrow]] is a semilattice homomorphism from the weak-order semilattice on W to [C.sub.[gamma]], and [C.sub.[gamma]] can be considered as the quotient semilattice of the weak order modulo the semilattice congruence [[theta].sub.[gamma]] induced by the fibers of [[pi].sup.[gamma].sub.[down arrow]]. This semilattice congruence is called Cambrian congruence. Since the lack of a maximal element is the only obstruction for the weak order to be a lattice, it follows immediately that the restriction of [[pi].sup.[gamma].sub.[down arrow]] (and hence [[theta].sub.[gamma]]) to closed intervals of the weak order yields a lattice homomorphism (and hence a lattice congruence).

In the remainder of this article, we switch frequently between the weak-order semilattice on W and the Cambrian semilattice [C.sub.[gamma]]. In order to point out properly which semilattice we consider, we denote the order relation of the weak-order semilattice by [[less than or equal to].sub.S], and the order relation of [C.sub.[gamma]] by [[less than or equal to].sub.[gamma]]. Analogously, we denote a closed (respectively open) interval in the weak-order semilattice by [[u, [upsilon]].sub.s] (respectively [(u, [upsilon]).sub.S]), and a closed (respectively open) interval in [C.sub.[gamma]] by [[u, [upsilon]].sub.[gamma]] (respectively [(u, [upsilon]).sub.[gamma]]).

3 EL-Shellability of the Closed Intervals in [C.sub.[gamma]]

In this section, we define an edge-labeling of [C.sub.[gamma]], discuss some of its properties and eventually prove Theorem 1.1.

3.1 The Labeling

Define for every w [member of] W the set of positions of the [gamma]-sorting word of w as

[[alpha].sub.[gamma]](w) = {(i - 1) x n + j | [[delta].sub.i,j] = 1} [subset or equal to] n,

where the [[delta].sub.i,j]'s are the exponents from (1). We remark that the set of positions of w depends not only on the choice of the Coxeter element [gamma], but also on the choice of the reduced word of [gamma].

Example 3.1 Let W = [G.sub.4], [gamma] = [s.sub.1][s.sub.2][s.sub.3] and consider u = [s.sub.1][s.sub.2][s.sub.3] | [s.sub.2], and v = [s.sub.2][s.sub.3][absolute value of [s.sub.2]][s.sub.1]. Then, [[alpha].sub.[gamma]]([upsilon]) = {1, 2, 3, 5}, and [[alpha].sub.[gamma]]([upsilon]) = {2, 3, 5, 7}, where u [member of] [C.sub.[gamma]], while [upsilon] [not member of] [C.sub.[gamma]].

It is not hard to see that an element w [member of] W lies in [C.sub.[gamma]] if and only if the following holds: if i [member of] [[alpha].sub.[gamma]](w) and i > n, then i - n [member of] [[alpha].sub.[gamma]](w). In the previous example, we see that [[alpha].sub.[gamma]](u) contains both 5 and 2, while [[alpha].sub.[gamma]](v) does not contain 7 - 3 = 4.

Lemma 3.2 Let u, [upsilon] [member of] W with u [[less than or equal to].sub.S] [upsilon]. Then [[alpha].sub.[gamma]](u) is a subset of [[alpha].sub.[gamma]]([upsilon]). Denote by e (CY) the set of covering relations of CY, and define an edge- labeling of CY by

[[lambda].sub.[gamma]]: E(CY) [right arrow] N, (u, [upsilon]) [??] min{i | i [member of] [[alpha].sub.[gamma]]([upsilon])\[[alpha].sub.[gamma]](u)}. (3)

Figure 1 shows the Hasse diagram of a Cambrian lattice [C.sub.[gamma]] of the Coxeter group [A.sub.3], together with the labels defined by the map [[lambda].sub.[gamma]].

3.2 Properties of the Labeling

We notice that the definition of [[lambda].sub.[gamma]] depends on a specific reduced word for [gamma]. The following lemma shows that the structural properties of [[lambda].sub.[gamma]] are independent of the choice of reduced word for [gamma].

Lemma 3.3 Let 7 [gamma] [member of] W be a Coxeter element, and let u, [upsilon] [member of] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon]. The number of maximal falling and rising chains in [[u, [upsilon]].sub.[gamma]] does not depend on the choice of a reduced word for [gamma].

Whenever we use an initial letter s of [gamma] in the remainder of this article, we consider [[lambda].sub.[gamma]] with respect to a fixed reduced word for [gamma] which has s as its first letter. The previous lemma implies that this can be done without loss of generality.

Lemma 3.4 Let [C.sub.[gamma]] be a Cambrian semilattice, and let u, [upsilon] [member of] [C.sub.[gamma]] such that u [[less than or equal to].sub.[gamma]] [upsilon]. Let [i.sub.0] = min{i | i [member of] [[alpha].sub.[gamma]]([upsilon])\[[alpha].sub.[gamma]](u)}. Then the following hold.

(i) The label [i.sub.0] appears in every maximal chain of the interval [[u, [upsilon]].sub.[gamma]].

(ii) The labels of a maximal chain in [[u, [upsilon]].sub.[gamma]] are distinct.

The [gamma]-sortable words of W are defined recursively as described in Proposition 2.3. Thus we need to investigate how our labeling behaves with respect to this recursion.

Lemma 3.5 Let W be a Coxeter group and let [gamma] [member of] W be a Coxeter element. For u, [upsilon] [member of] [C.sub.[gamma]] with u [[??].sub.[gamma]] [upsilon] and for s [member of] S initial in [gamma], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.3 Proof of Theorem 1.1

We will prove Theorem 1.1 by showing that the map [[lambda].sub.[gamma]] defined in (3) is an EL-labeling for every closed interval in [C.sub.[gamma]]. In particular we show the following.

Theorem 3.6 Let u, [upsilon] [member of] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon]. Then the map [[lambda].sub.[gamma]] defined in (3) is an EL-labeling for [[u, [upsilon]].sub.[gamma]].

We notice in view of Lemma 3.3 that the statement of Theorem 3.6 does not depend on a reduced word for [gamma], even though our labeling does. For the proof of Theorem 3.6, we need one more technical lemma. This lemma uses many of the deep results on Cambrian semilattices developed in [15], and requires the following alternative characterization of the (right) weak order on W. Let T = {[wsw.sup.-1] | w [member of] W, s [member of] S}, and define for w [member of] W, the (left) inversion set of w as inv(w) = {t [member of] T | [l.sub.S](tw) [less than or equal to] [l.sub.S](w)}. It is the statement of [3], Proposition 3.1.3] that u [[less than or equal to].sub.S] [upsilon] if and only if inv(u) [subset or equal to] inv([upsilon]). Moreover, for w [member of] W, we say that t [member of] inv(w) is called a cover reflection of w if there exists some s [member of] S with tw = ws. We denote by cov(w) the set of all cover reflections of w.

Lemma 3.7 Let u, [upsilon] [member of] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon] and let s be initial in [gamma]. If s [[not less than or equal to].sub.[gamma]] u and s [[less than or equal to].sub.[gamma]] [upsilon], then the join s [[disjunction].sub.[gamma]] u covers u in [C.sub.[gamma]].

Proof: First of all, since s [[less than or equal to].sub.[gamma]] [upsilon] and u [[less than or equal to].sub.[gamma]] [upsilon], we conclude from [15, Theorem 7.1] that s [[disjunction].sub.[gamma]] u exists, and set z = s [[disjunction].sub.[gamma]] u. By assumption, we have u = [[pi].sup.[sigma][gamma].sub.[down arrow]]([u.sub.<s>]) [member of] [W.sub.<s>], and Proposition 2.3 implies u = [u.sub.<s>]. We deduce then from [15, Lemma 2.23] that cov(z) = {s} [union] cov(u). Therefore s is a cover reflection of z, and it follows from [15, Proposition 5.4 (i)] that z = s [[disjunction].sub.[gamma]] [z.sub.<s>], and [15, Proposition 5.4 (ii)] implies that cov(z) = {s} [union] cov([z.sub.<s>]). Hence, cov(u) = cov([z.sub.<s>]), and [15, Theorem 8.9 (iv)] implies u = [z.sub.<s>]. (The required fact that [z.sub.<s>] is [gamma]-sortable follows from [15, Propositions 3.13 and 6.10].)

On the other hand, it follows from the definition of a cover reflection that there exists an element z' = sz [member of] W with z' [??] z, thus [z'.sub.<s>] [[less than or equal to].sub.S] [z.sub.<s>], see [15, Section 2.5]. Furthermore we have that inv(z') = inv(z)\{s}, and since inv(s) = {s}, Proposition 3.1.3 in [3] implies s [[not less than or equal to].sub.S] z'. Hence, by definition of [[pi].sup.[gamma].sub.[down arrow]], see (2), we have [[pi].sup.[gamma].sub.[down arrow]](z') = [[pi].sup.s[gamma].sub.[down arrow]]([z'.sub.<s>]) [member of] [W.sub.<s>], and [[pi].sup.[gamma].sub.[down arrow]](z') [[??].sub.[gamma]] z'. Since [[pi].sup.s[gamma].sub.[down arrow]] is order-preserving, see [15, Theorem 6.1], we conclude from [z'.sub.<s>] [[less than or equal to].sub.S] [z.sub.<s>] that [[pi].sup.s[gamma].sub.[down arrow]]([z'.sub.<s>]) [[less than or equal to].sub.S] [[pi].sup.s[gamma].sub.[down arrow]]([z.sub.<s>]). Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [[pi].sup.[gamma].sub.[down arrow]](z') [[??].sub.[gamma]] z and u [<.sub.[gamma]] z, the previous implies u = [[pi].sup.[gamma].sub.[down arrow]](z') and thus u [[??].sub.[gamma]] z. []

Proof of Theorem 3.6: Let [[u, [upsilon]].sub.[gamma]] be a closed interval of [C.sub.[gamma]]. Since the weak order on W is finitary, it follows that [[u, [upsilon]].sub.[gamma]] is a finite lattice. We show that there exists a unique maximal rising chain in [[u, [upsilon]].sub.[gamma]] which is the lexicographically first among all maximal chains in this interval.

We proceed by induction on length and rank, using the recursive structure of [gamma]-sortable words, see Proposition 2.3. We assume that [l.sub.S]([upsilon]) [greater than or equal to] 3, and that W is a Coxeter group of rank [greater than or equal to] 2, since the result is trivial otherwise. Say that W is of rank n, and say that [l.sub.S]([upsilon]) = k. Suppose that the induction hypothesis is true for all parabolic subgroubs of W of rank < n and suppose that for every closed interval [[u', [upsilon]'].sub.[gamma]] of [C.sub.[gamma]] with [l.sub.S]([upsilon]') < k, there exists a unique rising maximal chain from u' to [upsilon]' which is lexicographically first among all maximal chains in [[u', [upsilon]'].sub.[gamma]]. We show that there is a unique rising maximal chain in the interval [[u, [upsilon]].sub.[gamma]] wich is lexicographically first among all maximal chains in [[u, [upsilon]].sub.[gamma]]. For s initial in [gamma], we distinguish two cases: (1) s [[less than or equal to].sub.[gamma]] [upsilon] and (2) s [[not less than or equal to].sub.[gamma]] [upsilon].

(1a) Suppose first that s [[less than or equal to].sub.[gamma]] u as well. Then, s is the first letter in the [gamma]-sorting word of every element in [[u, [upsilon]].sub.[gamma]]. It follows from [15, Proposition 2.18] and Proposition 2.3 that the interval [[u, [upsilon]].sub.[gamma]] is isomorphic to the interval [[su, s[upsilon]].sub.s[gamma]s]. Moreover, Lemma 3.5 implies that for a covering relation x [[??].sub.[gamma]] y in [[u, [upsilon]].sub.[gamma]] we have [[lambda].sub.[gamma]](x, y) = [[lambda].sub.s[gamma]s](sx, sy) + 1. Say that c': su = [sx.sub.0] [[??].sub.s[gamma]s] [sx.sub.1] [[??].sub.s[gamma]s] ... [[??].sub.s[gamma]s] [sx.sub.t] = s[upsilon] is the unique rising maximal chain in [[su, s[upsilon]].sub.s[gamma]s]. (This chain exists by induction, since [l.sub.S](s[upsilon]) < [l.sub.S]([upsilon]).) Then, the chain c: u = [x.sub.0] [[??].sub.[gamma]] [x.sub.1] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [x.sub.t] = [upsilon] is a maximal chain in [[u, [upsilon]].sub.[gamma]] and clearly rising. With Lemma 3.5, we find that c is the unique rising chain and every other maximal chain in [[u, [upsilon]].sub.[gamma]] is lexicographically larger than c.

(1b) Suppose now that s [[not less than or equal to].sub.[gamma]] u. Since s [[less than or equal to].sub.[gamma]] [upsilon] and u [[less than or equal to].sub.[gamma]] [upsilon] the join [u.sub.1] = s [[disjunction].sub.[gamma]] u exists and lies in [[u, [upsilon]].sub.[gamma]]. Lemma 3.7 implies that u [[??].sub.[gamma]] [u.sub.1]. Consider the interval [[[u.sub.1], [upsilon]].sub.[gamma]]. Then s [[less than or equal to].sub.[gamma]] [u.sub.1] and analogously to (1a) we can find a unique maximal rising chain c': [u.sub.1] [[??].sub.[gamma]] [u.sub.2] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [u.sub.t] = [upsilon] in [[[u.sub.1], [upsilon]].sub.[gamma]] which is lexicographically first. Moreover, min{i | i [member of] [[alpha].sub.[gamma]]([upsilon])\[[alpha].sub.[gamma]]([u.sub.1])} > 1, since s [[less than or equal to].sub.[gamma]] [u.sub.1] [[less than or equal to].sub.[gamma]] [upsilon]. By definition of our labeling, the label 1 cannot appear as a label in any chain in the interval [[[u.sub.1], [upsilon]].sub.[gamma]]. On the other hand, it follows from Lemma 3.5 that [[lambda].sub.[gamma]](u, [u.sub.1]) = 1. Thus, the chain c: u [[??].sub.[gamma]] [u.sub.1] [[??].sub.[gamma]] [u.sub.2] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [u.sub.t] = [upsilon] is maximal and rising in [[u, [upsilon]].sub.[gamma]]. Suppose that there is another element u' that covers u in [[u, [upsilon]].sub.[gamma]] such that [[lambda].sub.[gamma]](u, u') = 1. Then, by definition of [[lambda].sub.[gamma]], it follows that s appears in the [gamma]-sorting word of u'. In particular, since s is initial in [gamma], we deduce that s [[less than or equal to].sub.[gamma]] u'. Therefore u' is above both s and u in [C.sub.[gamma]]. By the uniqueness of joins and the definition of [u.sub.1] it follows that [u.sub.1] = u'. Thus c is the lexicographically smallest maximal chain in [[u, [upsilon]].sub.[gamma]]. Finally, Lemma 3.4 implies that c is the unique maximal rising chain.

(2) Since s [[not less than or equal to].sub.[gamma]] [upsilon], it follows that no element of [[u, [upsilon]].sub.[gamma]] contains the letter s in its [gamma]- sorting word. We consider the parabolic Coxeter group [W.sub.<s>] (generated by S\{s}) and the Coxeter element s[gamma]. It follows from Proposition 2.3 that the interval [[u, [upsilon]].sub.[gamma]] is isomorphic to the interval [[[u.sub.<s>], [[upsilon].sub.<s>]].sub.s[gamma]] in [W.sub.<s>]. Since the rank of [W.sub.<s>] is n - 1 < n, by induction there exists a unique maximal rising chain c' : [u.sub.<s>] = [([x.sub.0]).sub.<s>] [[??].sub.s[gamma]] [([x.sub.1]).sub.<s>] [[??].sub.s[gamma]] ... [[??].sub.s[gamma]] [([x.sub.t]).sub.<s>] = [[upsilon].sub.<s>] which is lexicographically first among all maximal chains in [[[u.sub.<s>], [[upsilon].sub.<s>]].sub.s[gamma]]. The result then follows with Lemma 3.5. []

Proof of Theorem 1.1: This follows by definition from Theorem 3.6. []

4 Applications

In [12], Nathan Reading investigated, among others, the topological properties of open intervals in so-called fan posets. A fan poset is a certain partial order defined on the maximal cones of a complete fan of regions of a real hyperplane arrangement. For a finite Coxeter group W and a Cambrian congruence [theta], the Cambrian fan [F.sub.[theta]] is the complete fan induced by certain cones in the Coxeter arrangement AW of W. More precisely, each such cone is a union of regions of AW which correspond to elements of W lying in the same congruence class of [theta]. It is the assertion of [12, Theorem 1.1], that a Cambrian lattice of W is the fan poset associated to the corresponding Cambrian fan. The following theorem is a concatenation of [12, Theorem 1.1] and [12, Propositions 5.6 and 5.7]. In fact, Propositions 5.6 and 5.7 in [12] imply this result for a much larger class of fan posets.

Theorem 4.1 Let W be a finite Coxeter group and let [gamma] [member of] W be a Coxeter element. Every open interval in the Cambrian lattice [C.sub.[gamma]] is either contractible or spherical.

It is well-known that the reduced Euler characteristics of the order complex of an open interval (x, y) in a poset determines [mu](x, y), see for instance [16, Proposition 3.8.6]. Hence, it follows immediately from Theorem 4.1 that for [gamma]-sortable elements x and y in a finite Coxeter group W satisfying x [[less than or equal to].sub.[gamma]] y, we have [absolute value of [mu](x, y)] [less than or equal to] 1, as was already remarked in [13, pp. 4-5]. In light of Proposition 2.1 and Theorem 3.6, we can extend this statement to compute the Mobius function of closed intervals in the Cambrian semilattice [C.sub.[gamma]], by counting the falling maximal chains with respect to the labeling defined in (3).

Theorem 4.2 Let W be a (possibly infinite) Coxeter group and [gamma] [member of] W a Coxeter element. For u, [upsilon] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon], we have [absolute value of [mu](u, [upsilon])] [less than or equal to] 1.

Proof: In view of Proposition 2.1 it is enough to show that the interval [[u, [upsilon]].sub.[gamma]] has at most one maximal falling chain. We use similar arguments as in the proof of Theorem 3.6 and proceed by induction on length and rank. Again, for s initial in [gamma], we distinguish the following two cases: s [[less than or equal to].sub.[gamma]] [upsilon] and s [[not less than or equal to].sub.[gamma]] [upsilon]. Here we discuss only the special case where s [[less than or equal to].sub.[gamma]] [upsilon] and s [[not less than or equal to].sub.[gamma]] u. (The others follow by applying the same methods as in the proof of Theorem 3.6.) It follows from Lemma 3.4 that a maximal chain u = [c.sub.0] [[??].sub.[gamma]] [c.sub.1] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [c.sub.t-1] [??] [c.sub.t] = [upsilon] of [[u, [upsilon]].sub.[gamma]] can be falling only if [[lambda].sub.[gamma]]([c.sub.t- 1], [upsilon]) = 1. Hence, if there is no element [[upsilon].sub.1] [member of] [(u, [upsilon]).sub.[gamma]], with [[upsilon].sub.1] [??] [upsilon] satisfying [[lambda].sub.[gamma]]([[upsilon].sub.1], [upsilon]) = 1, then the interval [[u, [upsilon]].sub.[gamma]] has no maximal falling chain, which means that [mu](u, [upsilon]) = 0. Otherwise, consider the interval [[u, [[upsilon].sub.1]].sub.[gamma]]. By the choice of [[upsilon].sub.1], it follows that every maximal falling chain in [[u, [[upsilon].sub.1]].sub.[gamma]] can be extended to a maximal falling chain in the interval [[u, [upsilon]].sub.[gamma]]. Conversely, every maximal falling chain in [[u, [upsilon]].sub.[gamma]] can be restricted to a maximal falling chain in [[u, [[upsilon].sub.1]].sub.[gamma]]. Therefore, since [l.sub.S]([[upsilon].sub.1]) < [l.sub.S]([upsilon]), we deduce from the induction hypothesis that the interval [[u, [[upsilon].sub.1]].sub.[gamma]] has at most one maximal falling chain. Thus [absolute value of [mu]x(u, [upsilon])] [less than or equal to] 1. []

In addition Propositions 5.6 and 5.7 in [12] characterize the open intervals in a (finite) Cambrian lattice which are contractible, and those which are spherical in the following way: an interval [[u, [upsilon]].sub.[gamma]] in [C.sub.[gamma]] is called nuclear if the join of the upper covers of u is precisely [upsilon]. Nathan Reading showed that the nuclear intervals are precisely the spherical intervals. With the help of our labeling, we can generalize this characterization to infinite Coxeter groups.

Theorem 4.3 Let u, [upsilon] [member of] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon] and let k denote the number of atoms of the interval [[u, [upsilon]].sub.[gamma]]. Then, [mu](u, [upsilon]) = [(-1).sup.k] if and only if [[u, [upsilon]].sub.[gamma]] is nuclear.

For the proof of Theorem 4.3, we need the following lemma.

Lemma 4.4 Let u, [upsilon] [member of] [C.sub.[gamma]] with u [[less than or equal to].sub.[gamma]] [upsilon], and let s be initial in [gamma]. Suppose further that s [[not less than or equal to].sub.[gamma]] u, while s [[less than or equal to].sub.[gamma]] [upsilon]. Then the following are equivalent:

1. The interval [[u, [upsilon]].sub.[gamma]] is nuclear.

2. There exists an element [upsilon]' [member of] [[u, [upsilon]].sub.[gamma]] satisfying s [[not less than or equal to].sub.[gamma]] [upsilon]' [[??].sub.[gamma]] [gamma], and the interval [[u, [upsilon]'].sub.[gamma]] is nuclear.

Proof of Theorem 4.3: In view of Proposition 2.1, we need to show that [[u, [upsilon]].sub.[gamma]] has a falling chain if and only if [[u, [upsilon]].sub.[gamma]] is nuclear. We use similar arguments as in the proof of Theorem 3.6 and proceed by induction on length and rank. For the inductive step we distinguish two cases: (1) s [[less than or equal to].sub.[gamma]] [upsilon] and (2) s [[less than or equal to].sub.[gamma]] [upsilon], where s initial in [gamma]. Here we discuss the special case where s [[not less than or equal to].sub.[gamma]] u, while s [[less than or equal to].sub.[gamma]] [upsilon]. If [[u, [upsilon]].sub.[gamma]] is nuclear, the result follows by combining Lemmas 3.5,4.4, Theorem 4.2 and by applying induction on the rank of W. Conversely, suppose that there exists a maximal falling chain c: u = [x.sub.0] [[??].sub.[gamma]] [x.sub.1] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [x.sub.t] = [upsilon] in [[u, [upsilon]].sub.[gamma]], and let A = {w [member of] [C.sub.[gamma]] | u [[??].sub.[gamma]] w and w [[less than or equal to].sub.[gamma]] [upsilon]} denote the set of atoms of [[u, [upsilon]].sub.[gamma]]. It follows then that the chain c' : u = [x.sub.0] [[??].sub.[gamma]] [x.sub.1] [[??].sub.[gamma]] ... [[??].sub.[gamma]] [x.sub.t-1] is falling, thus by induction we can conclude that the interval [[u, [x.sub.t-1]].sub.[gamma]] is nuclear. We deduce from Lemma 3.4 that s [[not less than or equal to].sub.[gamma]] [x.sub.t-1], and since [x.sub.t-1] [??] [upsilon], it follows from Lemma 4.4 that [[u, [upsilon]].sub.[gamma]] is nuclear. This completes the proof of the theorem. []

Proof of Theorem 1.2: It follows directly from Theorem 1.1, [5, Theorem 5.9] and Theorem 4.2. The characterization of the spherical intervals is an immediate consequence of Theorem 4.2. []

We conclude this article with a short example of an infinite Coxeter group.

Example 4.5 Consider the affine Coxeter group [[??].sub.2], which is generated by the set {[s.sub.1], [s.sub.2], [s.sub.3]} satisfying [([s.sub.1][s.sub.2]).sup.3] = [([s.sub.1][s.sub.3]).sup.3] = [([s.sub.2][s.sub.3]).sup.3] = [epsilon], as well as [s.sup.2.sub.1] = [s.sup.2.sub.2] = [s.sup.2.sub.3] = [epsilon]. Consider the Coxeter element [gamma] = [s.sub.1][s.sub.2][s.sub.3]. Figure 2 shows the sub-semilattice of the Cambrian semilattice [C.sub.[gamma]] consisting of all [gamma]-sortable elements of [[??].sub.2] of length [less than or equal to] 7. We encourage the reader to verify Theorem 3.6 and Theorem 4.2.

Acknowledgements

The authors would like to thank Nathan Reading for pointing out a weakness in a previous version of the proof of Theorem 3.6 and for many helpful discussions on the topic.

References

[1] A. Bjorner. Shellable and Cohen-Macaulay Partially Ordered Sets. Trans. Amer. Math. Soc., 260:159-183, 1980.

[2] A. Bjorner. Topological Methods. volume 2 of Handbook of Combinatorics, pages 1819-1872. MIT Press, Cambridge, MA, 1996.

[3] A. Bjorner and F. Brenti. Combinatorics of Coxeter Groups. Springer, New York, 2005.

[4] A. Bjorner and M. L. Wachs. On Lexicographically Shellable Posets. Trans. Amer. Math. Soc., 277:323-341, 1983.

[5] A. Bjorner and M. L. Wachs. Shellable and Nonpure Complexes and Posets I. Trans. Amer. Math. Soc., 348:1299-1327, 1996.

[6] A. Bjorner and M. L. Wachs. Shellable and Nonpure Complexes and Posets II. Trans. Amer. Math. Soc., 349:3945-3975, 1997.

[7] B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, 2002.

[8] J. E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, Cambridge, 1990.

[9] C. Ingalls and H. Thomas. Noncrossing Partitions and Representations of Quivers. Composition Mathematica, 145:1533-1562, 2009.

[10] M. Kallipoliti and H. Muhle. On the Topology of the Cambrian Semilattices. arXiv:1206.6248, 2012.

[11] V. Pilaud and C. Stump. EL-Labelings and Canonical Spanning Trees for Subword Complexes. arXiv:1210.1435, 2012.

[12] N. Reading. Lattice Congruences, Fans and Hopf Algebras. J. Combin. Theory (Ser. A), 110:237-273, 2005.

[13] N. Reading. Cambrian Lattices. Adv. Math., 205:313-353, 2006.

[14] N. Reading. Sortable Elements and Cambrian Lattices. Alg. Universalis, 56:411-437, 2007.

[15] N. Reading and D. E. Speyer. Sortable Elements in Infinite Coxeter Groups. Trans. Amer. Math. Soc., 363:699-761, 2011.

[16] R. P. Stanley. Enumerative Combinatorics, Vol. 1. Cambridge University Press, Cambridge, 1997.

[17] D. Tamari. The Algebra of Bracketings and their Enumeration. Nieuw Archiefvoor Wiskunde, 10:131-146, 1962.

[18] M. L. Wachs. Poset Topology: Tools and Applications. In Geometric Combinatorics, volume 13 of IAS/Park City Math. Ser., pages 497-615. American Mathematical Society, Providence, RI, 2007.

Myrto Kallipoliti and Henri Muihle ([dagger])

Fak. fur Mathematik, Universitdt Wien, Garnisongasse 3, 1090 Vienna, Austria

([dagger]) Email: {myrto.kallipoliti, heriri.muehle}@uriivie.ac.at. The authors were supported by the FWF research grant no. Z130-N13.

(i) Actually, Proposition 5.7 in [5] is stated for posets admitting a so-called CR-labeling. EL-shellable posets are a particular instance of this class of posets, and for the scope of this article it is sufficient to restrict our attention to these.
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Kallipoliti, Myrto; Muhle, Henri
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUAU
Date:Jan 1, 2013
Words:7579
Previous Article:Poset vectors and generalized permutohedra (extended abstract).
Next Article:The Eulerian polynomials of type D have only real roots.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters