• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • 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
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • 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
    • Lectures related to the course
  • PART III
    • Preface
    • 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
    • Preface
    • 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
video Ch2a: link to bilibili
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
video Ch2b: link to bilibili
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
video Ch2c: link to bilibili
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
video Ch2d: link to bilibili
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:2834: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