Printer Friendly

Bisections between noncrossing and nonnesting partitions for classical reflection groups.

1 Introduction and background

The Coxeter-Catalan combinatorics is an active field of study in the theory of Coxeter groups, having at its core the numerological concurrences according to which several independently motivated sets of objects to do with a Coxeter group W have the cardinality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where h is the Coxeter number of W and [d.sub.1], ..., [d.sub.n] its degrees. Two of these sets of objects are

* the noncrossing partitions NC{W), which in their classical (type A) avatar are a long-studied combinatorial object harking back at least to Kreweras [6], and in their generalisation to arbitrary Coxeter groups are due to Bessis and Brady and Watt [4, 5]; and

* the nonnesting partitions NN(W), introduced by Postnikov [9] for all the finite crystallographic reflection groups simultaneously.

Athanasiadis [2], and Athanasiadis and Reiner [3] proved in a case-by-case fashion that [absolute value of NN(W)] = [absolute value of NC(W)] for all finite Weyl groups W, and asked for a bijective proof. Their work also proved equidistribution by type, cited as Theorem 1.17 below. Our contribution has been to provide a family of bijective proofs, one for each type of classical reflection group, that also address equidistribution by type. The bijections in types B, C, and D have not appeared before in the literature. The ultimate goal in connecting NN(W) and NC(W) from this perspective, a proof both uniform and bijective, remains open.

In the remainder of this section we lay out briefly the definitions of the objects involved: in [section]1.1, the uniform definitions of nonnesting and noncrossing partitions; in [section]1.2, a mode of extracting actual partitions from these definitions which our bijections rely upon; in [section]1.3, the resulting notions for classical reflection groups. In section 2 we present a family of type-preserving bijections between noncrossing and nonnesting partitions for all the classical reflection groups, one type at a time.

Two other papers presenting combinatorial bijections between noncrossing and nonnesting partitions independent of ours, one by Stump [12] and by Mamede [8], appeared essentially simultaneously to it. Both of these limit themselves to types A and B, whereas we also treat type D; our approach is also distinct in its type preservation and in providing additional statistics characterising the new bijections.

1.1 Uniform noncrossing and nonnesting partitions

For noncrossing partitions we follow Armstrong [1, [section]2.4-6]. The treatment of nonnesting partitions is due to Postnikov [9].

Let W be a finite Coxeter group and consider the dual Coxeter system (W,T).

The set NC(W) of (uniform) noncrossing partitions of W is defined as an interval of the absolute order.

Definition 1.1 The absolute order Abs(W) of W is the partial order on W such that for w, x [member of] W, w [less than or equal to] x if and only if

[l.sub.T](x) = [l.sub.T]{w) + [l.sub.T](w.sup.-1]x),

where [l.sub.T](w) is the minimum length of any expression for w as a product of elements of T. A word for w in T of length [l.sub.T](w) will be called a reduced T-word for w.

Definition 1.2 A standard Coxeter element of(W, S) is any element of the form c = [s.sub.[sigma](1)][s.sub.[sigma](2)] ... [s.sub.[sigma](n)], where [sigma] is a permutation of the set [n] and S = {[s.sub.1], [s.sub.2], ..., [s.sub.n]}, the set of simple generators of W. A Coxeter element is any conjugate of a standard Coxeter element in W.

Definition 1.3 Relative to any Coxeter element c, the poset of (uniform) noncrossing partitions is the interval NC(W, c) = [1, c] in the absolute order.

This definition does not depend on the choice of Coxeter element c, see Armstrong [1]. We use the notation NC{W) for the poset of noncrossing partitions of W with respect to any c.

Now assume W is crystallographic. The set NN{W) of nonnesting partitions is defined in terms of the usual root poset of W.

Definition 1.4 A (uniform) nonnesting partition for W is an antichain in the root poset of W. We denote the set of nonnesting partitions of W by NN(W).

To each root a we have an orthogonal hyperplane [alpha] [perpendicular] with respect to (*, *), and these define a hyperplane arrangement and a poset of intersections.

Definition 1.5 The partition lattice [GAMMA](M) of W is the intersection poset of reflecting hyperplanes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

1.2 Classical partitions

Our drawings of partitions are taken from Athanasiadis and Reiner [3]. We have reversed the orderings of the ground sets from Athanasiadis's presentation.

Let W be a classical reflection group.

Definition 1.6 A classical partition for W is a partition Part(L) of the set

{[+ or -][e.sub.i] : i = 1, ..., n} [union] {0},

induced by the partition into fibers of the orthogonal projection to L, for some L [member of] [PI](W) in the standard choice of coordinates.

We will streamline the notation of classical partitions by writing [+ or -]i for [+ or -][e.sub.i]. Thus, a classical partition for W is a partition of [+ or -][n] = {1, ..., n, -1, ..., -n, 0} for some n, symmetric under negation. A classical partition always contains exactly one part fixed by negation, which contains the element 0, namely the fiber over 0 [member of] L. Since the position of 0 is predictable given the other elements, in many circumstances we will omit it altogether. If the block containing 0 contains other elements as well, we shall call it a zero block. A detailed discussion of what these partitions are for each specific type is found in [2] and [3].

Finally, we introduce the type of a partition.

Definition 1.7 Let [pi] = Part(L) be a classical partition for a classical reflection group W. The type type([pi]) of [pi] is the conjugacy class of L under the action of W on [PI](W).

1.3 Classical noncrossing and nonnesting partitions

Definitions of the classes of noncrossing and nonnesting classical partitions are most intuitively presented in terms of a diagrammatic representation, motivating the names "noncrossing" and "nonnesting". After Armstrong [1, [section]5.1] we call these bump diagrams.

Let P be a partition of a totally ordered ground set (S, <).

Definition 1.8 Let G(P) be the graph with vertex set S and edge set

{(s, s') : s < P s' and [??]s" [member of] S s.t. s < p s" <P s'}

where s < p s' iff s < s' and s and s' are in the same block of P.

A bump diagram of P is a drawing of G(P) in the plane in which the elements of S are arrayed along a horizontal line in their given order, all edges lie above this line, and no two edges intersect more than once.

Definition 1.9 P is noncrossing if its bump diagram contains no two crossing edges, equivalently if G(P) contains no two edges of form (a, c), (b, d) with a < b < c < d.

Definition 1.10 P is nonnesting if its bump diagram contains no two nested edges, equivalently if G(P) contains no two edges of form (a, d), (b, c) with a < b < c < d.

We will abuse the terminology slightly and refer to the bump diagram of P as noncrossing, resp. nonnesting, if P is. We will denote the set of classical noncrossing and nonnesting partitions for W by [NC.sup.cl](W), resp. [NN.sup.cl](W). To define these sets it remains only to specify the ordered ground set.

Definition 1.11 A classical nonnesting partition for a classical reflection group W is a classical partition for W nonnesting with respect to the ground set

1 < ... < n + 1 if W = [A.sub.n];

-n, < ... < -1 < 0 < 1 < -< n if W = [B.sub.n];

-n, < ... < -1 < 1 < ... < n if W = [C.sub.n];

-n < ... < -1, 1 < ... < n if W = [D.sub.n].

Classical nonnesting partitions for [B.sub.n] differ from those for [C.sub.n], reflecting the different root posets. We have specified that 0 is part of the ordered ground set for [B.sub.n]. Despite that, 0 cannot occur in a classical partition. It is easily seen that its presence is necessary when drawing bump diagrams: the dot 0 "ties down" a problematic edge of the zero block in the middle, preventing it from nesting with the others.

Definition 1.12 A classical noncrossing partition for a classical reflection group W not of type D is a classical partition for W noncrossing with respect to the ground set

1 < ... < n + 1 if W = [A.sub.n];

-1 < ... < -n < 1 < ... < n if W = [B.sub.n];

-1 < ... < -n < 1 < ... < n if W = [C.sub.n].

Observe that the order < in these ground sets differs from those for nonnesting partitions.

We will draw these circularly. Arrange dots labelled -2, ..., -n, 2, ..., n in a circle and place 1 and -1 in the middle. We let 1 and -1 be drawn coincidently, after [3], although it would be better to use two circles as in [7], with a smaller one in the center on which only 1 and -1 lie. There is a standard way to represent partitions of [D.sub.n] in this se[pi]ing. The edges we will supply in our diagrams are those delimiting the convex hulls of the blocks.

Definition 1.13 A classical noncrossing partition [pi] for [D.sub.n] is a classical partition for [D.sub.n] such that no two blocks have intersecting convex hulls in the circular diagram representing [pi], except possibly two blocks [+ or -]B meeting only at the middle point.

See the figures in Section 2 for examples of bump diagrams of every type.

We state the relations between these classical noncrossing and nonnesting partitions and the uniform ones. For w [member of] W, let the fixed space Fix(w) of w be the subspace of y (VF) consisting of vectors fixed by w.

Proposition 1.14 The map [[florin].sub.NC] : w [??] Part(Fix(w)) is a bijection between NC(W, c) and [NC.sup.cl](W), where c is the usual choice of standard Coxeter element. Furthermore, it is an isomorphism of posets, where NC(W, c) is ordered by the absolute order and [NC.sup.cl](W) by the refinement order.

Proposition 1.15 The map [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a bijection between NN{W) and [NN.sup.cl](W).

The distribution of classical noncrossing and nonnesting partitions with respect to type is well-behaved. In the noncrossing case, the images of the conjugacy classes of the group W itself are the same as these conjugacy classes of the action of W on [PI](W).

One can check that

Proposition 1.16 Two subspaces L, L' [member of] [PI](W) are conjugate if and only if both of the following hold:

* the multisets of block sizes {[absolute value of C] : C [member of] Part(L)} and {[absolute value of C] : C [member of] Part(L')} are equal;

* if either Part(L) or Part(L') has a zero block, then both do, and these zero blocks have equal size.

We close this section with the statement of the uniform equidistribution result of Athanasiadis and Reiner.

Theorem 1.17 Let W be a Weyl group. Let [[florin].sub.NC] and [[florin].sub.NN] be the functions of Propositions 1.14 and 1.15.

For any type [lambda] we have

[absolute value of (type o [[florin].sub.NC]).sup.-1](A)] = [absolute value of (type o [[florin].sub.NN]).sup.-1] ([lambda])].

2 Type-preserving classical bijections

Throughout, partitions will be drawn and considered drawn with the greatest elements of their ground sets to the left.

Given any partition, define the order [<.sub.1] on those of its blocks containing positive elements so that B [<.sub.1] B' if and only if the least positive element of B is less than the least positive element of B'.

2.1 Type A

The bijection in type A, which forms the foundation of the ones for the other types, is due to Athanasiadis [2, [section]3]. We include it here to make this foundation explicit and to have bijections for all the classical groups in one place.

Let [pi] be a classical partition for [A.sub.n]. Let [M.sub.1] [<.sub.1] ... [<.sub.1] [M.sub.m] be the blocks of [pi], and [a.sub.i] the least element of [M.sub.i], so that [a.sub.1] < ... < [a.sub.m]. Let [u.sub.i] be the cardinality of [M.sub.i]. Define the two statistics a([pi]) = ([a.sub.i], ..., [a.sub.m]) and, [mu]([pi]) = ([[mu].sub.1] ..., [[mu].sub.m]).

We will say that a list of partition statistics S establishes a bijection for a classical reflection group W if, given either a classical noncrossing partition [[pi].sub.NC] or a classical nonnesting partition [[pi].sub.NN] for W, the other one exists uniquely such that s([[pi].sub.NC]) = s([[pi].sub.NN]) for all s [member of] S. We will say it establishes a type-preserving bijection if furthermore 7rNG and 7rNN always have the same type.

Theorem 2.1 The statistics (a, [mu]) establish a type-preserving bijection for An.

[FIGURE 1 OMITTED]

Figure 1 illustrates this bijection.

The type-preserving assertion is obtained by [mu] preservation. As for the bijection itself, we describe a process for converting back and forth between classical noncrossing and nonnesting partitions with the same tuples a, [mu]. Routine verifications are left out of it.

Proof: View [M.sub.1], ..., [M.sub.m] as chains, i.e. connected components, in the bump diagram for [pi], each corresponding to a block. By virtue of [mu] we know the length of each chain, so we can view the chains as abstract unlabeled graphs in the plane and our task as that of interposing the vertices of these chains in such a way that the result is nonnesting or noncrossing, as desired.

Suppose we start with [[pi].sup.NN]. To build the noncrossing diagram of [[pi].sup.NC], we will inductively place the chains [M.sub.i], ..., [M.sub.m], in that order. Suppose that, for some j [less than or equal to] n, we have placed [M.sub.i] for all < j. To place [M.sub.j], we insert its rightmost vertex so as to become the [a.sub.jth] vertex counting from right to left, relative to the chains [M.sub.j-1], ..., [M.sub.1] already placed. We then insert the remaining vertices of [M.sub.j] in the unique possible way so that no pair of crossing edges are formed. (In this instance, this means that all the vertices of [M.sub.j] should be placed consecutively, in immediate succession.)

Now, suppose we start with [[pi].sup.NC] and want [[pi].sup.NN]. We again build the bump diagram chain by chain, at each step placing the rightmost vertex in exactly the same way and placing the remaining vertices in the unique way so that no pair of nesting edges are formed. (This can be achieved if every edge is drawn the same size, with its vertices at constant Euclidean distance 1.)

Note that, in both directions, all the choices we made were unique, so the resulting partitions are unique.

A careful study of this proof provides a useful characterisation of the pairs of tuples a, y that are the statistics of a classical nonnesting or noncrossing partition of type A.

Corollary 2.2 Suppose we are given a pair of tuples of positive integers a = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let n > 0. Define [a.sub.0] = 0 and [[mu].sub.0] = 1. Then, a and y represent a classical noncrossing or nonnesting partition for An if and only if

1. [m.sub.1] = [m.sub.2] = m;

2. n + 1 = [[summation].sup.m.sub.k=1] [[mu].sub.k] ; and

3. [a.sub.i-1] < [a.sub.i] [less than or equal to] [[summation].sup.i-1.sub.k=0] for i = 1, 2, ..., m.

2.2 Type C

In the classical reflection groups other than [A.sub.n], the negative elements of the ground set must be treated, and so it will be useful to have some terminology to deal with these.

Definition 2.3 A positive block of a classical partition [pi] is a block of [pi] that contains some positive integer; similarly a negative block contains a negative integer. A switching block of [pi] is a block of it that contains both positive and nonpositive elements, and a nonswitching block is one that contains positive elements but not negative ones, or the reverse.

A single edge of the bump diagram is positive or negative or switching or nonswitching if it would have those properties as a block of size 2.

Note that in later sections, where there will be elements of the ground set that are neither positive nor negative, there may be blocks that consist only of these and so are neither switching nor nonswitching.

Let [pi] be a classical partition for [C.sub.n]. Given [pi], let [M.sub.1] [<.sub.1] ... [<.sub.1] Mm be the nonswitching positive blocks of [pi], and [a.sub.i] the least element of [M.sub.i]. Let [[mu].sub.i] be the cardinality of [M.sub.i]. These two tuples are reminiscent of type A. Let [P.sub.1] [<.sub.l] ... [<.sub.l] [P.sub.k] be the switching blocks of [pi], let [P.sub.i] be the least positive element of [P.sub.i], and let [v.sub.i] be the number of positive elements of [P.sub.i]. Define the three statistics a([pi]) = ([a.sub.1], ..., [a.sub.m]), [mu]([pi]) = ([[mu].sub.1], ..., [[mu].sub.m]), v([pi]) = ([v.sub.1]; ..., [v.sub.k]). We have

n = [m.summation over (i=1)] [[mu].sub.i] + [k.summation over (j=1)] [v.sub.j].

Theorem 2.4 The statistics (a, [mu], v) establish a type-preserving bijection for [C.sub.n].

[FIGURE 2 OMITTED]

Proof: We state a procedure for converting back and forth between classical noncrossing and nonnesting partitions that preserve the values a, [mu], and v. Suppose we start with a partition [pi], be it noncrossing [[pi].sup.NN] or nonnesting [[pi].sup.NC], and we want to find the partition [pi]', which respectively would precisely be [[pi].sup.NC] or [[pi].sup.NN]. To do this, we construct the positive side of [pi]' inductively from these tuples, which will determine [pi]' completely.

In the bump diagram of [pi], consider the labeled connected component representing [P.sub.i], which we call the chain [P.sub.i]. Let the partial chain [P'.sub.j] be the abstract unlabeled connected graph obtained from the chain [P.sub.i] by removing its negative nonswitching edges and negative vertices, leaving the unique switching edge incomplete, i.e. partially drawed so that it becomes a clear half-edge in our new abstract graph, and losing the labeling. Notice how the tuple v allows us to draw these partial chains. Whatever procedure we followed for type A will generalise to this case, treating the positive parts of the switching edges first.

We want to obtain the bump diagram for [pi]', so we begin by using v to partially draw the chains representing its switching blocks: we draw only the positive edges (switching and nonswitching) of every chain, leaving the unique switching edge incomplete. This is done by reading v from back to front and inserting each partial switching chain [P'.sub.i] in turn with its rightmost dot placed to the right of all existing chains. In the noncrossing case, we end up with every vertex of [P'.sub.i] being strictly to the right of every vertex of [P'.sub.j] for i < j. In the nonnesting case, the vertices of the switching edges will be exactly the k first positions from right to left among all the vertices of [P'.sub.1], ..., [P'.sub.k]. It remains to place the nonswitching chains [M.sub.1], [M.sub.2], ..., [M.sub.m], and this we do as in the type A bijection, except that at each step, we place the rightmost vertex of [M.sub.j] so as to become the [a.sub.jth] vertex, counting from right to left, relative to the chains [M.sub.j-i], ..., [M.sub.1] and the partial chains [P'.sub.1], [P'.sub.2], ..., [P'.sub.k] already placed.

Now we have the positive side of [pi]'. We copy these blocks down again with all parts negated, and end up with a set of incomplete switching blocks [P.sub.1*], ..., [P.sub.k*] on the positive side and another equinumerous set -[P.sub.1*], ..., -[P.sub.k*] on the negative side that we need to pair up and connect with edges in the bump diagram.

There is a unique way to connect these incomplete blocks to get the partition [pi]', be it [[pi].sup.NG] or [[pi].sup.NN]. In every case [P.sub.i*] gets connected with -[P.sub.k+1-i*], and in particular symmetry under negation is attained. If there is a zero block it arises from [P.sub.(k+i)/2*]

Finally, [pi] and [pi]' have the same type. Since the [P.sub.i*] are paired up the same way in each, including any zero block, [mu] and v determine the multiset of block sizes of n and [pi]' and the size of any zero block, in identical fashion in either case. Then this is Proposition 1.16. []

Again, a careful look at the preceding proof gives the characterization of the tuples that describe classical noncrossing and nonnesting partitions for type C.

Corollary 2.5 Suppose we are given some tuples of positive integers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], v = ([v.sub.1], ..., [v.sub.k]) and let n > 0. Define [a.sub.0] = 0 and [[mu].sub.0] = 1. Then, a, [mu] and v represent a classical noncrossing or nonnesting partition for [C.sub.n] if and only if

1. [m.sub.1] = [m.sub.2] = m;

2. n = [[summation].sup.m.sub.i=1] [[mu].sub.i] + [[summation].sup.k.sub.j=1] [v.sub.j];

3. [a.sub.i-1] < [a.sub.i] [less than or equal to] [[summation].sup.m.sub.i=1] [[mu].sub.k] + [[summation].sup.k.sub.j=1] [v.sub.j] for i = 1, 2, ..., m.

2.3 Type B

We will readily be able to modify our type C bijection to handle type B. Indeed, if it were not for our concern about type, we would already possess a bijection for type B, differing from the type C bijection only in pairing up the incomplete switching blocks in a way respecting the presence of the element 0. Our task is thus to adjust that bijection to recover the type-preservation.

If [pi] is a classical partition for [B.sub.n], we define the tuples a,([pi]), [mu]([pi]) and v([pi]) as in type C.

Notice that classical noncrossing partitions for [B.sub.n] and for [C.sub.n] are identical, and that the strictly positive part of any classical nonnesting partition for [B.sub.n] is also the strictly positive part of some nonnesting [C.sub.n]-partition, though not necessarily one of the same type. Thus Corollary 2.5 characterises the classical noncrossing or nonnesting partitions for [B.sub.n] just as well as for [C.sub.n].

Suppose [pi] is a classical nonnesting partition for [B.sub.n]. In two circumstances its tuples a([pi]), [mu]([pi]), v([pi]) also describe a unique nonnesting partition for [C.sub.n] of the same type: to be explicit, this is when [pi] does not contain a zero block, and when the unique switching chain in [pi] is the one representing the zero block. If [P.sub.1] [<.sub.l] ... [<.sub.l] [P.sub.k] are the switching blocks of [pi], then [pi] contains a zero block and more than one switching chain if and only if k is odd and k > 1. We notice that [P.sub.k] must be the zero block. On the other hand, if [[pi].sup.c] is a classical nonnesting partition for [C.sub.n], the zero block must be [P.sub.(k+1)/2]. Reflecting this, our bijection will be forced to reorder v to achieve type preservation.

Generalizing our prior language, we will say that two lists [S.sup.NC] = {[s.sup.NC.sub.1], ..., [s.sup.NC.sub.a]} and [S.sup.NN] = {[s.sup.NN.sub.1], ..., [s.sup.NN.sub.a]} of partition statistics, in that order, and a list [SIGMA] = {[[sigma].sub.1], ..., [[sigma].sub.a]} of bijections establish a (type-preserving) bijection for a classical reflection group W if, given either a classical noncrossing partition [[pi].sup.NC] or a classical nonnesting partition [[pi].sup.NN] for W, the other one exists uniquely such that [[sigma].sub.i]([[pi].sup.NC.sub.i]([[pi].sup.NC])) = [[pi].sup.NN.sub.i]([[pi].sup.NN]) for all 1 [less than or equal to] i [less than or equal to] a (and furthermore [[pi].sup.NN] and [[pi].sup.NC] have the same type).

Suppose we have a tuple v = ([v.sub.1], ..., [v.sub.k]) with k odd. Define the reordering

[[sigma].sub.B](v) = ([v.sub.1], ..., [v.sub.(k-1)/2], [v.sub.(k-3)/2], ..., [V.sub.k], [v.sub.(k+1)/2]).

If k is not odd then let [[sigma].sub.B](v) = v. Clearly [[sigma].sub.B] is bijective. For explicitness, we write for k odd

[[sigma].sup.-1.sub.B](v) = ([v.sub.1], ..., [v.sub.(k-1)/2], [v.sub.k], [v.sub.(k-1)/2], ... [v.sub.k-1])

and for k even [[sigma].sup.-1.sub.B] (v) = v.

Theorem 2.6 The lists of statistics (a, [mu], v) and (a, [mu], v) establish a type-preserving bijection for [B.sub.n] via the bijections (id, id, [[sigma].sub.B]).

Proof (Sketch): We use the same procedures as in type C to convert back and forth between classical nonnesting and noncrossing partitions, except that we rearrange v as appropriate. Notice v can be reordered in any way, so we order it to have type preservation. []

Figure 3 illustrates the resulting bijection.

2.4 Type D

The handling of type D partitions is a further modification of our treatment of the foregoing types, especially type B.

In classical partitions for [D.sub.n], the elements [+ or -]1 will play much the same role as the element 0 of classical nonnesting partitions for [B.sub.n]. So when applying the order [<.sub.1] and the terminology of Definition 2.3 in type D we will regard [+ or -]1 as being neither positive nor negative.

[FIGURE 3 OMITTED]

Given [pi] [member of] [NN.sup.cl]([D.sub.n]), define the statistics a([pi]), [mu]([pi]) and v([pi]) as in type B. Let [R.sub.1] [<.sub.l] ... [<.sub.l] [R.sub.l] be the blocks of [pi] which contain both a positive element and either 1 and -1. It is clear that l [less than or equal to] 2. Define the statistic c([pi]) = ([c.sub.1], ..., [c.sub.l]) by [c.sub.i] = [R.sub.i] [intersection] (1, -1). To streamline the notation we shall usualy write [c.sub.i] as one of the symbols +, -, [+ or -]. Observe that [pi] contains a zero block if and only if c([pi]) = ([+ or -]).

To get a handle on type D classical noncrossing partitions, we will transform them into type B ones. Let [NC.sup.cl.sub.r]([B.sub.n-1]) be a relabelled set of classical noncrossing partitions for [B.sub.n-1], in which the parts 1, ..., (n - 1) and -1, ..., -n - 1 are changed respectively to 2, ..., n and -2, ..., -n. Define a map CM : [NC.sup.cl]([D.sub.n]) [right arrow] [NC.sup.cl.sub.r]([B.sub.n-1), which we will call central merging, such that for [pi] [member of] [NN.sup.cl]([D.sub.n]), CM([pi]) is the classical noncrossing [B.sub.1]-partition obtained by first merging the blocks containing [+ or -]1 (which we have drawn at the center of the circular diagram) into a single part, and then discarding these elements [+ or -]1. Define the statistics a, [mu] and v for [pi] to be equal to those for CM([pi]), where the entries of a should acknowledge the relabelling and thus be chosen from {2, ..., n}.

These statistics do not uniquely characterise [pi], so we define additional statistics c([pi]) and [xi]([pi]). The definition of c([pi]) is analogous to the nonnesting case: let [R.sub.1] [<.sub.l] ... [<.sub.l] [R.sub.l] be the blocks of [pi] which intersect {1, -1}, and define c([pi]) = ([c.sub.1], ..., [c.sub.l]) where [c.sub.i] = [R.sub.i] [intersection] {1, -1}. Also define [zeta]([pi]) = ([c.sub.1], ... [c.sub.l]) where [c.sub.i] = [R.sub.i] [intersection] {1, -1}. Also define [zeta]([pi]) = ([zeta].sub.1], ..., [[zeta].sub.l]) where [[zeta].sub.l] = #(R.sub.l] [intersection] {2, ..., n}) is the number of positive parts of [R.sub.l].

Observe that CM([pi]) lacks a zero block if and only if c([pi]) = (), the case that 1 and -1 both belong to singleton blocks of [pi]. In this case CM([pi]) is just [pi] with the blocks {1} and {-1} removed, so that [pi] is uniquely recoverable given CM([pi]). Otherwise, CM([pi]) has a zero block. If c([pi]) = ([+ or -]) this zero block came from a zero block of [pi], and [pi] is restored by resupplying [+ or -]1 to this zero block. Otherwise two blocks of [pi] are merged in the zero block of CM([pi]). Suppose the zero block of CM([pi]) is {[c.sub.1], ..., [c.sub.j], -[c.sub.1], ..., -[c.sub.j]}, with 0 < [c.sub.1] < ... < [c.sub.j], so that j = [[summation].sup.l.sub.i=1] [[zeta].sub.1]. By the noncrossing and symmetry properties of [pi], one of the blocks of [pi] which was merged into this block has the form {-[m.sub.i+i], ..., -[m.sub.j], [m.sub.1], ..., [m.sub.1], s} where 1 [less than or equal to] i [less than or equal to] j and s [member of] {1, -1}. Then, by definition, c([pi]) = (s, -s) and [xi]([pi]) = - i), except that if j - i = 0 the latter component of each of these must be dropped.

Let a tagged noncrossing partition for [B.sub.n-1] be an element [pi] [member of] [NC.sup.cl.sub.r]([B.sub.n-1]) together with tuples c([pi]) of nonempty subsets of {1, -1} and [zeta]([pi]) of positive integers such that:

1. the entries of c([pi]) are pairwise disjoint;

2. c([pi]) and [zeta]([pi]) have equal length;

3. the sum of all entries of [zeta]([pi]) is the number of positive elements in the zero block of [pi].

We have the following important lemmas whose proof we omit in this abstract.

Lemma 2.7 Central merging gives a bijection between classical noncrossing partitions for [D.sub.n] and tagged noncrossing partitions for [B.sub.n-1].

Lemma 2.8 A classical nonnesting partition [pi] for [D.sub.n] is uniquely determined by the values of a([pi]), [mu]([pi]), v([pi]), and c([pi]).

All that remains to obtain a bijection is to describe the modifications to v that are needed for correct handling of the zero block and its components (rather as in type B). For a classical nonnesting partition [pi] for [D.sub.n], find the tuples a([pi]), [mu]([pi]), v([pi]) = ([v.sub.1], ..., [v.sub.k]), and c([pi]). Let [zeta]([pi]) t>e the tuple of the last / entries of v([pi]), where l is the length of c([pi]). Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Define a bijection [[sigma].sub.D] by [[sigma].sub.D] (v([pi])) = ([??]([pi]), [zeta]([pi])). This gives us all the data for a tagged noncrossing partition CM([pi]) for [B.sub.n-1], which corresponds via central merging with a noncrossing partition [pi]' for [D.sub.n]. Going backwards, from a noncrossing partition [pi]' we recover a nonnesting partition [pi] by applying central merging, finding the list of statistics (a([pi]), [mu]([pi]), v([pi]), c([pi])) via the equality

v([pi]) = [[sigma].sup.-1.sub.D] (v[pi]'), [zeta]([pi]'))

(the other statistics remain equal) and using these statistics to make a nonnesting partition as usual. Type preservation may be seen to be implied within these modifications of the statistics.

All in all, we have just proved the following theorem.

Theorem 2.9 The lists of statistics (a, [mu], (v, [zeta]), c) and (a, [mu], v, c) establish a type-preserving bijection for [D.sub.n] via the bijections (id, id, [([[sigma].sub.D]).sup.-1], id).

Figures 4 and 5 illustrate this bijection.

[FIGURE 4 OMITTED]

We omit the characterization of the tuples representing noncrossing and nonnesting partitions of type D.

[FIGURE 5 OMITTED]

3 Acknowledgments

This work sprang from a project in Federico Ardila's course on Coxeter groups in the spring of 2008, and was supported by the SFSU-Colombia Combinatorics Initiative. The authors thank Federico for many useful comments and suggestions.

References

[1] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, preprint, arXiv:math.CO/061110 6v2.

[2] C. A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electronic J. Combin. 5 (1998), R42.

[3] C. A. Athanasiadis and V. Reiner, Noncrossing partitions for the group [D.sub.n], SIAM J. Discrete Math. 18 (2004), 397-417.

[4] D. Bessis, The dual braid monoid, Ann. Sci. Ecole Norm. Sup. (4), 36 (2003), 647-683.

[5] T. Brady and C. Watt, K([pi], 1) 's for Artin groups of 'finite type in Proceedings of the conference on geometric and combinatorial group theory, Part I (Haifa 2000), Geom. Dedicata. 94 (2002), 225-250.

[6] G. Kreweras, Sur lespartitions non croisees d'un cycle, Discrete Math. 1 (1972), 333-350.

[7] C. Krattenthaler and T. W. Muller, Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions, Trans. Amer. Math. Soc, to appear; preprint, arXiv: 0704.0199v2.

[8] R. Mamede, A bijection between noncrossing and nonnesting partitions of types A and B, preprint, arXiv:0810.1422vl.

[9] A. Postnikov and R. Stanley, Deformations of Coseter hyperplane arrangements, preprint, April 14, 1997.

[10] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195- 222.

[11] R. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, Cambridge, 1997.

[12] Christian Stump, Non-crossing partitions, non-nesting partitions and Coxeter sortable elements in types A and B, preprint, arXiv:0808.2822v1.

Alex Fink (1) ([dagger]) and Benjamin Iriarte Giraldo (2) ([double dagger])

(1) Department of Mathematics, University of California, Berkeley, Berkeley, CA, USA; finka@math.berkeley.edu

(2) Departamento de Mathematics, Universidad de los Andes, Bogota, Colombia; b-iriart@uniandes.edu.co

([dagger]) (1) Supported by the SFSU-Los Andes initiative.

([double dagger]) (2) Supported by the SFSU-Los Andes initiative.
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Fink, Alex; Giraldo, Benjamin Iriarte
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2009
Words:5903
Previous Article:Enumeration of derangements with descents in prescribed positions.
Next Article:New Hopf structures on binary trees.
Topics:

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