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

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