The Art of Bijective Combinatorics    Part III
The cellular ansatz:  bijective combinatorics and quadratic algebra

The Institute of Mathematical Sciences, Chennai, India  (January-March 2018)

Chapter 3   Tableaux for the PASEP quadratic algebra
Ch 3a     The 5-parameters PASEP model, the matrix ansatz, PASEP and alternative tableaux
Catalan alternative tableaux, representation with 4 operators

February 12, 2018
slides of Ch 3a   (pdf,  19 Mo)                 
video Ch3a: link to Ekalavya  (IMSc Media Center)
video Ch3a: link to YouTube
video Ch3a: link to bilibili
The PASEP   3   2:30
definition of the PASEP model with 5 parameters   4   1:42
reminding about Markov chains   6   9:05
definition of stationnary probabilities   8   11:21
TASEP with two parameters   10   13:22
example of stationnary probabilities (TASEP, alpha=beta=1, n=3)   11  13:41
phase transitions for the TASEP   13   17:19
Combinatorics and PASEP   15   22:09
Shapiro-Zeilberger combinatorial interpretation of the the stationnary probabilities
for the TASEP with pair of paths (alpha=beta=1)   17   24:30
Orthogonal polynomials and PASEP   21   30:59
The Askey tableau of classical orthogonal polynomials   23   32:30
The matrix ansatz   24   34:16
the matrix ansatz (Derrida, Evans, Hakim, Pasquier)   25-26   34:32
some examples (solution of the matrix ansatz with 2 parameters alpha and beta, q=0)   29-31   42:51
The PASEP algebra   32   45:33
Alternative tableaux   36   47:52
 definition of alternative tableaux   37-38   47:57
from alternative tableaux to complete alternative tableaux   39-42   49:07
3 parameters for alternative tableaux   43   50:16 
"normal ordering" in the PASEP algebra   45   51:51
Stationary probabilities for the PASEP   46   54:34
Enumeration of alternative tableaux   51   1:03:54
Catalan alternative tableau   54   1:06:57
discussion about bijections permutations -- alternating tableaux   55   1:07:51
A combinatorial representation of the PASEP algebra   57   1:11:42
Polya urns   58   1:11:54
priority queues   61   1:13:55
weighted Dyck path for Polya urns and priority queues   62-64   1:16:21
comparison with annihilation and creation operators in qauntum mechanics   65   1:19:09
dictionnary data structures and its four operators A, S, J, K   69   1:23:09
representation of the PASEP algebra with   A, S, J, K   70   1:24:31
an example of local rules derived from this representation   72   1:30:49
The end   73   1:32:14 

Ch 3b     Laguerre histories, the exchange-fusion algorithm, commutations diagrams
from the representation of the PASEP algebra, equivalence commutations diagrams and exchange-delete algorithm

February 15, 2018
slides of Ch 3b   (pdf,   35 Mo)         
video Ch3b: link to Ekalavya  (IMSc Media Center)
video Ch3b: link to YouTube
video Ch3b: link to bilibili
From Ch3a   3   0:23
Four operators A, S, J, K defined on the Fock space (basis  I k > )   11   2:58
Combinatorial representation of the PASEP quadratic algebra   14   9:02
four operators A, S, J, K defined on the vector space generated by alternating words  16  11:24
Laguerre histories: definition   23   26:31
The bijection Laguerre histories --- permutations   described with words (FV bijection)   31   34:52
Reciprocal bijection  permutations --- Laguerre histories   42   38:03
peak, through (valley), double rise, double descent of a permutation   43   38:09
x-decomposition of a permutation   45   40:40
the pattern 31-2 in a permutation   49   44:02
Laguerre histories and orthogonal polynomials   50   46:01
The FV bijection described with operators   53   47:24
Direct proof for the number of alternating tableaux of size n = (n+1)!   57   49:49
Analogy with the direct proof using operators U, D representing the Weyl-algebra (see Ch2)   63   53:51
The "exchange-fusion" algorithm   65   54:33
The inverse "exchange-fusion" algorithm   89   1:03:58
 A variation of the "exchange-fusion" algorithm: the "exchange-delete" algorithm   117   1:16:32
The inverse "exchange-delete" algorithm   138   1:19:06
Commutations diagrams   157   1:21:25
(local rules for the operators A, S, J, K)
Commutations diagrams bijections   163   1:25:17
analogy with the commutation diagrams bijection for the representation of the Weyl-Heisenberg algebra (Ch 2)
The bijection Laguerre histories (permutations) --- alternative tableaux
with local rules (commutation diagrams)   165   1:26:51
The reverse bijection alternative tableaux --- Laguerre histories (permutations)
with local rules (commutation diagrams)   182   1:29:33
Two bijections, one theorem   197   1:32:12
The "exchange-delete" algorithm with the inverse permutations
(with a variant: keep the min instead of the max)   199   1:32:51
Proof of the main theorem: equivalence local rules (commutation diagrams) on Laguerre histoires
and exchange-fusion (or exchange-delete) algorithm   212   1:34:17
End of the second part of slides   123   1:39:26

Ch 3c     interpretation of the parameters of the 3-PASEP, Genocchi sequence of a permutation, permutation tableau
bijection inversion tables - tree-like tableaux with the insertion algorithm

February 22, 2018
slides of Ch 3c   (pdf,   38 Mo)            
video Ch3c: link to Ekalavya  (IMSc Media Center)
video Ch3c: link to YouTube
video Ch3c: link to bilibili
Reminding Ch3b   3   0:23
the "exchange-fusion" algorithm   4   0:33
the "exchange-delete" algorithm   24   1:38
the bijection Laguerre histories --- permutations (with operators)  39   2:15
equivalence "local rules" and "exchange-delete" algorithme   41   3:02
Genocchi sequence of a permutation   53   5:58
definition of the Genocchi sequence   56   8:33
relation between the shape of the alternative tableau in the "exchange-fusion" algorithm
and the Genocchi sequence of the inverse permutation   57   11:12
Dumont theorem: permutations with an alternating Genocchi sequence   60   14:14
historical notes: Euler and Genocchi numbers   62   16:29
Knuth and Genocchi numbers 64   18:15
Some parameters   65   18:54
left-to-right minimum elements   66-67   19:14
subexcedant function: definition   68   20:36
the double distribution left-to-right and right-to-left minimum elements of a permutation   69   21:08
the double distribution number of empty rows and colums in an alternative tableau   74   27:40
permutation tableaux   77   29:42
permutation tableaux: definition   79-81   30:00
bijection permutation tableaux -- alternative tableaux   84   32:02
from an alternative tableau to a permutation tableau   86-91   32:44
from a permutation tableau to an alternative tableau   91   35:13
discussion: permutation tableau, Q-tableau and reverse Q-tableau for the PASEP algebra   99   36:19
end of the first part of slides   112   42:07
complements: Postnikov bijection, pipe dreams and Ammag-diagrams   112   42:08
from an Ammag-diagram to a permutation via pipe dreams   114-115   43:04
Grassmanian permutation   118   45:19
complements: reminding Ch6a, BJC2, heaps of dimers and symmetric group   120   46:44
complements: bijection decorated permutations --- Ammag diagrams
bijection permutation tableaux --- permutations   127   49:58
Excedances and Genocchi sequence of a permutation   136   55:19
The direct bijection subexcedant functions --- tree-like tableaux   141   58:28
row /colum insertion in a Ferrers diagram   143   58:56
special point of a tree-like tableau   151   1:00:33
insertion algorithm in a tree-like tableau   1R6   1:02:15
Parameters   177   1:06:31
number of elements in the first row and first column (of a tree-like tableau)   180-181   1:07:58
the parameter "q" (number of crossings in the tableau)   182   1:08:41
expression of the parameter "q"  in terms of the corresponding subexcedant function   190   1:09:48
q-Laguerre histories   192   1:10:59
definition of the q-weight of a Laguerre history   194   1:11:18
the parameter "q" in terms of patterns  31-2   196   1:12:40
interpretation of the parameters "q"  in the exchange-fusion algorithm  199   1:15:12
Bernardi permutations avoiding patterns  31-24 and 24-31 are enumerated by Catalan numbers   201   1:17:53
end of the second part of slides   204   1:20:55