Printer Friendly

On the H-triangle of generalised nonnesting partitions.

1 Introduction

For a crystallographic root system [PHI], there are three well-known Coxeter-Catalan objects [Arm09]: the set of noncrossing partitions NC([PHI]), the set of nonnesting partitions NN([PHI]) and the cluster complex [DELTA]([PHI]). The former two and the set of facets of the latter are all counted by the same numbers, the Coxeter-Catalan numbers Cat([PHI]). For the root system of type [A.sub.n-1], these reduce to objects counted by the classical Catalan numbers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], namely the set of noncrossing partitions of [n] = {1, 2, ..., n}, the set of nonnesting partitions of [n] and the set of triangulations of a convex (n + 2)-gon, respectively.

Each of these Coxeter-Catalan objects has a generalisation [Arm09], a Fuss-Catalan object defined for each positive integer k. These are the set of k-divisible noncrossing partitions [NC.sub.(k)]([PHI]), the set of k-generalised nonnesting partitions [NN.sup.(k)]([PHI]) and the generalised cluster complex [[DELTA].sup.(k)]([PHI]). They specialise to the corresponding Coxeter-Catalan objects when k = 1. The former two and the set of facets of the latter are counted by Fuss-Catalan numbers [Cat.sup.(k)]([PHI]), which specialise to the classical Fuss-Catalan numbers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in type [A.sub.n-1].

The enumerative coincidences do not end here. Chapoton defined the M-triangle, the H-triangle and the F-triangle, which are polynomials in two variables that encode refined enumerative information on NC([PHI]), NN([PHI]) and [DELTA]([PHI]) respectively [Cha04, Cha06]. This allowed him to formulate the M = F conjecture [Cha04, Conjecture 1] and the H = F conjecture [Cha06, Conjecture 6.1] relating these polynomials through invertible transformations of variables. These conjectures were later generalised to the corresponding Fuss-Catalan objects by Armstrong [Arm09, Conjecture 5.3.2.]. The M = F conjecture was first proven by Athanasiadis [Ath07] for k = 1, and later by Krattenthaler [Kra06a, Kra06b] and Tzanaki [Tza08] for k > 1. In this extended abstract, we prove the H = F conjecture in the k = 1 case. The proof of the generalised conjecture of Armstrong can be found in the full version [Thi14].

2 Definitions and the Main Result

Let [PHI] = [PHI](S) be a crystallographic root system with a simple system S. Then [PHI] = [[PHI].sup.+] [??] - [[PHI].sup.+] is the disjoint union of the set of positive roots [[PHI].sup.+] and the set of negative roots -[[PHI].sup.+]. Every positive root can be written uniquely as a linear combination of the simple roots and all coefficients of this linear combination are nonnegative integers. For further background on root systems, see [Hum90]. Define the root order on [[PHI].sup.+] by

[beta] [greater than or equal to] [alpha] if and only if [beta] - [alpha] [member of] [<S>.sub.N],

that is, [beta] [greater than or equal to] [alpha] if and only if [beta] - [alpha] can be written as a linear combination of simple roots with nonnegative integer coefficients. The set of positive roots [[PHI].sup.+] with this partial order is called the root poset. A set of pairwise incomparable elements of the root poset is called an antichain. The support of a root [beta] [member of] [[PHI].sup.+] is the set of all [alpha] [member of] S with [alpha] [less than or equal to] [beta].

We define the set of nonnesting partitions NN([PHI]) of [PHI] as the set of antichains in the root poset of [PHI].

Let us define the H-triangle [Cha06, Section 6] as

[H.sub.[PHI]](x, y) = [summation over (A[member of]NN([PHI]))][x.sup.[absolute value of A]][y.sup.[absolute value of A[intersecion]S]].

Let [[PHI].sub.[greater than or equal to]-1] = [[PHI].sup.+] [union] - S be the set of almost positive roots of [PHI]. Then there exists a symmetric binary relation called compatibility [FZ03, Definition 3.4] on [[PHI].sub.[greater than or equal to]-1] such that all negative simple roots are pairwise compatible and for [alpha] [member of] S and [beta] [member of] [[PHI].sup.+], -[alpha] is compatible with [beta] if and only if [alpha] is not in the support of [beta].

Define a simplicial complex [DELTA]([PHI]) as the set of all subsets A [subset or equal to] [[PHI].sub.[greater than or equal to]-1] such that all almost positive roots in A are pairwise compatible. This is the cluster complex of [PHI]. This simplicial complex is pure, all facets have cardinality n, where n = [absolute value of S] is the rank of [PHI].

Let us define the F-triangle [Cha04, Section 2] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Consider the Weyl group W = W([PHI]) of the root system [PHI]. A standard Coxeter element in W is a product of all the simple reflections of W in some order. A Coxeter element is any element of W that is conjugate to a standard Coxeter element. Let T denote the set of reflections in W. For w [member of] W, define the absolute length [l.sub.T](w) of w as the minimal I such that w = [t.sub.1][t.sub.2] ... [t.sub.l] for some [t.sub.1], [t.sub.2], ..., [t.sub.l] [member of] T. Define the absolute order on W by

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

Fix a Coxeter element c [member of] W. We define the set of noncrossing partitions NC([PHI]) of [PHI] as the interval [e, c] in the absolute order. We drop the choice of the Coxeter element c from the notation, since a different choice of Coxeter element results in a different but isomorphic poset.

Let us define the M-triangle [Cha04, Section 3] as

[M.sub.[PHI]](x, y) = [summation over (u,[upsilon][member of]NC([PHI]))][mu](x, [upsilon])[x.sup.rk(u)][y.sup.rk([upsilon])],

where rk is the rank function of the graded poset NC([PHI]) and [mu] is its Mobius function.

As mentioned in the introduction, NC([PHI]), NN([PHI]) and the set of facets of [DELTA]([PHI]) are all counted by the same number Cat([PHI]). But more is true: define the Narayana number Nar([PHI], i) as the number of elements of NC([PHI]) of rank i [Arm09, Definition 3.5.4]. The number of antichains in the root poset of cardinality i also equals Nar([PHI], i) [Ath05, Proposition 5.1, Remark 5.2]. Let ([h.sub.0], [h.sub.1], ..., [h.sub.n]) be the h-vector of [DELTA]([PHI]), defined by the relation

[n.summation over (i=0)][h.sub.i][x.sup.n-i] = [summation over (l,m)][f.sub.l,m][(x - 1).sup.n-(l+m)].

Then [h.sub.n-i] = Nar([PHI], i) for all i [member of] {0, l, ..., n} [FR05, Theorem 3.2].

The main result of this extended abstract is the following theorem, conjectured by Chapoton.

Theorem 1 If [PHI] is a crystallographic root system of rank n, then

[H.sub.[phi]](x, y) = [(x - 1).sup.n][F.sub.[phi]] (1/x - 1, 1 + (y - 1)x/x - 1).

In order to prove Theorem 1, we first find a combinatorial bijection for nonnesting partitions that leads to a differential equation for the H-triangle analogous to one known for the F-triangle. Using both of these differential equations and induction on the rank n, we prove Theorem 1 by showing that the derivatives with respect to y of both sides of the equation as well as their specialisations at y = 1 agree. After proving Theorem 1, we use it together with the M = F (ex-)conjecture to relate the H-triangle to the M-triangle.

3 Proof of the Main Result

To prove Theorem 1, we show that the derivatives with respect to y of both sides of the equation agree, as well as their specialisations at y = 1. To do this, we need the following lemmas.

Lemma 1 If [PHI] is a crystallographic root system of rank n, then

[H.sub.[PHI]](x, 1) = [(x - 1).sup.n][F.sub.[PHI]](1/x - 1, 1/x - 1).

Proof: We have

[(x - 1).sup.n][F.sub.[PHI]](1/x - 1, 1/x - 1) = [summation over (l,m)][f.sub.l,m][(x - 1).sup.n-(l+m)] = [n.summation over (i=0)][h.sub.i][x.sub.n-i],

where ([h.sub.0], [h.sub.1], ..., [h.sub.n]) is the h-vector of [DELTA]([PHI]). So

[[x.sup.i]][(x - 1).sup.n][F.sub.[PHI]](1/x - 1, 1/x - 1) = [h.sub.n-i] = Nar([PHI], i).

by [FR05. Theorem 3.2]. But

[[x.sup.i]][H.sub.[PHI]](x, 1) = Nar([PHI], i).

by [Ath05, Proposition 5.1. Remark 5.2].

Lemma 2 ([Cha04, Proposition 3]) If [PHI] is a crystallographic root system of rank n, then

[[partial derivative]/[partial derivative]y][F.sub.[PHI](S)](x, y) = [summation over ([alpha][member of]S)][F.sub.[PHI]{S\[alpha]}](x, y).

Lemma 3 For every simple root [alpha] [member of] S, there exists a bijection [THETA] from the set of nonnesting partitions A [member of] NN([PHI](S)) with [alpha] [member of] A to NN([PHI](S\{[alpha]})), such that [absolute value of [THETA](A)] = [absolute value of A] - 1 and [absolute value of [THETA](A) [intersection] S\{[alpha]}] = [absolute value of A [intersection] S] - 1 for all A [member of] NN([PHI](S)).

Proof: Define [THETA](A) = A\{[alpha]}. If [beta] [member of] A and [beta] [not equal to] [alpha]. then [beta] and [alpha] are incomparable. since A is an antichain. So [alpha] is not in the support of [beta]. So [beta] [member of] [PHI](S\{[alpha]}). Clearly [THETA](A) = A\{[alpha]} is an antichain in the root poset of [PHI](S\{[alpha]}), so [THETA] is well defined. It is also clear that [absolute value of [THETA](A)] = [absolute value of A] - 1 and [absolute value of [THETA](A) [intersection] S\{[alpha]}] = [absolute value of A [intersection] S] - 1 for all A [member of] NN([PHI](S)).

Define the map [PSI]: NN([PHI](S\{[alpha]})) [right arrow] NN([PHI](S)) by [PSI](A) = A [union] {[alpha]}. If A [member of] NN([PHI](S\{[alpha]})) and [beta] [member of] A. then [alpha] is not in the support of [beta], so [alpha] and [beta] are incomparable. Thus [psi](A) = A [union] {[alpha]} is an antichain in the root poset of [PHI](S). so [PSI] is well-defined. Clearly [PSI] is the inverse of [THETA], so [THETA] is a bijection.

Lemma 4 If [PHI] is a crystallographic root system of rank n, then

[[partial derivative]/[partial derivative]y][H.sub.[PHI](S)](x, y) = x[summation over ([alpha][member of]S)][H.sub.[PHI](S\{[alpha]})](x, y).

Proof: Say h;,m([PHI]) = [xlym]H[PHI](x, y). We wish to show that

[mh.sub.l,m]([PHI](S)) = [summation over ([alpha][member of]S)][h.sub.l-1,m-1]([PHI](S\{[alpha]}).

So we seek a bijection [THETA] from the set of pairs (A, [alpha]) with A [member of] NN([PHI](S)) and [alpha] [member of] A [intersection] S to the set of pairs ([alpha]', A') with [alpha]' [member of] S and A' [member of] NN([PHI](S\{[alpha]'})) such that if [THETA](A, [alpha]) = (A', [alpha]'), then [absolute value of A'] = [absolute value of A] - 1 and [absolute value of A' [intersection] S\{[alpha]'}] = [absolute value of A [intersection] S] - 1. Such a bijection is given in Lemma 3.

We are now in a position to prove Theorem 1.

Proof of Theorem 1: We proceed by induction on n. If n = 0, both sides are equal to 1, so the result holds. If n > 0,

[[partial derivative]/[partial derivative]y][H.sub.[PHI](S)](x, y) = x[summation over ([alpha][member of]S)][H.sub.[PHI](S\{[alpha]})](x, y),

by Lemma 4. By induction hypothesis, this is further equal to

x[summation over ([alpha][member of]S)](x - 1)[F.sub.[PHI](S\{[alpha]})](1/x - 1, 1 + (y - 1)/x - 1),

which equals

[partial derivative]/[partial derivative]y[(x - 1).sup.n][F.sub.[PHI](S)](1/x - 1, 1 + (y - 1)x/x - 1)

by Lemma 2. But

[H.sub.[PHI]](x, 1) = [(x - 1).sup.n][F.sub.[PHI]](1/x - 1, 1/x - 1)

by Lemma 1, so

[H.sub.[PHI]](x, y) = [(x - 1).sup.n][F.sub.[PHI]](1/x - 1, 1 + (y - 1)x/x - 1),

since the derivatives with respect to y as well as the specialisations at y = 1 of both sides agree.

4 Consequences and generalisations

We may also recover the original statement of the conjecture, due to Chapoton.

Corollary 1 ([Cha06, Conjecture 6.1]) If [PHI] is a crystallographic root system of rank n, then

[H.sub.[PHI]](x, y) = [(1 - x).sup.n][F.sub.[PHI]](x/1 - x, xy/1 - x).

Proof: We have [Cha04, Proposition 5]

[F.sub.[PHI]](x, y) = [(-1).sup.n][F.sub.[PHI]](-1 - x, -1 - y). (1)

Substitute (1) into Theorem 1 to get the result.

Using the M = F (ex-)conjecture, we can also relate the H-triangle to the M-triangle.

Corollary 2 If [PHI] is a crystallographic root system of rank n, then

[H.sub.[PHI]](x, y) = [(1 + (y - 1)x).sup.n][M.sub.[PHI]](y/y - 1, (y - 1)x/1 + (y - 1)x).

Proof: We have [Kra06a, Conjecture FM] [Ath07, Theorem 1.1]

[F.sub.[PHI]](x, y) = [y.sup.n][M.sub.[PHI]](1 + y/y - x, y - x/y). (2)

Substitute (2) into Theorem 1 to get the result.

Lemma 1, Lemma 2, Lemma 4, Theorem 1 and Corollary 2 all generalise to the corresponding FuB Catalan objects [NN.sup.(k)]([PHI]), [NC.sup.(k)]([PHI]) and [[DELTA].sup.(k)]([PHI]). For proofs of these more general results and further consequences, see the full version of the article [Thi14].

References

[Arm09] Drew Armstrong. Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups. Memoirs of the American Mathematical Society, 202, 2009.

[Ath05] Christos A. Athanasiadis. On a Refinement of the Generalized Catalan Numbers for Weyl Groups. Transactions of the American Mathematical Society, 357:179-196, 2005.

[Ath07] Christos A. Athanasiadis. On some enumerative aspects of generalized associahedra. European Journal of Combinatorics, 28:1208-1215, 2007.

[Cha04] Frederic Chapoton. Enumerative Properties of Generalized Associahedra. Seminaire Lotharingien de Combinatiore, 51, 2004.

[Cha06] Frederic Chapoton. Sur le nombre de reflexions pleines dans les groupes de coxeter finis. Bulletin of the Belgian Mathematical Society, 13:585-596, 2006.

[FR05] Sergey Fomin and Nathan Reading. Generalized Cluster Complexes and Coxeter Combinatorics. International Mathematics Research Notices, 44:2709-2757, 2005.

[FZ03] Sergey Fomin and Andrei Zelevinsky. Y-Systems and Generalized Associahedra. Annals of Mathematics, 158:977-1018, 2003.

[Hum90] James E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, Cambridge, 1990.

[Kra06a] Christian Krattenthaler. The F-triangle of the generalised cluster complex. Topics in Discrete Mathematics, pages 93-126, 2006.

[Kra06b] Christian Krattenthaler. The M-triangle of generalised non-crossing partitions for the types E7 and Eg. Seminaire Lotharingien de Combinatoire, 54, 2006.

[Thi14] Marko Thiel. On the H-triangle of generalised nonnesting partitions. European Journal of Combinatorics, 39:244-255, 2014.

[Tza08] Eleni Tzanaki. Faces of Generalized Cluster Complexes and Noncrossing Partitions. SIAM Journal on Discrete Mathematics, 22:15-30, 2008.

Marko Thiel *

Department of Mathematics, University of Vienna, Austria

* Email: marko.thiel@univie.ac.at
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Thiel, Marko
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2014
Words:2559
Previous Article:Poset topology and homological invariants of algebras arising in algebraic combinatorics.
Next Article:Supercharacters of unipotent groups defined by involutions (extended abstract).
Topics:

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters