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 2   Quadratic algebra, Q-tableaux and planar automata

 

Ch 2a     The philosophy of the cellular ansatz: Q-tableaux and complete Q-tableaux

the PASEP algebra, alternative tableaux, a quadratic algebra for ASM

January 29, 2018

 

slides of Ch 2a   (pdf,  22 Mo)                 

video Ch2a: link to Ekalavya  (IMSc Media Center)

video Ch2a: link to YouTube

 

Recalling the philosophy of the cellular ansatz with the example of Q defined by UD=DU+Id   p4-6   2:01

The PASEP algebra definded by DE=ED+E+D  7   3:31

Tableaux for the PASEP algebra  14   12:04

Alternative tableaux  32   18:41

alternative tableau: definition  34   20:16

expression of the stationary probabilities of the PASEP model with alternative tableaux  40   26:47   

Catalan alternative tableaux: definition  43   32:37

Quadratic algebra for ASM (alternating sign matrices)  45   36:38   

alternating sign matrices:definition  46   36:58

formula for the number of ASM  51   40:33

the ASM quadratic algebra  52  43:18

Complete Q-tableaux   85   53:22

the class of general quadratic algebra for the cellular ansatz  86   53:36

analog of normal ordering for the class of general quadratic algebra  87-88   54:54

complete Q-tableau associated to a quadratic algebra: definition  89-90   56:44   

weight of a complete Q-tableau: definition  91   59:43

upper word border (uwb) and lower word border (lwb) of a complete Q-tableau  91   59:43

the general "normal ordering" theorem in term of complete Q-tableaux  92   1:03:22  

Proof of the general "normal ordering" theorem  93   1:04:31

tree associated to a "normal ordering" calculus  98-99   1:06:43

bijection leaves of this tree and complete Q-tableaux  103   1:10:20

Q-tableaux  105   1:12:09

condition (*) for the labels  L  given to the set  R  of rewriting rules  106-107   1:12:25  

Q-tableau: definition  108   1:13:48

Q-tableaux: example 1 with Q defined by  UD=DU+I   110   1:15:26   

permutations as complete Q-tableaux  113   1:16:02

permutations and Rothe diagrams as Q-tableaux  115   1:16:08

rooks placements as Q-tableaux  118   1:16:26

Q-tableaux: example 2 with the PASEP algebra  DE=qED+E+D  122   1:17:12   

Q-tableaux: example 3 with the ASM quadratic algebra  126   1:17:57

exercise: ASM with only 2 " labels"   133   1:18:55   

Exercise  137   1:20:00

surjective pistol and Genocchi numbers  138   1:20:05

directed animals  139   1:22:35

Le-diagrams  142   1:24:41

permutation tableaux  144   1:27:11  

The end  145   1:29:06

  

Ch 2b     Planar automata, The RSK planar automaton, reverse Q-tableaux and reverse quadratic algebra,

tree-like tableaux, duplication of equations and RSK

February 1, 2018

 

slides of Ch 2b   (pdf,  27 Mo)                 

video Ch2b: link to Ekalavya  (IMSc Media Center)

video Ch2b: link to YouTube

 

Reminding Ch 2a   p4   1:05

Planar automaton   12  5:10 

definition  13  (also see Ch1b, p93)   6:03   

equivalence planar automata and Q-tableaux   16   11:08

Planar automata: example   17  14:23 

surjective pistol: definition   18   14:29   

Genochi, Bernoulli and tangent numbers   19   16:57   

Leonhard Euler and Genocchi numbers   20   18:53

quadratic algebra for surjective pistol  (solution of the exercise)  22   23:26   

alternative tableaux with alternating shape   24   26:49

dircted animals (exercise)   25   29:33

Le-diagrams (exercise)   28   30:12

The RSK planar automaton   30   30:50

the RSK reverse planar automaton   34   33:06   

planar automaton for jeu de taquin   37   36:14

Bijections for "tableaux" accepted by planar automata  43   37:44

Summary for Q-tableaux and planar automata   48   41:14

Reverse (dual) Q-tableaux   51   42:42   

reverse Q-tableaux: definition   52   43:14

Reverse Q-tableaux for the PASEP algebra   54   47:58

bijection alternative tableau - tree-like tableau   58-62   49:00

tree-like tableau: definition   63   52:02

binary tree underlying a tree-like tableau   66-68   55:45

binary tree underlying an alternative tableau   70-73   1:00:01

Reverse Q-tableaux for the Weyl-Heisenberg algebra   74   1:00:06

Reverse quadratic algebra   81   1:02:27   

reverse quadratic algebra:definition   82   1:02:33

reverse PASEP algebra   83   1:03:00

reverse Weyl-Heisenberg algebra   87   1:05:16

Reverse quadratic algebra and reverse planar automata   91   1:09:56

Duplications of equations in quadratic algebras   97   1:11:19

duplications for the Weyl-Heisenberg algebra   98-100   1:11:44

comparaison between the duplications process and the representation methodology   103-105   1:17:25

Another demultiplication of the algebra  UD=DU+Id   109   1:20:02

comparaison between the duplications process and the representation methodology:

two inversions tables   116   1:22:10

The end   118   1:26:18

 

Ch 2c     Duplication of equations in the PASEP algebra, the XYZ algebra

XYZ tableaux: rhombus tilings, Aztec tilings, ASM, 6 and 8-vertex model

February 5, 2018

 

slides of Ch 2c   (pdf,  22 Mo)                 

video Ch2c: link to Ekalavya  (IMSc Media Center)

video Ch2c: link to YouTube

 

From Ch 2b: duplication of equations in quadratic algebras   3   0:22

Demultiplication in the PASEP algebra   9   2:33

The Adela bijection between alternative tableaux and pairs (P,Q)   13   8:42

A research problem with the Adela bijection   14   12:36

Adela duality with Catalan alternative tableaux   15   13:50

Isla Negra in Chile   16-17   19:22

The 8-vertex algebra (or XYZ-algebra)   18   20:34

XYZ-tableaux and B.A.BA  configurations   21   26:23

bijections complete XYZ-tableaux and B.A.BA  configurations   26   30:20

Alternating sign matrices  35   38:23

B.A.BA  configurations for alternating sign magtrices  41-42   40:07

characterisation of such configurations   (solution of an exercise)  43   40:20

Correlations functions in XXZ spin chains   44   42:29

a paper by Kitanine, Maillet, Slavnov, Terras   45   42:50

a research problem 46-47   43:13

Rhombus tilings  49   47:03

rewriting rules for tilings of the triangular lattice   54-55   50:36

the quadratic algebra related to tilings of the triangular lattice  56-57   52:50

tilings and plane partitions   61   55:13

MacMahon formula written as the coefficient c(u, v; w)  for a quadratic algebra  66   58:21

Dimers tilings on the square lattice   67   59:16

rewriting rules for tilings on the square lattice   70   1:00:24

the quadratic algebra related to tilings on the square lattice   71   1:01:20  

(corrections after the class: slide 71 of the video is incorrect)

Aztec tilings   72   1:05:40

rewriting rules for Aztec tilings   75   1:08:32

the Aztec tilings quadratic algebra  76   1:10:04

relation with alternating sign matrices  76

a random Aztec tiling   78   1:17:24

complement: the "arctic circle" theorem  79   1:18:19

Geometric interpretation of XYZ-tableaux, 6-  and 8- vertex model   80   1:19:49

the 8-vertex model   81   1:20:10

the 6-vertex model  82   1:22:17

ice model   84   1:23:28

bijection 6-vertex configuration and alternating sign matrices  86-88   1:24:24

The end   89   1:27:01

Ch 2d     The LGV Lemma, binomial determinants,

XYZ-tableaux: rhombus tilings, plane partitions and non-intersecting paths

XYZ-tableaux: ASM, osculating paths and FPL

February 8, 2018

 

slides of Ch 2d   (pdf,  27 Mo)

slides of Ch 2d (complements)  (pdf,  20 Mo )                

video Ch2d: link to Ekalavya  (IMSc Media Center)

video Ch2d: link to YouTube

 

Reminding Ch 2c:   3   2:10

from a B.A.BA configuration (=Z-tableau) to a complete Z-tableau  6-7   2:49

quadratic algebra for rhombus tilings    12   5:29

quadratic algebra for square lattice tilings  (correction to Ch 2c)   16   6:34

border condition for Aztec tilings as Q-tableaux (missing in Ch 2c)   19   8:41

the six-vertex model as a Q-tableau with the border condition  23   12:02

Second geometric interpretation of Z-tableaux (XYZ-tableaux)   26   15:23

configuration of non-intersecting paths  (general with 2 parameters =0)(corrected figure)   29   17:34        

Ising model configuration ("closed graph")   31   21:13

Second geometric interpretation of Z-tableaux: 

"nice" configuration of non-intersecting paths (3 parameters =0)   32   24:02

The LGV Lemma  (from BJC 1, Ch 5a)   35   25:10

the crossing condition   40   28:00   

the LGV Lemma (in its simple form)   41   28:53

a simple example (Fermat matrix)   44   30:01

Non-intersecting paths and binomial determinant   48   31:09

definition of binomial determinants   50   31:28   34:22   

combinatorial interpretation of  binomial determinant  56   36:05    

Comparison of the quadratic algebras for rhombus tilings, plane partitions and  non-ingtersecting paths   62   37:29  

Bijections rhombus tilings, plane partitions and non-ingtersecting paths   66   38:49

Osculating paths  75   42:29

bijection ASM -- osculating paths   80-81   45:16   

Fully packed loops (FPL)   82   50:57

bijection  ASM -- FPL   86-92   55:12

About the bijection  ASM -- FPL   97   58:37

Taking the "complementary" of a B.A.BA configuration (Z-tableau)   103   1:03:15

A research problem about Z-tableaux related to correlations functions in XXZ spin chain   109   1:09:20

Some open questions about Ch 2   114   1:13:42

 

Complements: the beautiful garden of some jewels of combinatorics

ASM, TSSCPP, DPP, FPL, RS, ...  2     1:17:17

ASM and Bruhat order in the symmetric group, Schubert and Grothendick polynomials from ASM   3   1:17:17

Symmetric plane partitions   4    1:18:59  

Cyclicaly symmetric plane partitions   8   1:19:54

The ASM conjecture   12   1:21:55

Descending plane partition (DPP)   16   1:23:44

Totally symmetric plane partitions   20   1:26:26

Ten formulae   22   1:26:41

Totally symmetric self-complementary plane partitions (TSSCPP)   26   1:28:07

Andrews proof of the enumerative formula for TSSCPP   31   1:28:53

The proof of the AMS conjecture   32   1:29:20

Spin chain model and the Razumov-Stroganov (RS) conjecture   39  1:31:57

Markov chain on chord diagram   42   1:33:06

stationary probabilities with FPL and associated chord diagram   54-55   1:34:01

around the Razumov-Stroganov conjecture: q-KZ  (Di Francesco and Zinn-Justin)   56   1:35:21

more on ASM and orthogonal polynomials    57   1:35:54

The end   58   1:37:47