72ndS´eminaireLotharingiendeCombinatoire,LyonMarch24,2014 MyrtoKallipolitiandHenriM¨uhle On m -CoverPosetsandTheirApplications

(1)

Them-Cover Poset Them-Tamari Lattices Morem-Tamari Like Lattices

On m-Cover Posets and Their Applications

Myrto Kallipoliti and Henri M¨ uhle

Universit¨ at Wien

72nd S´ eminaire Lotharingien de Combinatoire, Lyon

March 24, 2014

(2)

Outline

The m-Cover Poset Basics

Some Properties The m-Tamari Lattices

Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

(3)

Basics Some Properties

Outline

The m-Cover Poset Basics

Some Properties The m-Tamari Lattices

Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

(4)

The m-Cover Poset

let P = (P , ≤) be a poset

bounded poset: a poset with a least and a greatest element, denoted by ˆ 0 and ˆ 1

for m > 0, consider m-tuples p = ˆ 0, ˆ 0, . . . , ˆ 0

| {z }

l

1

, p, p , . . . , p

| {z }

l

2

, q, q, . . . , q

| {z }

l

3

for p, q ∈ P with ˆ 0 6= p l q

where l is the covering relation of P

(5)

The m-Cover Poset

write p = ˆ 0 ^l

¹

, p ^l

²

, q ^l

³

instead define P ^hmi = n

ˆ 0 ^l

¹

, p ^l

²

, q ^l

³

| 0 _P 6= p l q, l ₁ + l ₂ + l ₃ = m o m-cover poset of P : the poset P ^hmi = P ^hmi , ≤

where ≤ means componentwise order

(6)

Example

P

2 P ^h2i

(1,2)

(2,2)

(7)

Example

P

2 3

P ^h2i

(1,2) (2, 2) (1, 3)

(2,3)

(3,3)

(8)

Example

P

2 3 4

P ^h2i

(1,2) (2, 2) (1, 3)

(2, 3) (3, 3)

(1, 4)

(3,4)

(4,4)

(9)

Example

P

2 3

4 P ^h2i

(1, 2) (2, 2)

(1, 3) (3, 3) (1,4)

(3, 4) (4,4)

(2, 4)

(10)

Example

P

2 4 3

5 P ^h2i

(1, 2) (2, 2)

(1, 3) (3, 3)

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

(5,5)

(11)

Example

P

2 3

4 5

P ^h2i

(1, 2) (2, 2)

(1, 3) (3,3)

(1,4) (4,4)

(2, 4)

(1, 5) (3, 5) (4, 5)

(5, 5)

(12)

A Characterization

Theorem (Kallipoliti & , 2013)

Let P be a bounded poset. Then, P ^hmi is a lattice for all m > 0 if and only if P is a lattice and the Hasse diagram of P with ˆ 0 removed is a tree rooted at ˆ 1.

these posets are (in principle) so-called chord posets

see Kim, M´ esz´ aros, Panova, Wilson: “Dyck Tilings, Increasing Trees, Descents and Inversions” (JCTA 2014)

they have a natural connection to Dyck paths

(13)

A Characterization

Theorem (Kallipoliti & , 2013)

Let P be a bounded poset. Then, P ^hmi is a lattice for all m > 0 if and only if P is a lattice and the Hasse diagram of P with ˆ 0 removed is a tree rooted at ˆ 1.

these posets are (in principle) so-called chord posets

see Kim, M´ esz´ aros, Panova, Wilson: “Dyck Tilings, Increasing Trees, Descents and Inversions” (JCTA 2014)

they have a natural connection to Dyck paths

(14)

Example

P

1 2

3 4

5 P ^h2i

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

(3,3) (4,4)

(3, 5) (4, 5)

(5, 5)

(15)

Example

P

2 3 4

5 P ^h2i

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

(3,3) (4,4)

(3, 5) (4, 5)

(5, 5)

(16)

Irreducible Elements

join-irreducible element of P : a non-minimal element p ∈ P with a unique lower cover p ?

meet-irreducible element of P : a non-maximal element p ∈ P with a unique upper cover p ^?

J (P): set of all join-irreducible elements of P M(P ): set of all meet-irreducible elements of P

this is of course abuse of notation!

(17)

Irreducible Elements

Proposition (Kallipoliti & , 2013)

Let P be a bounded poset with ˆ 0 ∈ M(P / ) and ˆ 1 ∈ J / (P ), and let m > 0. Then,

J P ^hmi

= n

ˆ 0 ^s , p ^m−s

| p ∈ J (P ) and 0 ≤ s < m o

, and

M P ^hmi

= n

p ^s , (p ^? ) ^m−s

| p ∈ M(P ) and 1 ≤ s ≤ m o

.

(18)

Irreducible Elements

Corollary (Kallipoliti & , 2013)

Let P be a bounded poset with ˆ 0 ∈ M(P / ) and ˆ 1 ∈ J / (P ), and let m > 0. Then,

J P ^hmi = m ·

J (P )

and

M P ^hmi = m ·

M(P)

.

(19)

Cardinality

Proposition (Kallipoliti & , 2013)

Let P be a bounded poset with n elements, c cover relations and a atoms. Then for m > 0, we have

P ^hmi

= (c − a) m

2 + m(n − 1) + 1.

atoms are elements covering ˆ 0

(20)

Basics

Them-Cover Poset of the Tamari Lattices A More Explicit Approach

Outline

The m-Cover Poset Basics

Some Properties

The m-Tamari Lattices Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

(21)

Basics

m-Dyck Paths

m-Dyck path: a lattice path from (0, 0) to (mn, n) consisting only of up-steps (0, 1) and right-steps (1, 0) and staying weakly above x = my

D ^(m) _n : set of all m-Dyck paths of parameter n we have

D _n ^(m)

= Cat ^(m) (n) = ¹ _n ^mn+n _n−1

these are the Fuss-Catalan numbers

step sequence: u p = (u 1 , u 2 , . . . , u n ) with u 1 ≤ u 2 ≤ · · · ≤ u n

and u i ≤ m(i − 1) for 1 ≤ i ≤ n

(22)

Basics

Example

p ∈ D ⁽⁴⁾ ₅

(23)

Basics

Example

p ∈ D ⁽⁴⁾ ₅

u₁= 0 u₂= 2 u₃= 2 u₄= 9 u₅= 15

u p = (0, 2, 2, 9, 15)

(24)

Basics

Rotation Order on D ^(m) n

rotation order: exchange a right-step of p ∈ D ^(m) _n , which is followed by an up-step, with the subpath of p starting with this up-step

m-Tamari lattice: the lattice T _n ^(m) = D _n ^(m) , ≤ _R

where ≤

R

denotes the rotation order

we omit superscripts, when m = 1

(25)

Basics

Example

p ∈ D ⁽⁴⁾ ₅

(26)

Basics

Example

p ∈ D ⁽⁴⁾ ₅

(27)

Basics

Example

p ∈ D ⁽⁴⁾ ₅

(28)

Basics

Example

p ⁰ ∈ D ⁽⁴⁾ ₅

(29)

Basics

Example

p ⁰ ∈ D ⁽⁴⁾ ₅

(30)

Basics

Example

D

₃⁽²⁾

, ≤

R

(31)

Basics

Example

D

₃⁽²⁾

, ≤

R

Behold: this is the

2-cover poset of the

pentagon lattice!

(32)

Basics

Example

D

₃⁽²⁾

, ≤

R

Behold: this is the 2-cover poset of the pentagon lattice!

The pentagon lattice

is isomorphic to T ₃ .

(33)

Basics

The Posets T n ^hmi

the Hasse diagram of T _n with 0 removed is a tree if and only if n ≤ 3

Observation

The poset T _n ^hmi is a lattice for all m > 0 if and only if n ≤ 3.

(34)

Basics

The Posets T n ^hmi

T _n has Cat(n) elements, n − 1 atoms, and ⁿ⁻¹ ₂ Cat(n) cover relations

Observation We have

D ^hmi _n

= n − 1 2

Cat(n) − 2 m

2 + m · Cat(n) − m + 1.

(35)

Basics

The Posets T n ^hmi

for n > 3 and m > 1: T _n ^hmi is not a lattice and D _n ^hmi

< Cat ^(m) (n)

idea: consider a lattice completion of T _n ^hmi

Dedekind-MacNeille completion: the smallest lattice containing a given poset, denoted by DM

Theorem (Kallipoliti & , 2013) For m, n > 0, we have T _n ^(m) ∼ = DM T _n ^hmi

.

(36)

Basics

Sketch of Proof

how do you prove such a statement?

recall the following result ... Theorem (Banaschewski, 1956)

If P is a finite lattice, then P ∼ = DM J (P ) ∪ M(P)

.

... and investigate the irreducibles

(37)

Basics

Sketch of Proof

how do you prove such a statement?

recall the following result ...

Theorem (Banaschewski, 1956)

If P is a finite lattice, then P ∼ = DM J (P ) ∪ M(P)

.

... and investigate the irreducibles

(38)

Basics

Irreducibles of T n ^(m)

a meet-irreducible element of T ₈ ⁽⁴⁾ :

(39)

Basics

Irreducibles of T n ^(m)

Proposition (Kallipoliti & , 2013) Let p ∈ D ^(m) _n . Then, p ∈ M T _n ^(m)

if and only if its step sequence u _p = (u ₁ , u ₂ , . . . , u _n ) satisfies

u j =

( 0, for j ≤ i ,

a, for j > i ,

where 1 ≤ a ≤ mi and 1 ≤ i < n.

(40)

Basics

Irreducibles of T n ^(m)

a join-irreducible element of T ₈ ⁽⁴⁾ :

(41)

Basics

Irreducibles of T n ^(m)

Proposition (Kallipoliti & , 2013) Let p ∈ D ^(m) _n . Then, p ∈ J T _n ^(m)

if and only if its step sequence u _p = (u ₁ , u ₂ , . . . , u _n ) satisfies

u j =

( m(j − 1), for j ∈ {i, / i + 1, . . . , k},

m(j − 1) − s , for j ∈ {i, i + 1, . . . , k},

for exactly one i ∈ {1, 2, . . . , n}, where k > i and 1 ≤ s ≤ m.

(42)

Basics

Irreducibles of T n ^(m)

Corollary (Kallipoliti & , 2013)

M T _n ^(m)

= m ⁿ ₂

for every m, n > 0.

Corollary (Kallipoliti & , 2013)

J T _n ^(m)

= m ⁿ ₂

for every m, n > 0.

(43)

Basics

Irreducibles of T n ^hmi

the previous results also imply what the irreducibles of T _n look like

we have characterized the irreducibles of P ^hmi for arbitrary bounded posets earlier

put these things together!

but how?

elements of T

n^(m)

: m-Dyck paths

elements of T

n^hmi

: m-tuples of Dyck paths

(44)

Basics

Irreducibles of T n ^hmi

the previous results also imply what the irreducibles of T _n look like

we have characterized the irreducibles of P ^hmi for arbitrary bounded posets earlier

put these things together!

but how?

elements of T

n^(m)

: m-Dyck paths

elements of T

n^hmi

: m-tuples of Dyck paths

(45)

Basics

The Strip-Decomposition

(46)

Basics

The Strip-Decomposition

(47)

Basics

The Strip-Decomposition

(48)

Basics

The Strip-Decomposition

(49)

Basics

The Strip-Decomposition

(50)

Basics

The Strip-Decomposition

(51)

Basics

The Strip-Decomposition

(52)

Basics

The Strip-Decomposition

We obtain an injective map δ : D ^(m) _n → D _n m

!

(53)

Basics

Irreducibles of T n ^hmi

Corollary (Kallipoliti & , 2013) For m, n > 0, we have

J T _n ^hmi

= m ⁿ ₂

=

M T _n ^hmi .

Proposition (Kallipoliti & , 2013) If p ∈ J T _n ^(m)

, then δ(p) ∈ J T _n ^hmi

. If p ∈ M T _n ^(m) , then δ(p) ∈ M T _n ^hmi

.

(54)

Basics

Irreducibles of T n ^hmi

Proposition (Kallipoliti & , 2013) The map δ is an poset isomorphism between

J T _n ^(m) , ≤ _R

and

J T _n ^hmi , ≤ _R

, respectively between

M T _n ^(m) , ≤ _R

and

M T _n ^hmi , ≤ _R

.

Proposition (Kallipoliti & , 2013)

Every element in D ^hmi _n can be expressed as a join of elements in J T _n ^hmi

.

(55)

Basics

Proving the Connection

Theorem (Kallipoliti & , 2013) For m, n > 0, we have T _n ^(m) ∼ = DM T _n ^hmi

.

Proof

T _n ^(m) ∼ = DM

J T _n ^(m)

∪ M T _n ^(m)

∼ = DM

J T _n ^hmi

∪ M T _n ^hmi

∼ = DM T _n ^hmi

.

(56)

Basics

Bouncing Dyck Paths

let ∧ _R and ∨ _R denote meet and join in T _n define a map

β i ,j : (D _n ) ^m → (D _n ) ^m ,

(q 1 , q ₂ , . . . , q _m ) 7→ (q 1 , . . . , q _i ∧ _R q _j , . . . , q _i ∨ _R q _j , . . . , q _m ) bouncing map: β = β m−1,m ◦ · · · ◦ β _2,3 ◦ β _1,m ◦ · · · ◦ β _1,3 ◦ β _1,2 , define ζ : D ^(m) _n → (D _n ) ^m , p 7→ β ◦ δ(p)

Conjecture The posets

D ^(m) _n , ≤ _R and

ζ D ^(m) _n , ≤ _R

are isomorphic.

(57)

Basics

Bouncing Dyck Paths

let ∧ _R and ∨ _R denote meet and join in T _n define a map

β i ,j : (D _n ) ^m → (D _n ) ^m ,

(q 1 , q ₂ , . . . , q _m ) 7→ (q 1 , . . . , q _i ∧ _R q _j , . . . , q _i ∨ _R q _j , . . . , q _m ) bouncing map: β = β m−1,m ◦ · · · ◦ β _2,3 ◦ β _1,m ◦ · · · ◦ β _1,3 ◦ β _1,2 , define ζ : D ^(m) _n → (D _n ) ^m , p 7→ β ◦ δ(p)

Conjecture The posets

D ^(m) _n , ≤ _R and

ζ D ^(m) _n , ≤ _R

are isomorphic.

(58)

Basics

Example

δ(D

⁽²⁾₃

), ≤

R

(59)

Basics

Example

ζ(D

₃⁽²⁾

), ≤

R

(60)

The Dihedral Groups Other Coxeter Groups

Outline

The m-Cover Poset Basics

Some Properties

The m-Tamari Lattices Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

(61)

A Generalization

T _n is associated with the Coxeter group A n−1

Reading’s Cambrian lattices provide a generalization of T _n to the other Coxeter groups

what about the m-cover posets of other Cambrian lattices?

(62)

Cambrian Lattices Associated with the Dihedral Groups

D _k : the dihedral group of order 2k C _k : the following poset:

a₁ b

a₂ .. . a_k−1

1

(63)

Properties of C _k ^hmi

Proposition (Kallipoliti & , 2013)

For k > 1 and m > 0, the poset C _k ^hmi is a lattice with

m+1 2

k + m + 1 elements.

m+1 2

k + m + 1 = Cat ^(m) (D _k )

(64)

Properties of C _k ^hmi

Proposition (Kallipoliti & , 2013)

For k > 1 and m > 0, the poset C _k ^hmi is in fact trim, and its M¨ obius function takes values only in {−1, 0, 1}.

this generalizes some structural and topological properties of

C _k

(65)

Example

C ₄

c₁ a₁

c₂ c₃

1

C ₄ ^h2i

(0,c₁) (0,a₁) (c₁,c₁) (0,c₂)

(c1,c2) (0,c3)

(c₂,c₂) (0,1) (a₁,a₁) (c₂,c₃)

(c₃,c₃)

(c₃,1) (a₁,1) (1,1)

(66)

Other Coxeter Groups

unfortunately, this approach does not work for other Coxeter groups

the 2-cover poset of the B

3

-Tamari lattice has 66 elements ... ... and its Dedekind-MacNeille completion has 88 elements ... ... but Cat

⁽²⁾

(B

3

) = 84

it even fails for the other Cambrian lattices of A n−1

(67)

Other Coxeter Groups

unfortunately, this approach does not work for other Coxeter groups

the 2-cover poset of the B

3

-Tamari lattice has 66 elements ...

... and its Dedekind-MacNeille completion has 88 elements ...

... but Cat

⁽²⁾

(B

3

) = 84

it even fails for the other Cambrian lattices of A n−1

(68)

Other Coxeter Groups

unfortunately, this approach does not work for other Coxeter groups

the 2-cover poset of the B

3

-Tamari lattice has 66 elements ...

... and its Dedekind-MacNeille completion has 88 elements ...

... but Cat

⁽²⁾

(B

3

) = 84

it even fails for the other Cambrian lattices of A n−1

(69)

Thank you!

(70)

Fuss-Catalan Numbers for Coxeter Groups

let W be a Coxeter group of rank n, and let d ₁ , d ₂ , . . . , d _n be the degrees of W

define Cat ^(m) (W ) = Q n i=1

md

n

+d

i

d

i

(71)

Fuss-Catalan Numbers for Coxeter Groups

let W be a Coxeter group of rank n, and let d ₁ , d ₂ , . . . , d _n be the degrees of W

define Cat ^(m) (W ) = Q n i=1

md

n

+d

i

d

i

if W = S _n , then d i = i + 1 for 1 ≤ i < n we have Cat ^(m) (S _n ) = ¹ _n ^mn+n _n−1

= Cat ⁽ⁿ⁾ (m)

(72)

Fuss-Catalan Numbers for Coxeter Groups

let W be a Coxeter group of rank n, and let d ₁ , d ₂ , . . . , d _n be the degrees of W

define Cat ^(m) (W ) = Q n i=1

md

n

+d

i

d

i

if W = D _k , then d 1 = 2 and d 2 = k we have Cat ^(m) (D _k ) = ^m+1 ₂

k + m + 1

(73)

72ndS´eminaireLotharingiendeCombinatoire,LyonMarch24,2014 MyrtoKallipolitiandHenriM¨uhle On m -CoverPosetsandTheirApplications

On m-Cover Posets and Their Applications

Myrto Kallipoliti and Henri M¨ uhle

Universit¨ at Wien

72nd S´ eminaire Lotharingien de Combinatoire, Lyon

March 24, 2014

Outline

The m-Cover Poset Basics

Some Properties The m-Tamari Lattices

Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

Outline

The m-Cover Poset Basics

Some Properties The m-Tamari Lattices

Basics

The m-Cover Poset of the Tamari Lattices A More Explicit Approach

More m-Tamari Like Lattices

The Dihedral Groups

Other Coxeter Groups

The m-Cover Poset

let P = (P , ≤) be a poset

bounded poset: a poset with a least and a greatest element, denoted by ˆ 0 and ˆ 1

for m > 0, consider m-tuples p = ˆ 0, ˆ 0, . . . , ˆ 0

| {z }

l

, p, p , . . . , p

| {z }

l

, q, q, . . . , q

| {z }

l

for p, q ∈ P with ˆ 0 6= p l q

where l is the covering relation of P

The m-Cover Poset

write p = ˆ 0 l

, p l

, q l

instead define P hmi = n

ˆ 0 l

, p l

, q l

| 0 P 6= p l q, l 1 + l 2 + l 3 = m o m-cover poset of P : the poset P hmi = P hmi , ≤

where ≤ means componentwise order

Example

P

2

P h2i

(1,2)

(2,2)

Example

P

2 3

P h2i

(1,2) (2, 2) (1, 3)

(2,3)

(3,3)

Example

P

2 3 4

P h2i

(1,2) (2, 2) (1, 3)

(2, 3) (3, 3)

(1, 4)

(3,4)

(4,4)

Example

P

2 3

4

P h2i

(1, 2) (2, 2)

(1, 3) (3, 3) (1,4)

(3, 4) (4,4)

(2, 4)

Example

P

2 4 3

write p = ˆ 0 ^l

, p ^l

, q ^l

instead define P ^hmi = n

ˆ 0 ^l

, p ^l

, q ^l

| 0 _P 6= p l q, l ₁ + l ₂ + l ₃ = m o m-cover poset of P : the poset P ^hmi = P ^hmi , ≤

P ^h2i

P ^h2i

P ^h2i

P ^h2i

P ^h2i

P ^h2i

Let P be a bounded poset. Then, P ^hmi is a lattice for all m > 0 if and only if P is a lattice and the Hasse diagram of P with ˆ 0 removed is a tree rooted at ˆ 1.

Let P be a bounded poset. Then, P ^hmi is a lattice for all m > 0 if and only if P is a lattice and the Hasse diagram of P with ˆ 0 removed is a tree rooted at ˆ 1.

P ^h2i

P ^h2i

meet-irreducible element of P : a non-maximal element p ∈ P with a unique upper cover p ^?

J P ^hmi

ˆ 0 ^s , p ^m−s

M P ^hmi

p ^s , (p ^? ) ^m−s