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

Alternative tableaux, permutations and partially asymetric exclusion process
Isaac Newtion Institute for Mathematical Sciences, 23 April 2008
workshop "Statistical Mechanics and Quantum Field Theory Methods in Combinatorial Enumeration"
slides  (pdf  10 Mo)      complementary slides  (2,5 Mo)  
video  (1h 10mn)
This video together with the set of slides is a kind of "video-preprint" where the notion of alternative tableaux is introduced for the first time
abstract:
     We introduce a new combinatorial object called "alternative tableau". This notion is at the heart of different topics: the combinatorics of permutations and of orthogonal polynomials, and in physics the model PASEP (partially asymmetric exclusion process).
     The model PASEP have been recently intensively studied by combinatorists, in particular giving combinatorial interpretations of the stationary distribution (works of Brak, Corteel, Essam, Parvianinen, Rechnitzer, Williams, Duchi, Schaeffer, Viennot, ...). Some interpretations are in term of the so-called "permutation tableaux", introduced by Postnikov, followed by Steingrimsson and Williams, in relation with some considerations in algebraic geometry (total positivity on the Grassmannian).
     Permutations tableaux have been studied by Postnikov, Steingrimsson, Williams, Burstein, Corteel, Nadeau and various bijections with permutations have been given. The advantage of introducing alternative tableaux is to give a complete symmetric role for rows and columns. We give a bijection between the two kinds of tableaux and a direct bijection between permutations and alternative tableaux. We also give combinatorial interpretation of the stationary distribution of the PASEP in term of alternative tableaux.
     Then we show the relation between alternative tableaux and the combinatorial theory of orthogonal polynomials developed by Flajolet and the author. In particular the Françon-Viennot bijection between permutations and "Laguerre histories" (i.e. some weighted Motzkin paths) plays a central role here and enable us to construct another bijection between permutations and alternative tableaux.
     This last bijection is in the same vein as the construction of the classical Robinson-Schensted-Knuth correspondence by "local rules" as originally defined by Fomin. The bijection can also be presented in analogy with Schützenberger "jeu de taquin". We finish the talk by giving "la cerise sur le gâteau": the surprising connection between the two bijections relating permutations and alternative tableaux. 
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
video Maule I: link to bilibil 
remark
This seminar talk, and the following "Maule:  Tamari(v) is a maule",Maths seminar, IMSc, Chennai, 26 February 2018, are extended version of the talk I gave at the 79th SLC

(Séminaire Lotharingien de Combinatoire), Bertinoro, Italy, 11 September 2017.  Abstract with some pictures here .

The two set of slides presented here are a slighty augmented version of the one presented on the website of the 79th SLC . 
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
video Maule II: link to bilibili  
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).
note added:
In May  2018, C. Ceballos, A. Padrol and  C. Sarmiento published the paper arXiv: 1805:03566 [Math.CO]
"The ν-Tamari lattice as the rotation lattice of ν-trees"
Some results of their paper intersect some results given here in these two Maule lectures and at the 79th SLC, in particular the fact that the v-Tamari lattice defined by L.-F. Préville-Ratelle and the speaker (in terms of a flip in a pair of paths) corresponds to a rotation in the associated v-tree (theorem 3.2, which is in fact the title of the paper).
This equivalence is proved by using the associated Catalan alternative tableau and v-Tamari lattice defined with Γ-moves:
p155 (first lecture on maules) A rotation in the binary tree (the v-tree) corresponds exactly to a certain Γ-move in the associated Catalan alternative tableau,
p123-124 (second lecture on maules) Equivalence between a flip defining the covering relation of Tamari(v) and a Γ-move. 

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 (the talk given at Athens) 
slides preliminary version: (long 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.