XAVIER VIENNOT
  • PART I
    • abstract
    • contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • list of bijections
    • index
  • PART II
    • abstract
    • contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Some lectures related to the course
  • PART III
    • abstract
    • contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • references, comments and historical notes
  • PART IV
    • introduction
    • contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • references
  • Epilogue

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

slides Maule I (pdf,   44 Mo)  

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

video Maule I: link to YouTube

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.