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 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