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 4 Trees and Tableaux
Ch 4a Trees and Tableaux: binary trees and Catalan alternative tableaux
March 1, 2018
slides of Ch 4a (pdf, 28 Mo)
video Ch4a: link to Ekalavya (IMSc Media Center)
video Ch4a: link to YouTube
TASEP and Catalan alternative tableaux 3 0:38
Catalan alternative tableaux 9 2:37
definition 10 2:42
Characterisation of Catalan alternative tableaux
Catalan permutation tableaux: definition 14 5:28
(another) example 16 7:48
construction of the blue cells (from the red cells) 20-22 8:05
Binary trees and complete binary trees 28 9:54
definition of a binary tree 29 10:44
classical enumerative combinatorics: recurrence relation for Catalan numbers 32 13:10
modern enumerative combinatorics: operations on combinatorial objects and algebraic equation 33-34 13:49
exercise: "complete" bijective proof for the Catalan numbers 38 15:34
bijection binary trees -- complete binary trees 42 17:48
height, left height, right height in a binary tree 47 19:20
left and right principal branch in a binary tree 48 19:57
preorder traversal of a binary tree 49 20:54
inorder (symmetric order) traversal of a binary tree 52 21:51
Bijection binary tree -- pair of paths (u,v) 55 23:56
Reverse bijection pair of paths (u,v) -- binary tree 61 34:12
the "push-gliding" algorithm 62-71 34:21
Bijection Catalan alternative tableaux -- binary trees 72 41:58
Second bijection Catalan alternative tableaux -- binary trees 78 46:21
reverse bijection 96 50:45
TASEP, Catalan alternative tableaux and binary trees 108 53:15
expression of the 2 parameters TASEP stationary probability with binary trees and canopy 111 55:01
bijective proof for the partition function 112-114 56:44
Bijection Catalan alternative tableaux -- pairs of paths (u,v) 116 1:04:45
reverse bijection 120 1:07:56
commutative diagram: Catalan alternative tableaux - binary trees - pair of paths (u,v) 128-129 1:10:19
The Adela bijection: demultiplication (of equations) in the PASEP algebra 130 1:15:15
Adela bijection (for alternative tableaux) 134 1:17:38
the Catalan case: Adela duality 135-136 1:21:04
TASEP, Catalan tableaux and pair of paths (u,v) 137 1:22:52
relation with the Shapiro-Zeilberger interpretation 139 1:23:31
2-parameters stationary probabilites as a determinant (Olya Mandelshtam) 141 1:25:05
LGV proof with dual configuration of paths for Narayan-Kreweras determinant 144 1:27:11
The end 145 1:28:14
Ch 4b Trees and tableaux: the Loday-Ronco algebra of binary trees
April 16, 2018
slides of Ch 4b (pdf, 23 Mo)
video Ch4b: link to Ekalavya (IMSc Media Center)
video Ch4b: link to YouTube
graded Hopf algebra 4 0:44
reminding: increasing binary trees, canopy and up-down sequence 5 2:15
two Hopf algebras: Malvenuto-Reutenauer (permutations) and Loday-Ronco (binary trees) 18 14:56
definition of the map psi* 20 15:57
definitions: standartisation of a word and Malvenuto-Reutenauer product 21 17:32
definition of the Loday-Ronco product 22 25:08
Loday-Ronco product with an example 23 27:22
"Jeu de taquin" for increasing woods and increasing binary trees 24 32:36
increasing woods: definition 25 33:02
slidings in an increasing woods 27 36:32
jeu de taquin for an increasing woods 28 39:26
invriance of the symmetric order for an increasing wood 29 40:39
example: from a permutation to its "déployée" 30-42 43:05
Catalan alternative tableaux (reminding of Ch4a) 45 47:03
definitions: alternative tableaux and Catalan alternative tableaux (reminding Ch4a) 46-47 47:10
characterisation of Catalan alternative tableaux with Catalan permutation tableaux 48 49:42
definitions: permutation tableaux and Catalan permutation tableaux 49 50:51
Catalan alternative tableaux of rectangular shape 54 52:44
BIjection Catalan alternative tableaux -- binary trees (reminding Ch4a, 78-107) 57 54:17
(with jeu de taquin on unlabelled woods) 58-70
profile and canopy in this bijection 71 38:15
free columns, free rows and principal branches of the corresponding binary tree 72-73 59:19
Catalan alternative tableaux underlying the "Jeu de taquin" for increasing woods 74 1:01:03
Construction of the Loday-Ronco product from the Malvenuto-product of permutations 95 1:04:06
Expression of the Loday-Ronco product with rectangular Catalan alternative tableaux 104 1:08:23
Analog of the Loday-Ronco product for Catalan alternative tableaux 114 1:12:52
The "sharp" product 126 1:17:49
definition: sharp product of two binary trees 131 1:19:00
Loday-Ronco product and the sharp product 133 1:20:46
the sharp product of two Catalan alternative tableaux 135 1:21:48
the Loday-Ronco product in term of Catalan tableaux 141 1:24:03
the end 145 1:27:28
Ch 4c Trees and tableaux: alternative binary trees, non-ambiguous trees and beyond
April 19, 2018
slides of Ch 4c (pdf, 32 Mo)
video Ch4c: link to Ekalavya (IMSc Media Center)
video Ch4c: link to YouTube
From Ch4b:" jeu de taquin" for an increasing wood and Catalan alternative tableau 3 0:44
Alternative binary trees 9 02:30
definition: edge-alternative binary tree 10 02:52
definition: edge alternative wood 11 03:58
definition: alternative binary tree 12 05:31
bijection alternative binary tree and permutation 14 06:46
"Jeu de taquin" for alternative binary trees and woods 17 11:42
definition of the 3 possible slidings 19 12:34
the bijection alternative tableaux -- alternative trees (with jeu de taquin) 20-37 14:39
Reminding the "exchange-fusion" algorithm 38 19:35
Reminding the bijection alternative tableaux -- permutations (inverse exchange-fusion) 45 20:50
Comparison of the "jeu de taquin" bijection with the "exchange-fusion" bijection 61 24:30
the twisted symmetric order 63 24:50
Genocchi sequence of a permutation (reminding) 67 30:30
Comparison of the underlying binary trees (alternative tableaux and alternative binary trees) 69 32:38
Second version of the bijection alternative tableaux -- alternative binary trees 74 33:46
Tree-like tableaux 79 36:02
definition: tree-like tableaux (reminding) 83 36:45
Catalan tree-like tableaux: two bijections with binary trees (reminding) 86 39:30
Non-ambiguous trees 91 40:32
intervals of permutations having the same underlying non-ambiguous tree 98-104 42:33
hook formula for non-ambiguous trees 106 44:38
formula for the number of non-ambiguous trees (with Stirling numbers) 108 50:08
Complete non-ambiguous trees, Bessel functions and heaps of "sticks" 109 50:54
Emma Jin's bijection between complete non-ambiguous trees and some heaps of "sticks" 111-116 54:09
q-Polya numbers for parallelogram polyominoes, q-Bessel and heaps of segments 119-120 1:03:19
Bijection parallelogram polyominoes -- binary trees via non-ambiguous trees 121 1:05:00
Tree-like tableaux are Q-tableaux or the reverse PASEP quadratic algebra 127 1:07:12
In conclusion: the philosophy of the cellular ansatz 141 1:10:38
reminding the trilogy for RSK: growth diagrams and representation of the quadratic algebra UD=DU+Id,
edge local rules and demultiplication of equations 142-151 1:10:50
reminding commutations diagrams from a representaion of the PASEP algebra 153 1:14:48
duplication of equations in the PASEP algebra: the Adela bijection 158-160 1:16:02
duplicaion of equations in the reverse PASEP algebra (with 4 generators) 165-168 1:18:38
equivalence with the commutations diagrams 169-173 1:18:59
A new bijection: duplication of equations in the reverse PASEP quadratic algebra 174 1:19:40
The proposed duplication of equations with only two operators 176 1:20:18
The "Tamil bijection" between alternative tableaux and some words 178 1:21:24
interpretation of the Tamil bijection with the underlying binary tree 181 1:23:38
the case of Catalan tableaux 185 1:24:58
example with parallelogram polyominoes 186 1:25:38
example: coding of a binary tree with the Tamil bijection 192 1:26:59
Many thanks 193 1:29:12
The godess Saraswathi 194 1:30:27