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 ω −1 ) = ℓ 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 1 . . . c k ∈ S n : c i increasing; c i , c j non-crossing}, where the Coxeter element c = (1, . . . , n) and where
ω = c 1 . . . 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 4 )
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
@
@@
@@
@@
@ A
AA AA
AA A
@@
@
@@
@@
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 4 )
∅, [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 1 ≤ . . . ≤ 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 ω −1 .
Observe that K 2 (ω) = c ω c −1 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=ζ
dk,
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 4 )
(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 2 +q 3 +2q 4 +q 5 +2q 6 + q 7 +2q 8 +q 9 +q 10 +q 12 evaluated at 8-th roots of unity gives
14 = |NC| if ζ = 1
6 = |NC K
4| if ζ = −1
2 = |NC K
2| = |NC K
6| if ζ = ±i 0 = |NC K | = |NC K
3| = |NC K
5| = |NC K
7| 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 4 )
Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15
Example (continued): NN ( S 4 )
12
Example (continued): NN ( S 4 )
12 7→ 23, 34
Christian Stump – A cyclic sieving phenomenon in Catalan Combinatorics LaCIM, UQAM, Montr´eal 12 of 15
Example (continued): NN ( S 4 )
12 7→ 23, 34
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24 7→ 13
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34
Example (continued): NN ( S 4 )
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 4 )
12 7→ 23, 34 7→ 12, 24 7→ 13 7→ 34 7→ 12, 23 7→ 13, 34 7→ 24
Example (continued): NN ( S 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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 4 )
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
ψ 1 : T n −→NC ˜ ( S n ), such that ψ 1 ◦ c = K ◦ ψ 1 , and a bijection
ψ 2 : NN( S n ) ˜ −→T n , such that ψ 2 ◦ P = c ◦ ψ 2 .
◮ 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
