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
The PAEP 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 (1st part) (pdf, 23 Mo)
slides of Ch 3b (2nd part) (pdf, 17 Mo)
video Ch3b: link to Ekalavya (IMSc Media Center)
video Ch3b: link to YouTube
slides first part
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
End of the first part of slides 117 1:16:30
slides second part
A variation of the "exchange-fusion" algorithm: the "exchange-delete" algorithm 3 1:16:32
The inverse "exchange-delete" algorithm 24 1:19:06
Commutations diagrams 43 1:21:25
(local rules for the operators A, S, J, K)
Commutations diagrams bijections 49 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) 51 1:26:51
The reverse bijection alternative tableaux --- Laguerre histories (permutations)
with local rules (commutation diagrams) 68 1:29:33
Two bijections, one theorem 83 1:32:12
The "exchange-delete" algorithm with the inverse permutations
(with a variant: keep the min instead of the max) 85 1:32:51
Proof of the main theorem: equivalence local rules (commutation diagrams) on Laguerre histoires
and exchange-fusion (or exchange-delete) algorithm 98 1:34:17
End of the second part of slides 109 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 (1st part) (pdf, 21 Mo)
slides of Ch 3c (2nd part) (pdf, 21 Mo)
video Ch3c: link to Ekalavya (IMSc Media Center)
video Ch3c: link to YouTube
slides first part
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
slides second part
complements: Postnikov bijection, pipe dreams and Ammag-diagrams 2 42:08
from an Ammag-diagram to a permutation via pipe dreams 4-5 43:04
Grassmanian permutation 8 45:19
complements: reminding Ch6a, BJC2, heaps of dimers and symmetric group 10 46:44
complements: bijection decorated permutations --- Ammag diagrams
bijection permutation tableaux --- permutations 17 49:58
Excedances and Genocchi sequence of a permutation 26 55:19
The direct bijection subexcedant functions --- tree-like tableaux 31 58:28
row /colum insertion in a Ferrers diagram 33 58:56
special point of a tree-like tableau 41 1:00:33
insertion algorithm in a tree-like tableau 46 1:02:15
Parameters 67 1:06:31
number of elements in the first row and first column (of a tree-like tableau) 70-71 1:07:58
the parameter "q" (number of crossings in the tableau) 72 1:08:41
expression of the parameter "q" in terms of the corresponding subexcedant function 80 1:09:48
q-Laguerre histories 82 1:10:59
definition of the q-weight of a Laguerre history 84 1:11:18
the parameter "q" in terms of patterns 31-2 86 1:12:40
interpretation of the parameters "q" in the exchange-fusion algorithm 89 1:15:12
Bernardi permutations avoiding patterns 31-24 and 24-31 are enumerated by Catalan numbers 91 1:17:53
end of the second part of slides 94 1:20:55