Lectures related to the Bijective Combinatorics Course BJC3

Lectures related to "The Art of Bijective Combinatorics" Part III

Maule: tilings, Young and Tamari lattices under the same roof

Maths seminar, IMSc, Chennai, 19 February 2018

video Maule I: link to Ekalavya (IMSc Media Center)

abstract

We introduce a new family of posets which I propose to call "maule". Every finite subset of the square lattice generates a maule by a dynamical process of particles moving on the square lattice. Three well-known lattices are maules: Ferrers diagrams Y(λ) contained in a given diagram λ (ideal of the Young lattice), some tilings on the triangular lattice (equivalent to plane partitions) and the very classic Tamari lattice defined with the notion of "rotation" on binary trees. We thus get a new simple definition of the Tamari lattice. Curiously, the concept of alternative tableaux plays a crucial role in this work. Such tableaux were introduced in a totally different context: the very classical model called PASEP ("partially asymmetric exclusion process"), a toy model in the physics of dynamical systems. Here we need only the subclass of Catalan alternative tableaux, corresponding to the TASEP ("totally asymmetric exclusion process").

ps: "maule" is a Mapuche word (pronounce « ma-ou-lé ») which is one of the areas in Chile, together with the name of a river crossing this area where this work was done, thanks to the invitation of Luc Lapointe from Talca university.

details of the slides and time for the video:

Maule 2 0:27

definition of a Gamma move 5 0:50

an example of Gamma moves in a cloud 10-15 3:39

main definition: maule 16 5:16

an example of maule 25 9:10

the Maule area in Chile 30 10:11

The Young lattice 33 11:25

the poset of Ferrers diagrams included in a given Ferrers is a (simple) maule, example 35-48 11:56

simple maule: definition 49 12:58

Tilings lattice 14:42

tiling of an hexagon in the triangular lattice 52 15:20

plane partition 53 16:50

MacMahon formula for plane partition in a box 57 19:40

bijection plane partition and non-crossing paths 59-60 20:25

the poset of plane partitions in a box

(equivalently tilings on an hexagon of the triangular lattice) is a simple maule 62 25:16

The Tamari lattice 63 27:28

binary trees and complete binary trees 64-65 27:37

rotation in binary trees 66 30:25

the Tamari lattice for n=4 68 36:40

the associahedron (for n=4) 69 37:34

intervals in the Tamari lattice and triangulations 70 39:43

Jules and Marius T-shirt 40:21

The Tamari lattice as a maule 72 41:22

example with n=4 73-81 41:35

the (first) main theorem Tamari(n) =Maule (V(n+1)) 83 43:36

Canopy of a binary tree 84 45:13

definition of the canopy 85 45:30

Alternative tableaux 87 49:28

definiiton of an alternative tableau 88-89 49:35

the PASEP in physics 91 51:20

expression of the stationary probabilities with alternative tableaux 93 53:28

Catalan alternative tableaux 94 54:43

definition 95 54:47

Characterisation of alternative Catalan tableaux 96 55:52

(with Catalan permutation tableaux) 98 57:00

permutation tableau 99 58:15

An example 103 1:00:06

construction of the blue cells, knowing the red cells 106-108 1:00:20

Bijection Catalan alternative tableaux --- binary trees 113 1:01:07

construction of the bijection with an example 114-117 1:01:19

bijection Catalan alternative tableaux --- Catalan permutation tableaux 121-124 1:03:06

Second bijection Catalan alternative tableaux --- binary trees 125 1:03:44

the second bijection 126-141 1:03:50

the reverse of the second bijection 144-152 1:06:50

Tamari and alternative tableaux 153 1:07:45

main lemma for a Gamma move in an alternative tableau 154 1:08:03

proof of the equivalence between Gamma move in an alternative tableau and rotation in a binary 156-157 1:11:15

The (second) main theorem 161 1:13:58

statement of the (second) main theorem Int(v) = Maule(X(v)) 1:14:00

an example 166-167 1:15:13

Another example 168 1:15:39

End of the proof of the (first) main theorem Tamari(n) = Maule (V(n+1)) 183 1:17:19

Bijection Catalan alternative tableaux --- Catalan staircase alternative tableaux 194 1:18:23

commutative diagram: binary trees, complete binary trees,

Catalan alternative tableaux, Catalan staircase alternative tableaux 206 1:19:36

behaviour of the canopy under rotation in binary

( equivalently Gamma move in a Catalan staircase alternative tableau) 207-209 1:19:47

Comments and remarks 210 1:20:49

some papers with Gamma and Le moves (Lam, Williams, ...) 211 1:20:52

Rubey chute moves and pipe dreams 212-214 1:21:52

maximal chains of maximal length in the Tamari lattice (Fishel, Nelslon) 218 1:23:43

bijection with standard shifted tableaux of staircase shape 219-226 1:24:24

The end 227 1:26:04

Maule: Tamari(v) is a maule

Maths seminar, IMSc, Chennai, 26 February 2018

slides Maule II (v2, pdf, 52 Mo)

video Maule II: link to Ekalavya (IMSc Media Center)

video Maule II: link to YouTube

abstract

This lecture follows the Maths seminar 19 February 2018 at IMSc.

By translating the rotation of binary trees in the context of Dyck paths, the classical Tamari lattice has been extended by F.Bergeron to m-Tamari (m integer), and then to any m rational by L.-F. Préville-Ratelle and the speaker. More generally, we defined a Tamari lattice for any path v with elementary steps East end North. We prove that this lattice Tamari(v) is also a maule, which gives a new and more simple definition of this lattice. Again, alternative tableaux (in the case of Catalan) and its avatars (permutation tableaux, tree-like tableaux and staircase tableaux) play a crucial role. These tableaux allow to relate this work with the recent work of C.Ceballos, A. Padrol et C. Sarmiento giving a geometric realization of Tamari(v), analogue to the classical associahedron for the classical Tamari lattice. With this concept of maule, we can also define a new lattice YTam(λ,v), ""mixing" the Young lattice Y(λ) and the Tamari lattice Tamari(v).

remark

these two seminars talks are an extended version of the talk I gave at the 79th SLC

(Séminaire Lotharingien de Combinatoire), Bertinoro, Italy, 11 September 2017

The two set of slides presented here are a slighty augmented version of the one presented on the website of the 79th SLC .

details of the slides and time for the video:

Maule 3 0:36

definition of a Gamma move 4-5 0:54

an example of Gamma moves in a cloud 7-11 1:51

main definition: maule 12 2:37

the Maule area in Chile 13 (added after the video)

complete maule (oral definition) 14 3:05

The Tamari lattice 14

binary trees and complete binary trees 15-16 4:15

rotation in binary trees 17 6:05

example: the Tamari lattice for n=4 7:01

Tamari lattice as a maule 19 7:48

example for n=4 21-28 8:10

Geometric realization of the Tamari lattice 31 9:42

Jean-Louis Loday and the associahedron 33 10:41

The Tamari lattice in terms of Dyck paths 34 11:33

from binary trees to Dyck paths 38 video with violonists 12:41

the analog of the rotation of binary trees with Dyck paths 40-41 13:41

Dyck paths and ballot paths 43 15:05

Tamari covering relationin term of ballot paths 44 15:41

Relation with diagonal coinvariant spaces, the m-Tamari lattice 45 16:32

Adriano Garsia and François Bergeron 46 16:45

the covering relation for the m-Tamari lattice 50 20:44

Rational Catalan combinatorics 52 22:05

The covering relation for the poset Tamari(v) (=T_v) 57-58 25:42

Theorem 1 T_v is a lattice 59 28:45

Theorem 2 dual of T_v 63 30:36

Thereom 3 T_n as union of intervals isomorphic to the T_v, length of v =n 65 31:48

BIjection binary trees --- pairs of paths (u,v) 67 34:32

The reverse bijection pairs of paths (u,v) --- binary trees 74 43:12

description of the "push-gliding" algorithm 75-83

Idea of the proof of theorems 1,2,3 86 46:07

combinatorics of binary trees: B binary tree --- w(B) a word in four letters 89 47:12

hypercube, associahedron, permutohedron 92 48:37

intervals of Tamari(v) and non-sepable rooted maps 93 50:28

Tamari(v) lattice as a maule 94 52:30

alternative tableaux: definition 95-96 52:49

Catalan alternative tableaux: definition 97 54:27

Bijection Catalan alternative tableaux --- pairs of paths (u,v) 98 54:52

the Adela row vector 100 55:10

Reverse bijection pairs of paths (u,v) --- Catalan alternative tableaux 103 57:06

a commutative diagram (binary trees -- Catalan alternative tableaux -- pairs of paths) 107 57:54

the duality Adela row vector and Adela column vector 110

The Tamari lattice Tamari(v) is a maule 115

main Lemma: Gamma move in a Catalan alternative tableau 116-119

equivalence between a flip defining the covering relation of Tamari(v) and a Γ-move 122-124

main theorem: Tamari(v) = Maule (X(v))

example: Tamari (3,5) as a maule

A mixture of Young lattice Y(u) and Tamari lattice T(v) 129

an example 131-143

A festival of bijections 145

the bijection Dyck paths --- staircase polygons --- pairs of paths (u,v) 148-153

another commutative diagram:

binary trees --- Dyck paths --- staircase polygons --- pairs of paths (u,v) --- Catalan alternative tableaux 153-154 1:10:54

The work of Ceballos, Padrol and Sarmiento 157 1:11:45

A triangulation of a regular polygon 158 1:11:58

Euler introduced triangulations and Catalan numbers in a letter to Goldbach, 4 September 1751 160-162 1:12:11

From triangulations to binary trees 164-168 video with violonists 1:13:10

the association Cont'Science (G.Duchamp, M.Pig Lagos, X. Viennot) 169 1:14:36

Tamari lattice with triangulations 170 1:15:03

a flip in a triangulation 172-173 1:15:24

bijections triangulations (of an n-gon) --- (I,J bar)-trees --- pair of paths (u,v) 176 1:16:02

v-trees (= underlying tree of a Catalan tree-like tableau) and geometry of Tamari(v) 178 1:17:32

v-trees, Tamari(v) and subwords complex 179 1:18:21

A festival of commutative diagrams (!) 180-182 1:19:20

Nadeau bijection: Catalan alternative tableaux --- non-crossing alternative arc-diagrams (= (I,J bar)-trees)

Comments, remarks and references 183 1:20:17

n! alternative tableaux and its avatar 188 1:20:48

more references 190-193

permutations tableaux, alternative tableaux, tree-like tableaux 194-196 1:21:07

The Adela bijectionn and demultiplication of equations in the PASEP algebra 200 1:21:24

the bijection Adela(T) = (P,Q) (for T alternative tableau) 204 1:22:20

Adeal duality P --- Q in the Catalan case 206-207 1:23:06

The end (with Tamari trees in flower) 213 1:24:36

Growth diagrams, local rules and beyond

21st Ramanujan Symposium: National Conference on algebra and its applications,

Ramanujan Institute, University of Madras, Chennai, India, 28 February 2018

slides part I (pdf, 17 Mo)

slides part II (pdf, 15 Mo)

abstract

Robinson-Schensted-Knuth correspondence (RSK), Schützenberger "jeu de taquin", Littlewood-Richarson coefficients are very classical objects in the combinatorics of Young tableaux, Schur functions and representation theory. Description has been given by Fomin in terms of "growth diagrams" and operators satisfying the commutation rules of the Weyl-Heisenberg algebra. After a survey of Fomin's approach, I will make a slight shift by introducing an equivalent description with "local rules on edges", and show how such point of view can be extended to some other quadratic algebras.

Growth diagrams and edge local rules

GASCom 2018, Athens, Greece, 18 June 2018

slides

slides preliminary version: (pdf, 33Mo) GT LaBRI, Bordeaux, June 1st 2018

paper (extended abstract, 10p. in Proceedings GASCom 2018)

abstract

Fomin growth diagrams for the Robinson-Schensted correspondence and for the jeu de taquin are some rules allowing the construction of the 4th Ferrers diagram once 3 Ferrers diagrams around an elementary cell are known.We propose here to replace these rules by some local rules on edges instead of local rules on vertices.

Keywords

Fomin growth diagrams, edge local rules, Schützenberger jeu de taquin, RSK product of two words, duality of Young tableaux.