SLC,07/09/2015 VivianePons Alatticeondecreasingtrees:themetasylvesterlattice

(1)

Them-lattices

A lattice on decreasing trees: the metasylvester lattice

Viviane Pons

Universit´ e Paris-Sud

SLC, 07/09/2015

Viviane Pons A lattice on decreasing trees: the metasylvester lattice

(2)

Them-lattices Sylvester classes Decreasing trees

123 213 132

231 312

321 Weak order on permutations

(3)

Motivations Them-lattices

Introduction Sylvester classes Decreasing trees

1234

2134 1324 1243

2314 3124 2143 1342 1423

3214 2341 3142 2413 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Weak Order permutations

2134

2314 3124

3214 2341 4123

3241 3412 4213

3421 4231 4312

4321

Tamari Lattice (1962) Catalan objects:

132-avoiding permutations, Dyck paths, binary trees, triangulations, ...

(4)

1234

2134 1324 1243

2314 3124 2143 1342 1423

3214 2341 3142 2413 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Weak Order permutations

2134

2314 3124

3214 2341 4123

3241 3412 4213

3421 4231 4312

4321

Tamari Lattice (1962) Catalan objects:

132-avoiding permutations

, Dyck paths, binary trees, triangulations, ...

(5)

1234

2134 1324 1243

2314 3124 2143 1342 1423

3214 2341 3142 2413 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Weak Order permutations

1234

2134

2314 3124

3214 2341 4123

3241 3412 4213

3421 4231 4312

4321

Catalan objects:

132-avoiding permutations

, Dyck paths, binary trees, triangulations, ...

(6)

1234

2134 1324 1243

2314 3124 2143 1342 1423

3214 2341 3142 2413 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Weak Order permutations

1234

2134

2314 3124

3214 2341 4123

3241 3412 4213

3421 4231 4312

4321

Tamari Lattice (1962) Catalan objects:

132-avoiding permutations, Dyck paths, binary trees, triangulations, ...

(7)

m-permutations?

Metasylvester lattice

m-Tamari Lattice (2012)*

m-Catalan objects:

m-Dyck paths, (m + 1)-ary trees

* Bergeron, Pr´ eville-Ratelle

(8)

??

m-permutations?

lattice

m-Tamari Lattice (2012)*

m-Catalan objects:

m-Dyck paths, (m + 1)-ary trees

* Bergeron, Pr´ eville-Ratelle

(9)

??

m-permutations?

Metasylvester lattice

m-Tamari Lattice (2012)*

m-Catalan objects:

m-Dyck paths, (m + 1)-ary trees

* Bergeron, Pr´ eville-Ratelle

(10)

Sylvester congruence*

ac . . . b ≡ ca . . . b, a ≤ b < c.

*Hivert, Novelli, Thibon – 2005

(11)

13254

31524 15324

35124 51324

53124

Number of sylvester classes: Catalan

→ in bijection with Binary trees through the binary search tree insertion algorithm

(12)

13254 31254

31524 15324

35124 51324

53124

Number of sylvester classes: Catalan

→ in bijection with Binary trees through the binary search tree insertion algorithm

(13)

13254

31254 13524

31524 15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(14)

13254

31254 13524

31524

15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(15)

13254

31254 13524

31524

15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(16)

13254

31254 13524

31524 15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(17)

13254

31254 13524

31524 15324

35124

51324 53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(18)

13254

31254 13524

31524 15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(19)

13254

31254 13524

31524 15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(20)

13254

31254 13524

31524 15324

35124 51324

53124

→ in bijection with Binary trees through the binary search tree insertion algorithm

(21)

13254

31254 13524

31524 15324

35124 51324

53124

Number of sylvester classes: Catalan

→ in bijection with Binary trees through the binary search tree insertion algorithm

(22)

1234

2134 1324

3124

1243

1423

4123

2314 2143

2413

4213

1342

3142

3412

3214 2341 1432

4132

4312

3241 2431

4231 3421

4321

(23)

I Permutations : n!

I Binary trees: _n+1 ¹ ²ⁿ _n

(24)

I Permutations : n!

I Decreasing binary trees: n!

I Binary trees: _n+1 ¹ ²ⁿ _n

(25)

Permutation: 215634

(26)

Permutation: 215634

215634

(27)

Permutation: 215634

6 215 34

(28)

Permutation: 215634

6 5 21

4 3

(29)

Permutation: 215634

6 5 2

1 4 3

(30)

Lattice onm-permutations Metasylvester lattice

m-permutations

1 ^m 2 ^m . . . n ^m

Example: 3244123515 is a 2-permutation of size 5.

(31)

m-permutations

A m-permutation of size n is a permutation of the word 1 ^m 2 ^m . . . n ^m

(32)

Them-lattices Metasylvester lattice

m-permutations

A m-permutation of size n is a permutation of the word 1 ^m 2 ^m . . . n ^m

Example: 3244123515 is a 2-permutation of size 5.

(33)

The m-permutations lattice

1122 1212

2112 1221

2121 2211

1324

3124 1342

3142 3412

(34)

The m-permutations lattice

1122 1212

2112 1221

2121 2211

1234 1324

3124 1342

3142 3412

(35)

Sylvester classes?

m-Tamari lattice

211233

221133 311223

223113 321123

223311 322113 331122

322311 332112

332211

(36)

Sylvester classes?

m-Tamari lattice

112233

211233

221133 311223

223113 321123

223311 322113 331122

322311 332112

332211

(37)

m-permutations ^(mn)! ₂

n

m-permtuations lattice 1, 6, 90, 2520, 113400

Decreasing _k=0 (1 + kn) Metasylvester lattice (m + 1)-ary trees

1, 3, 15, 105, 945

m-Catalan objects: _mn+1 ¹ ^(m+1)n _n

m-Tamari lattice (m + 1)-ary trees

m-Dyck paths 1, 3, 12, 55, 273

(38)

m-permutations ^(mn)! ₂

n

m-permtuations lattice 1, 6, 90, 2520, 113400

Decreasing

k=0 (1 + kn) Metasylvester lattice

(m + 1)-ary trees

1, 3, 15, 105, 945

m-Catalan objects: _mn+1 ¹ ^(m+1)n _n

m-Tamari lattice (m + 1)-ary trees

m-Dyck paths 1, 3, 12, 55, 273

(39)

m-permutations ^(mn)! ₂

n

m-permtuations lattice 1, 6, 90, 2520, 113400

Decreasing Q n−1

k=0 (1 + kn) (m + 1)-ary trees

1, 3, 15, 105, 945 m-Catalan objects: _mn+1 ¹ ^(m+1)n _n

m-Tamari lattice (m + 1)-ary trees

m-Dyck paths 1, 3, 12, 55, 273

(40)

m-permutations ^(mn)! ₂

n

m-permtuations lattice 1, 6, 90, 2520, 113400

Decreasing Q n−1

k=0 (1 + kn) Metasylvester lattice (m + 1)-ary trees

1, 3, 15, 105, 945 m-Catalan objects: _mn+1 ¹ ^(m+1)n _n

m-Tamari lattice (m + 1)-ary trees

m-Dyck paths 1, 3, 12, 55, 273

(41)

Metasylvester congruence*

ac . . . a ≡ ca . . . a (a < c ),

b . . . ac . . . b ≡ b . . . ca . . . b (a < b < c ).

Example:

1212 → 2112 321132 → 321312

(m + 1)-ary trees.*

*Novelli, Thibon – 2014

(42)

Metasylvester congruence*

ac . . . a ≡ ca . . . a (a < c ),

b . . . ac . . . b ≡ b . . . ca . . . b (a < b < c ).

Example:

1212 → 2112 321132 → 321312

The metasylvester classes are in bijection with decreasing (m + 1)-ary trees.*

*Novelli, Thibon – 2014

(43)

Proposition (Novelli, Thibon)

Each metasylvester class contains a single element avoiding the pattern a . . . b . . . a with a < b, it is the maximal element of the class in the m-permutation lattice.

Example:

211323 does not avoid the pattern.

322113 avoids the pattern.

(44)

Bijection metasylvester classes – decreasing trees

3382251158744766

(45)

Bijection metasylvester classes – decreasing trees 3382251158744766

3382251158744766

(46)

Bijection metasylvester classes – decreasing trees 8

33 225115 744766

3382251158744766

(47)

Bijection metasylvester classes – decreasing trees 8

3 5

2 1

7 4 6

3382251158744766

(48)

Theorem

The subposet formed by the maximal elements of the metasylvester classes is a lattice.

(49)

112233

211233 113223

221133 311223 113322

223113 321123 311322

223311 322113 331122

322311 332112

332211

3 2 1

3

1 2

3 2

1

3 2 1

3

1 2

3

2 1

3 2 1

3

1 2

3

2 1

3 2 1

3

2 1

3 2 1

3 2

1

(50)

112233

211233 113223

221133 311223 113322

223113 321123 311322

223311 322113 331122

322311 332112

332211

123 123 213

123 132 213

213

123 312

132 132 213

231

123 321

132 312 231

231 213 321

312 312 231

321

312 321 321 321

σ ⁻¹ µ avoids the pattern 231.

(51)

112233

211233 113223

221133 311223 113322

223113 321123 311322

223311 322113 331122

322311 332112

332211

123 123 123 213

123 132 213

213

123 312

132 132 213

231

123 321

132 312 231

231 213 321

312 312 231

321

312 321 321 321

σ µ avoids the pattern 231.

(52)

112233

211233 113223

221133 311223 113322

223113 321123 311322

223311 322113 331122

322311 332112

332211

123 123 123 213

123 132 213

213

123 312

132 132 213

231

123 321

132 312 231

231 213 321

312 312 231

321

312 321 321 321

σ ⁻¹ µ avoids the pattern 231.

(53)

123 123 123 213

123 132 213

213

123 312

132 132 213

231

123 321

132 312 231

231 213 321

312 312 231

321

312 321 321 321