Chains in non-crossing partition posets

Chains in non-crossing partition posets

B´er´enice Delcroix-Oger work in progress

with Matthieu Josuat-Verg`es (LIGM) and Lucas Randazzo (LIGM)

SLC 82 Curia & 9th combinatorics days April 2019

Outline

1 Saturated chains in non-crossing partition posets

2 Minimal factorisations of a cycle

3 2-partition posets

Saturated chains in non-crossing partition posets

1

Poset of non-crossing partitions

Definition (Kreweras 1972)

non-crossing partitiononn elements=

set partition of {1, . . . ,n} which parts do not intersect

1 2 3

4 5 7 6 8 9 10

11 12

Ordered by refinement.

1 2 3

4 5 7 6 8 9 10

11 12

≤

1 2 3

4 5 7 6 8 9 10

11 12

, not comp.

1 2 3

4 5 7 6 8 9 10

11 12

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5

3 1

4 1

3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4

1 3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413 → parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413

→ parking function !!

1

Saturated chains in NCP Poset [Stanley 1996]

Definition

A saturated chainin NC_n is a maximal chain π₁ < . . . < πn−2. 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

≤ 1

2 3 4 5 6

≤

1 2 3 4 5 6

≤

1 2 3 4 5 6

1 3 6 2 4 5 3

1

4 1

3

↔

31413 →parking function !!

1

From parking functions to planar binary trees

Chains in NCPP Parking functions Decorated Dyck paths

1 4 3 2

111 123

1 4 2 3 1 4 2 3 1 4 2 3

112 121 211

ba c

1 2 4 3 1 2 4 3 1 2 4 3

122 212 221

a b c

1 3 2 4 1 3 4 2 1 3 4 2

113 131 311

ab c

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

123 132 213 231

312 321 a b

c

1

From parking functions to planar binary trees

Chains in NCPP Parking functions Decorated Dyck paths 1 4 3 2

111 123

1 4 2 3 1 4 2 3 1 4 2 3

112 121 211

ba c

1 2 4 3 1 2 4 3 1 2 4 3

122 212 221

a b c

1 3 2 4 1 3 4 2 1 3 4 2

113 131 311

ab c

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

123 132 213 231

312 321 a b

c

1

From parking functions to planar binary trees

Chains in NCPP Parking functions Decorated Dyck paths 1 4 3 2

111 123

1 4 2 3 1 4 2 3 1 4 2 3

112 121 211

ba c

1 2 4 3 1 2 4 3 1 2 4 3

122 212 221

a b c

1 3 2 4 1 3 4 2 1 3 4 2

113 131 311

ab c

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

123 132 213 231

312 321 a b

c

1

From parking functions to planar binary trees

Chains in NCPP Parking functions Decorated Dyck paths 1 4 3 2

111 123

1 4 2 3 1 4 2 3 1 4 2 3

112 121 211

ba c

1 2 4 3 1 2 4 3 1 2 4 3

122 212 221

a b c

1 3 2 4 1 3 4 2 1 3 4 2

113 131 311

ab c

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

123 132 213 231

312 321 a b

c

1

π₁: Chains in NCPP → PBT π2: Decorated Dyck paths→ PBT

Shape

π₁ 6 4 3 2 1

π₂ 6 3 3 3 1

1

Hook formula(s)

Proposition (DO, Josuat-Verg`es) The multiplicity of a given leveled tree T

W(T) = ^Y

v∈L(T)

(h_v + 1),

where L(T)= {left children in T}

and h_v = nbr of inner vertices in the subtree of T rooted in v .

1

Hook formula(s)

Proposition (DO, Josuat-Verg`es) The multiplicity of a given leveled tree T

W(T) = ^Y

v∈L(T)

(h_v + 1),

where L(T)= {left children in T}

and h_v = nbr of inner vertices in the subtree of T rooted in v .

1

Hook formula(s)

Proposition (DO, Josuat-Verg`es) The multiplicity of a given leveled tree T

W(T) = ^Y

v∈L(T)

(h_v + 1),

where L(T)= {left children in T}

and h_v = nbr of inner vertices in the subtree of T rooted in v .

4

3 2

1

Hook formula(s)

Proposition (DO, Josuat-Verg`es) The multiplicity of a given leveled tree T

W(T) = ^Y

v∈L(T)

(hv + 1),

where L(T)= {left children in T}

and h_v = nbr of inner vertices in the subtree of T rooted in v .

4

3 2

Corollary (Hook formula) (n+ 1)ⁿ⁻¹ =^X

T

n!

Q

v∈V(T)h_v × ^Y

v∈L(T)

(h_v + 1)

where the sum runs over any complete binary tree T .

1

Hook formula(s)

Corollary (Hook formula) (n+ 1)ⁿ⁻¹ =^X

T

n!

Q

v∈V(T)h_v × ^Y

v∈L(T)

(h_v + 1)

where the sum runs over any complete binary tree T . Proposition (Postnikov 2005)

(n+ 1)ⁿ⁻¹ =^X

T

n!

2ⁿ Y

v∈V(T)

( 1 hv

+ 1)

Rk: ^P_TW(T) given by A0088716

Minimal factorisations of a cycle

2

Minimal factorisations of a cycle

Definition

A factorisation of (1 2 . . . n),σ₁· · ·σ_j, is minimalif^P_il(σ_i) =n+j−1.

Proposition (Biane 1997)

Minimal factorizations

⇔

Chains of NCPˆ0≤π₁ ≤ · · · ≤ˆ1

s.t. l(σi) blocks are merged between πi and πi−1.

2

Enumeration

The number of factorisations (1,2, . . . ,kn+ 1) =σ₁· · ·σ_n whereσ_i is a cycle on k+ 1 elements is

(kn+ 1)ⁿ⁻¹.

Proposition (DO - Josuat-Verg`es)

We have with T running over plane(k+ 1)-ary trees with n increasingly-labeled internal vertices:

(kn+ 1)ⁿ⁻¹ =^X

T

Y

v left vertex

hv,

where hv is equal to the number of leaves above v .

→ 5

2

YAHF

Proposition (DO - Josuat-Verg`es)

We have with T running over plane (k+ 1)-ary trees with n increasingly-labeled internal vertices:

(kn+ 1)ⁿ⁻¹=^X

T

Y

v left vertex

hv,

Corollary

Considering planar (k+ 1)-ary trees T , we get:

(kn+ 1)ⁿ⁻¹=^X

T

Y

v left vertex

hv

!

× n!

Q

v hv−1

k

2-partition posets

3

2-partitions [Edelmann 1980]

Definition

A 2-partitionis a couple (P,Q)_φ, where P is a non-crossing partition, Q is set-partition

andφis a bijections between parts of P and parts of Q s.t.

|P_i|=|φ(P_i)|.

Example:

( • •,{14}{3}{257}{6})₃₄₁₂ ↔ 2 6 5 1 4 7 3• •

3

2-partitions [Edelmann 1980]

Definition

A 2-partitionis a couple (P,Q)_φ, where P is a non-crossing partition, Q is set-partition

andφis a bijections between parts of P and parts of Q s.t.

|P_i|=|φ(P_i)|.

Example:

( • •,{14}{3}{257}{6})₃₄₁₂ ↔ 2 6 5 1 4 7 3• • Order : (P,Q)_φ≤(P⁰,Q⁰)_ψ iff P ≤P⁰,Q ≤Q⁰ and the bijections commute with the order

3

2-partition poset on 3 vertices [Edelman]

1 2 3 1 3 2•

1 2 3•

2 1 3•

1 2 3

• 2 1 3•

3 1 2

• 1 2 3•

1 3 2•

1 3 2• 1 2 3

• • •

1 3 2

• • •

2 1 3

• • •

3 1 2

• • •

2 3 1

• • •

3 2 1

• • •

3

2-partition poset on 3 vertices P 2

[Edelman]

111

112 121 211 122 212 221 113 131 311

123 132 213 231 312 321

3

Zeta polynomial

Definition (Stanley 1974)

The Zeta polynomialof the posets of 2-partitions is defined by:

ζ(l,k,n) =|{π₁ ≤. . . π_k|π_i ∈P2_n,rk(π_k) =l}|

Proposition (DO - Josuat-Verg`es - Randazzo) ζ(l,k,n) =l! kn

l

!

S(n,l+ 1)

In particular, ζ(l,−1,n) is given by A198204. Corollary (Edelman)

X

l

ζ(l,k,n) = (nk+ 1)ⁿ⁻¹

3

Zeta polynomial

Definition (Stanley 1974)

The Zeta polynomialof the posets of 2-partitions is defined by:

ζ(l,k,n) =|{π₁ ≤. . . π_k|π_i ∈P2_n,rk(π_k) =l}|

Proposition (DO - Josuat-Verg`es - Randazzo) ζ(l,k,n) =l! kn

l

!

S(n,l+ 1)

In particular, ζ(l,−1,n) is given by A198204.

Corollary (Edelman)

X

l

ζ(l,k,n) = (nk+ 1)ⁿ⁻¹

3

Zeta polynomial

Definition (Stanley 1974)

The Zeta polynomialof the posets of 2-partitions is defined by:

ζ(l,k,n) =|{π₁ ≤. . . π_k|π_i ∈P2_n,rk(π_k) =l}|

Proposition (DO - Josuat-Verg`es - Randazzo) ζ(l,k,n) =l! kn

l

!

S(n,l+ 1)

In particular, ζ(l,−1,n) is given by A198204.

Corollary (Edelman)

X

l

ζ(l,k,n) = (nk+ 1)ⁿ⁻¹

3

Some species

Proposition

The species of weak k-chains satisfies the following relation:

C_k,t^l =^X

p≥1

C_k−1,t^l,p ×C_k,t^l + 1^p,

whereC_k−1,t^l,p is the species which coincides withC_k−1,t^l on any set of size p and send any other set to the empty set.

Obrigada pela vossa aten¸c˜ ao !

3

Some species

Proposition

The species of weak k-chains satisfies the following relation:

C_k,t^l =^X

p≥1

C_k−1,t^l,p ×C_k,t^l + 1^p,

whereC_k−1,t^l,p is the species which coincides withC_k−1,t^l on any set of size p and send any other set to the empty set.

Obrigada pela vossa aten¸c˜ ao !