# On the H-triangle of generalised nonnesting partitions.

1 IntroductionFor 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

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: |