• 検索結果がありません。

A bijection between non-crossing and non-nesting partitions of types A and B

N/A
N/A
Protected

Academic year: 2022

シェア "A bijection between non-crossing and non-nesting partitions of types A and B"

Copied!
60
0
0

読み込み中.... (全文を見る)

全文

(1)

A bijection between non-crossing and non-nesting partitions of types A and B

Christian Stump

March 31, 2008

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 1 of 29

(2)

Overview

Classical non-crossing and non-nesting partitions

Motivation

Non-crossing partitions

Non-nesting partitions

A bijection betweenNN(W)and NC(W) in types AandB

(3)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 3 of 29

(4)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

(5)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 3 of 29

(6)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

(7)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 3 of 29

(8)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

(9)

Non-crossing and non-nesting set partitions

LetB ⊢ [n] be a set partition of the set [n] ∶= {1, . . . ,n}. Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 3 of 29

(10)

Non-crossing set partitions

A set partitionB ⊢ [n] is called

non-crossing, if fora<b<c <d such that a,c are contained in a block B of B, whileb,d are contained in a blockBof B, then B=B,

Example

B = {{1,9},{2,5,6,7},{3,4},{8}} ⊢ [9]is non-crossing:

(11)

Non-crossing set partitions

A set partitionB ⊢ [n] is called

non-crossing, if fora<b<c <d such that a,c are contained in a block B of B, whileb,d are contained in a blockBof B, then B=B,

Example

B = {{1,9},{2,5,6,7},{3,4},{8}} ⊢ [9]is non-crossing:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 4 of 29

(12)

Non-nesting set partitions

A set partitionB ⊢ [n] is called

non-nesting, if fora<b<c <d such that a,d are contained in a block B ofB, while b,c are contained in a blockB of B, then B=B.

Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]is non-nesting:

(13)

Non-nesting set partitions

A set partitionB ⊢ [n] is called

non-nesting, if fora<b<c <d such that a,d are contained in a block B ofB, while b,c are contained in a blockB of B, then B=B.

Example

B = {{1,4},{2,5,7,9},{3,6},{8}} ⊢ [9]is non-nesting:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 5 of 29

(14)

Non-crossing and non-nesting partitions

We will later see that non-crossing and non-nesting set partitions can be seen as the typeAinstances of more general constructions:

non-crossing partitionsNC(W), attached to anyreal reflection group W (Reiner), and furthermore to any well-generated complex reflection group W (Bessis),

non-nesting partitions NN(W) attached to any crystallographic real reflection group(Postnikov).

(15)

General motivation

Both constructions seem to be related enumeratively in a very deep way, in particular

both are counted by theCatalan numbers,

both have a positive partwhich is counted by the positive Catalan numbers,

both have a refinement which is counted by theNarayana numbers,

but so far only for typeA, explicit bijections are known.

Question / Open Problem

What is nature of the relationship between NC(W) andNN(W)? Find a bijection betweenNC(W) andNN(W)that preserve

“natural” statistics.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 7 of 29

(16)

General motivation

Both constructions seem to be related enumeratively in a very deep way, in particular

both are counted by theCatalan numbers,

both have a positive partwhich is counted by the positive Catalan numbers,

both have a refinement which is counted by theNarayana numbers,

but so far only for typeA, explicit bijections are known.

Question / Open Problem

What is nature of the relationship betweenNC(W) andNN(W)? Find a bijection betweenNC(W) andNN(W)that preserve

“natural” statistics.

(17)

My motivation

In the context ofrational Cherednik algebras, there naturally arises a bigradedW-moduleM such that

its dimension is equal to the number of non-nesting and the number of non-crossing partitions,

dimM=#NN(W) =#NC(W),

its bigraded Hilbert seriesH(M;q,t) is a natural q,t-analogue of the Catalan numbers,

the specialization t=1 is conjectured to be counted by a certain statistic area onNN(W),

H(M;q,1) = ∑

I∈NN(W)

qarea(I).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 8 of 29

(18)

My motivation

In the context ofrational Cherednik algebras, there naturally arises a bigradedW-moduleM such that

its dimension is equal to the number of non-nesting and the number of non-crossing partitions,

dimM=#NN(W) =#NC(W),

its bigraded Hilbert seriesH(M;q,t) is a natural q,t-analogue of the Catalan numbers,

the specialization t=1 is conjectured to be counted by a certain statistic area onNN(W),

H(M;q,1) = ∑

I∈NN(W)

qarea(I).

(19)

My motivation

In the context ofrational Cherednik algebras, there naturally arises a bigradedW-moduleM such that

its dimension is equal to the number of non-nesting and the number of non-crossing partitions,

dimM=#NN(W) =#NC(W),

its bigraded Hilbert seriesH(M;q,t) is a natural q,t-analogue of the Catalan numbers,

the specialization t=1 is conjectured to be counted by a certain statistic area onNN(W),

H(M;q,1) = ∑

I∈NN(W)

qarea(I).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 8 of 29

(20)

My motivation

In the context ofrational Cherednik algebras, there naturally arises a bigradedW-moduleM such that

its dimension is equal to the number of non-nesting and the number of non-crossing partitions,

dimM=#NN(W) =#NC(W),

its bigraded Hilbert seriesH(M;q,t) is a natural q,t-analogue of the Catalan numbers,

the specialization t=1 is conjectured to be counted by a certain statistic area onNN(W),

H(M;q,1) = ∑

I∈NN(W)

qarea(I).

(21)

My personal motivation

Open Problem

Find a second statistic tstat onNN(W)that describes those q,t-Catalan numbers combinatorially,

H(M;q,t) = ∑

I∈NN(W)

qarea(I)ttstat(I).

Remark

In typeA, such a statistic is known (Haglund & Haiman).

A first step would be to find a statistic qstat, such that qNH(M;q,q−1) = ∑

I∈NN(W)

qqstat(I).

Hope

A bijection betweenNC(W) andNN(W) for which some of those statistics can be “nicely” described in terms ofNC(W)could shade some light on this open problem.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 9 of 29

(22)

My personal motivation

Open Problem

Find a second statistic tstat onNN(W)that describes those q,t-Catalan numbers combinatorially,

H(M;q,t) = ∑

I∈NN(W)

qarea(I)ttstat(I).

Remark

In typeA, such a statistic is known (Haglund & Haiman).

A first step would be to find a statistic qstat, such that qNH(M;q,q−1) = ∑

I∈NN(W)

qqstat(I).

Hope

A bijection betweenNC(W) andNN(W) for which some of those statistics can be “nicely” described in terms ofNC(W)could shade some light on this open problem.

(23)

My personal motivation

Open Problem

Find a second statistic tstat onNN(W)that describes those q,t-Catalan numbers combinatorially,

H(M;q,t) = ∑

I∈NN(W)

qarea(I)ttstat(I).

Remark

In typeA, such a statistic is known (Haglund & Haiman).

A first step would be to find a statistic qstat, such that qNH(M;q,q−1) = ∑

I∈NN(W)

qqstat(I).

Hope

A bijection betweenNC(W) andNN(W) for which some of those statistics can be “nicely” described in terms ofNC(W)could shade some light on this open problem.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 9 of 29

(24)

My personal motivation

Open Problem

Find a second statistic tstat onNN(W)that describes those q,t-Catalan numbers combinatorially,

H(M;q,t) = ∑

I∈NN(W)

qarea(I)ttstat(I).

Remark

In typeA, such a statistic is known (Haglund & Haiman).

A first step would be to find a statistic qstat, such that qNH(M;q,q−1) = ∑

I∈NN(W)

qqstat(I).

Hope

A bijection betweenNC(W) andNN(W) for which some of those statistics can be “nicely” described in terms ofNC(W)could

(25)

Non-crossing set partitions and the symmetric group

When we order the elements in each block of a non-crossing set partitionBincreasingly, we can identify B with the permutation σ having cycles equal to the blocks ofB.

Example

[n] ⊣ B = {{1,9},{2,5,6,7},{3,4},{8}}

Sn∋σ = (1,9)(2,5,6,7)(3,4)

= [9,5,4,3,6,7,2,8,1].

The image of this embedding is the set of all permutations which have

only increasing cycles,

no “crossing” cycles in the sense described above.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 10 of 29

(26)

Non-crossing set partitions and the symmetric group

When we order the elements in each block of a non-crossing set partitionBincreasingly, we can identify B with the permutation σ having cycles equal to the blocks ofB.

Example

[n] ⊣ B = {{1,9},{2,5,6,7},{3,4},{8}}

Sn∋σ = (1,9)(2,5,6,7)(3,4)

= [9,5,4,3,6,7,2,8,1].

The image of this embedding is the set of all permutations which have

only increasing cycles,

no “crossing” cycles in the sense described above.

(27)

The absolute order on the symmetric group

Definition

For a permutationσ, let the absolute lengthlT(σ) be the minimal integerk such thatσ can be written as the product ofk transpositions,

lT(σ) ∶=min{k ∶σ=t1⋯tk, for transpositionsti}.

Theabsolute order onSn is then defined by σ≤T τ ∶⇔lT(τ) =lT(σ) +lT−1τ).

Theorem (Reiner)

σ∈ Sn is non-crossing if and only if

σ≤T (1,2, . . . ,n) =∶c⇔σ∈ [1,c].

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 11 of 29

(28)

The absolute order on the symmetric group

Definition

For a permutationσ, let the absolute lengthlT(σ) be the minimal integerk such thatσ can be written as the product ofk transpositions,

lT(σ) ∶=min{k ∶σ=t1⋯tk, for transpositionsti}. Theabsolute order onSnis then defined by

σ≤T τ ∶⇔lT(τ) =lT(σ) +lT−1τ).

Theorem (Reiner)

σ∈ Sn is non-crossing if and only if

σ≤T (1,2, . . . ,n) =∶c⇔σ∈ [1,c].

(29)

The absolute order on the symmetric group

Definition

For a permutationσ, let the absolute lengthlT(σ) be the minimal integerk such thatσ can be written as the product ofk transpositions,

lT(σ) ∶=min{k ∶σ=t1⋯tk, for transpositionsti}. Theabsolute order onSnis then defined by

σ≤T τ ∶⇔lT(τ) =lT(σ) +lT−1τ).

Theorem (Reiner)

σ∈ Snis non-crossing if and only if

σ≤T (1,2, . . . ,n) =∶c⇔σ∈ [1,c].

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 11 of 29

(30)

The non-crossing partition lattice of type A

3

Example

ForW = S4,NC(W) ⊆ Sn:

(31)

The absolute order for any real reflection group

Definition

LetW be a real reflection group (= Coxeter group) and letω∈W. Let itsabsolute lengthlT(ω)be the minimal integer k such that ω can be written as the product ofk reflections,

lT(ω) ∶=min{k ∶σ=t1⋯tk, for reflectionsti}. Theabsolute order onW is defined by

ω≤T ω∶⇔lT) =lT(ω) +lT−1ω).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 13 of 29

(32)

The absolute order for any real reflection group

In the absolute order, the intervall[1,c]doesnotdepend on the specific choice of the Coxeter elementc,

[1,c] ≃ [1,c], for Coxeter elementsc,c.

Definition

Fix a real reflection groupW and a Coxeter elementc. The non-crossing partition latticeassociated to W is defined as

NC(W) ∶= [1,c].

For any Coxeter element c, the intervall [1,c] is alattice with many nice properties.

(33)

The absolute order for any real reflection group

In the absolute order, the intervall[1,c]doesnotdepend on the specific choice of the Coxeter elementc,

[1,c] ≃ [1,c], for Coxeter elementsc,c.

Definition

Fix a real reflection groupW and a Coxeter elementc. The non-crossing partition latticeassociated to W is defined as

NC(W) ∶= [1,c].

For any Coxeter element c, the intervall [1,c]is a lattice with many nice properties.

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 14 of 29

(34)

Enumeration of NC (W )

Theorem (Reiner, Bessis-Reiner)

Let W be a real reflection group. Then non-crossing partitions are counted by the W -Catalan numbers,

#NC(W) =Cat(W) ∶=∏l

i=1

di+h di

,

where

l is the number of simple reflections in W ,

h is the Coxeter number,

d1, . . . ,dl are the degrees of the fundamental invariants.

(35)

Cat(W ) for all irreducible real reflection groups

An−1 Bn Dn

n+11 (2nn) (2nn) (2nn) − (2n−2n−1)

I2(m) H3 H4 F4 E6 E7 E8 m+2 32 280 105 833 4160 25080

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 16 of 29

(36)

The root poset

Definition

LetW be a crystallographic reflection group with associated root system Φ⊆Rl and let ∆⊆Φ+⊆Φ be asimple systemand a positive systemrespectively.

Define a partial order on Φ+ by thecovering relation α≺β∶⇔β−α∈∆.

Equipped with this partial order, Φ+is the root posetassociated toW.

(37)

The root poset

Example

The root posets of typeA4 and of typeB3:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 18 of 29

(38)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

(39)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 19 of 29

(40)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

(41)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 19 of 29

(42)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

(43)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 19 of 29

(44)

Non-nesting set partitions and the root poset

Non-nesting set partitions of[n]are in bijection withanti-chainsin the root poset of typeAn−1.

Example

σ= {{1,4},{2,5,7,9},{3,6},{8}}

(45)

Non-nesting partitions

Definition

Fix a crystallographic reflection groupW with associated root poset Φ+. An antichain in Φ+ is called non-nesting partition,

NN(W) ∶= {non-nesting partitions A⊆Φ+}.

Example

The 5 antichains in the root poset of typeA2:

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 20 of 29

(46)

Non-nesting partitions

Definition

Fix a crystallographic reflection groupW with associated root poset Φ+. An antichain in Φ+ is called non-nesting partition,

NN(W) ∶= {non-nesting partitions A⊆Φ+}. Example

The 5 antichains in the root poset of typeA2:

(47)

Enumeration of NN(W )

Theorem (Athanasiadis)

Let W be a crystallographic reflection group. Then

#NN(W) =Cat(W) =#NC(W).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 21 of 29

(48)

The area statistic on NN (W )

To an antichainA⊆Φ+, define the area statisticas area(A) ∶=#IA, where

IA∶= {α∈Φ+∶α≤β for someβ∈A}. Example (continued)

( ) =

(49)

Back to the module from the beginning

Conjecture

H(M;q,1) = ∑

A∈NN(W)

qarea(A).

In typeAthe conjecture is known to be true and furthermore MacMahon’s Major indexmaj on the associated Dyck path provides

qNH(M;q,q−1) = ∑

A∈NN(W)

qmaj(A)

= 1

[n+1]q[2n n]

q

=∏l

i=1

[di+h]q [di]q

.

whereN is the number of positive roots(Garsia & Haiman).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 23 of 29

(50)

Back to the module from the beginning

Conjecture

H(M;q,1) = ∑

A∈NN(W)

qarea(A).

In typeAthe conjecture is known to be true and furthermore MacMahon’s Major indexmaj on the associated Dyck path provides

qNH(M;q,q−1) = ∑

A∈NN(W)

qmaj(A)

= 1

[n+1]q[2n n]

q

=∏l

i=1

[di+h]q [di]q

.

whereN is the number of positive roots(Garsia & Haiman).

(51)

The bijection in type A

Defineφto be the map fromNN(Sn) to NC(Sn) = [1,(1, . . . ,n)]

by the rule shown in the following picture:

(1,7,9)(2,3,4,↧ 5) ∈NC(Sn)

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 24 of 29

(52)

The bijection in type A

Defineφto be the map fromNN(Sn) to NC(Sn) = [1,(1, . . . ,n)]

by the rule shown in the following picture:

(1,7,9)(2,3,4,↧ 5) ∈NC(Sn)

(53)

The bijection in type A

Defineφto be the map fromNN(Sn) to NC(Sn) = [1,(1, . . . ,n)]

by the rule shown in the following picture:

(1,7,9)(2,3,4,↧ 5)∈NC(Sn)

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 24 of 29

(54)

The bijection in type A

Defineφto be the map fromNN(Sn) to NC(Sn) = [1,(1, . . . ,n)]

by the rule shown in the following picture:

(1,7,9)(2,3,4,↧ 5) ∈NC(Sn)

(55)

Properties of the bijection

Theorem

The mapφis a bijection between NN(Sn) and NC(Sn)which sends

area to the (ordinary) length functionlS in the Coxeter group of type A,

maj to2N−maj−imaj, wheremaj is the Major index of a permutation andimaj the Major index of the inverse permutation.

Corollary

H(M;q,1) = ∑

σ∈NC(W)

qinv(σ), qNH(M;q,q−1) = ∑

σ∈NC(W)

qmaj(σ)+imaj(σ).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 25 of 29

(56)

Properties of the bijection

Theorem

The mapφis a bijection between NN(Sn) and NC(Sn)which sends

area to the (ordinary) length functionlS in the Coxeter group of type A,

maj to2N−maj−imaj, wheremaj is the Major index of a permutation andimaj the Major index of the inverse permutation.

Corollary

H(M;q,1) = ∑

σ∈NC(W)

qinv(σ), qNH(M;q,q−1) = ∑

σ∈NC(W)

qmaj(σ)+imaj(σ).

(57)

Properties of the bijection

Example (continued)

(1,7,9)(2,3,4,5) = [7,3,↧4,5,2,6,9,8,1] ∈NC(Sn)

lS =inv=#⎧⎪⎪⎪

⎨⎪⎪⎪⎩

(7,3),(7,4),(7,5),(7,2),(7,6),(7,1), (3,2),(3,1),(4,2),(4,1),(5,2),(5,1),

(2,1),(6,1),(9,8),(9,1),(8,1)

⎫⎪⎪⎪⎬⎪⎪⎪

=17

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 26 of 29

(58)

The bijection in type B

We can also define an bijection betweenNN(W) and

NC(W) = [1,c] wherec is a certain Coxeter element with the following properties:

it sends the statistic area almost to the (ordinary) length function lS in the Coxeter group of typeB,

it sends the statistic maj almost to 2N−maj−imaj, where maj is almostthef-Major index of a signed permutation (Adin, Roichman) and imaj is the f-Major index of the inverse signed permutation.

(59)

The bijection in type B

Corollary

qNH(M;q,q−1) = ∑

σ∈NC(W)

qmaj(rev(σ))+imaj(rev(σ))

= [2n n]

q2

=∏l

i=1

[di+h]q

[di]q .

Conjecture

H(M;q,1) = ∑

σ∈NC(W)

qlS(rev(σ)).

Christian Stump – A bijection between non-crossing and non-nesting partitions of typesAandB 28 of 29

(60)

A hope in type B and a remark on type D

Hope

In typeB, this bijection equipsNN(W) with more structure and we hope that this could help to find a statistic tstat onNN(W) to describe the whole Hilbert series of theW-module M in this type.

Remark

As the involution rev makes the situation much more difficult we were so far not able to find an analogous bijection in typeD.

参照

関連したドキュメント

Theorem 1.6 For every f in the group M 1 of 1. 14 ) converts the convolution of multiplicative functions on non-crossing partitions into the multiplication of formal power

Includes some proper curves, contrary to the quasi-Belyi type result.. Sketch of

Saturated chains in non-crossing partition posets... Poset of

Finite difference operator on words Non commutative Gandhi polynomials The Dumont-Foata polynomials. Commutative version Non commutative version A combinatorial

In particular, we find that, asymptotically, the expected number of blocks of size t of a k-divisible non-crossing partition of nk elements chosen uniformly at random is (k+1)

I The bijection sending the area to the sum of the major and the inverse major index can be generalized to types B and C but fails to exist in type D... Non-crossing and non-nesting

Since the support-tilting modules for a Dynkin algebra of Dynkin type ∆ correspond bijectively to the generalized non-crossing partitions of type ∆, the calculations pre- sented

A bijection between noncrossing and nonnesting partitions of types A and B..