A cyclic sieving phenomenon in Catalan Combinatorics

A cyclic sieving phenomenon in Catalan Combinatorics

Christian Stump

Universit´ e du Qu´ ebec ` a Montr´ eal

SLC 64, Lyon

March 30, 2010

Non-crossing partitions

◮ Non-crossing partitions can be defined for any Coxeter group W as

NC(W , c ) :=

ω ∈ W : ℓ _T (ω) + ℓ _T (c ω ⁻¹ ) = ℓ _T (c ) , where c is a Coxeter element and where ℓ _T (ω) denotes the absolute length on W ,

◮ for W = S _n being the symmetric group,

NC ( S _n ) = {ω = c ₁ . . . c _k ∈ S _n : c _i increasing; c _i , c _j non-crossing}, where the Coxeter element c = (1, . . . , n) and where

ω = c ₁ . . . c _k is the cycle notation of ω.

We focus on S _n (and keep the general case in mind).

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 2 of 15

Example: NC ( S ₄ )

3214

(13)

1432

(24)

2134

(12)

1324

(23)

1243

(34)

4231

(14)

3124

(132)

1423

(243)

3412

(13)(24)

2314

(123)

1342

(234)

3241

(134)

2431

(124)

2143

(12)(34)

4321

(14)(23)

4213

(143)

4132

(142)

3142

(1342)

2413

(1243)

3421

(1324)

2341

(1234)

4123

(1432)

4312

(1423)

!! !! !! !! !! !! !! !! !! !!

Q Q

Q Q Q Q

Q Q Q Q

Q Q aa aa aa aa

aa aa

aa aa aa aa PPP PPP

PPP PPP

PPP PPP

PPP PPP Q Q

Q Q Q Q

Q Q Q Q

Q Q aa aa aa aa

aa aa

aa aa aa aa PPP PPP

PPP PPP

PPP PPP

PPP PPP A A

A A A

A A A

@ @

@ @

@

@ @

@

!! !! !! !! !! !! !! !! !! !!

!! !! !! !! !! !! !! !! !! !!

Q Q

Q Q Q Q

Q Q Q Q

Q Q HH HH

HH HH HH HH

HH HH PPP PPP

PPP PPP

PPP PPP

PPP PPP Q Q

Q Q Q Q

Q Q Q Q

Q Q HH HH

HH HH HH HH

HH HH PPP PPP

PPP PPP

PPP PPP

PPP PPP A A

A A A A

A A Q Q

Q Q Q Q

Q Q Q Q

Q Q PPP PPP

PPP PPP

PPP PPP

PPP PPP A A

A A A A

A A

@ @

@ @

@ @

@

@ Q Q

Q Q Q Q

Q Q Q Q

Q Q HH HH

HH HH HH HH

HH HH A A

A A A A

A A

@ @

@ @

@ @

@

@ Q Q

Q Q Q Q

Q Q Q Q

Q Q

@

@@

@@

@ A

AA AA

A

@

@@

@@

@@

@ QQ

QQ QQ

QQ QQ

QQ

@

@@

@@

@@

@ QQ

QQ QQ

QQ QQ

QQ

@

@@

@@

@@

@ QQ

QQ QQ

QQ QQ

QQ

@

@@

@@

@@

@ A

AA AA

AA A

@@

@

@@

@@

@ QQ

QQ QQ

QQ QQ

QQ

Non-nesting partitions

◮ Non-nesting partitions can be defined for any crystallographic Coxeter group W as

NC(W ) := {A ⊂ Φ ⁺ : A antichain}, where Φ ⁺ denotes the root poset of W ,

◮ for W = S _n being the symmetric group, NN( S _n ) is the set of all antichains in

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 4 of 15

Example: NN ( S ₄ )

∅, [12], [23], [34], [13], [24], [14],

[12] − [23], [12] − [34], [23] − [34], [12] − [24],

[13] − [34], [13] − [24], [12] − [23] − [34]

Non-crossing and non-nesting partitions

Theorem (Athanasiadis 2004)

For any crystallographic Coxeter group W of rank ℓ, the number of non-crossing and of non-nesting partitions coincide with the W -Catalan number,

NC(W ) =

NN(W )

= Cat(W ) :=

ℓ

Y

i=1

d _i + h d i

,

where d ₁ ≤ . . . ≤ d _ℓ denote the degrees of the fundamental invariants of W .

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 6 of 15

An important open problem

Different groups found explicit bijections between non-crossing and non-nesting partitions for various types, but the general connection is still open:

Open Problem

Find a type-independent bijection between NC (W ) and NN(W ).

Further refinements

Define a cyclic group action on NC(W ) by Kreweras complementation,

K(ω) := c ω ⁻¹ .

Observe that K ² (ω) = c ω c ⁻¹ is conjugation by c.

Theorem (CSP on non-crossing partitions)

ω ∈ NC(W ) : K ^k (ω) = ω

= Cat(W ; ζ _d ^k ) :=

ℓ

Y

i=1

[d _i + h] _q [d i ] q

q=ζ

_d^k

,

where the product Cat(W ; q) is a q-analogue of the W -Catalan number Cat(W ) and where d = 2h is the order of the cyclic group.

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 8 of 15

Further refinements

◮ The theorem is an instance of the cyclic sieving

phenomenon (which you all know from the SLC 62 one year ago in Heilsbronn, Germany).

◮ It was proved accidentally for the symmetric group by C. Heitsch,

◮ and it was recently proved in much more generality by C. Krattenthaler in an unpublished manuscript and by him together with T. M¨ uller in two articles on 134 pages,

◮ it generalizes a theorem by D. Bessis and V. Reiner on the

CSP by conjugation.

Example (continued): NC ( S ₄ )

(12) 7→ (1234)(12) = (134) 7→ (1234)(143) = (23) 7→ (1234)(23) = (124) 7→ (1234)(142) = (34) 7→ (1234)(34) = (123) 7→ (1234)(132) = (14) 7→ (1234)(14) = (234) 7→ (1234)(243) = (12)

(13) 7→ (1234)(13) = (14)(23) 7→ (1234)(14)(23) = (24) 7→ (1234)(24) = (12)(34) 7→ (1234)(12)(34) = (13) () 7→ (1234)() = (1234)

7→ (1234)(4321) = () Cat( S _n ; q ) = 1+ q ² +q ³ +2q ⁴ +q ⁵ +2q ⁶ + q ⁷ +2q ⁸ +q ⁹ +q ¹⁰ +q ¹² evaluated at 8-th roots of unity gives



 

 

 

 

14 = |NC| if ζ = 1

6 = |NC ^K

⁴

| if ζ = −1

2 = |NC ^K

²

| = |NC ^K

⁶

| if ζ = ±i 0 = |NC ^K | = |NC ^K

³

| = |NC ^K

⁵

| = |NC ^K

⁷

| otherwise

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 10 of 15

Further refinements

Define a cyclic group action on NC(W ) by Panyushev complementation

P(A) := min{t ∈ Φ ⁺ : t 6≤ a for some a ∈ A} ∈ NN(W ).

Conjecture (V. Reiner, SLC 62)

ω ∈ NN(W ) : P ^k (ω) = ω

= Cat(W ; ζ _d ^k ).

Or equivalently, there exists a bijection ψ : NN(W ) ˜ −→ NC(W ) such that

ψ ◦ P = K ◦ ψ.

Example (continued): NN ( S ₄ )

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12

Example (continued): NN ( S ₄ )

12 7→ 23, 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

12, 23, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

12, 23, 34 7→ 13, 24

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

12, 23, 34 7→ 13, 24 7→ 14

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12

12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34 7→ 23

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34 7→ 23

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34 7→ 23 7→ 12, 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34 7→ 23 7→ 12, 34

Example (continued): NN ( S ₄ )

12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24 7→ 12 12, 23, 34 7→ 13, 24 7→ 14 7→ ∅ 7→ 12, 23, 34

12, 34 7→ 23 7→ 12, 34

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15

The type A : Non-crossing handshake configurations

◮ T n set of non-crossing handshake configurations of 2n,

◮ C 2n -action on T n by cyclic permutation of {1, . . . , 2n}.

Theorem

◮ T n , Cat( S _n ; q), C 2n

exhibits the CSP.

◮ We can construct a bijection

ψ ₁ : T n −→NC ˜ ( S _n ), such that ψ ₁ ◦ c = K ◦ ψ ₁ , and a bijection

ψ ₂ : NN( S _n ) ˜ −→T n , such that ψ ₂ ◦ P = c ◦ ψ ₂ .

◮ The construction can be easily generalized to type B .

Towards a uniform bijection

◮ The bijection in type A can be generalized to type B , but so far not to type D,

◮ the exceptional types can be checked by computer.

What does this have to do with a uniform bijection?

Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 14 of 15

Towards a uniform bijection

Theorem (Conjectured by D. Armstrong in all types)

Let L, R be a bipartition of the simple transpositions such that L and R pairwise commute, and let c be the associated bipartite Coxeter element. ψ = ψ ₁ ◦ ψ ₂ : NN( S _n ) ˜ −→NC( S _n , c = c _L c _R ) is the unique bijection with the following inductive property:

ψ : ∅ 7→ c _L ,

ψ ◦ P = K ◦ ψ,

ψ(I ) = Y

s∈L\supp I

s ψ

supp I (I).

Remark

◮ The theorem gives an inductively defined uniform definition of

a bijection between non-nesting and non-crossing partitions in