• 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 1   RSK   The Robinson-Schensted-Knuth  correspondence
Ch 1a     The RS correspondence: Schensted insertions, geometric version with shadow lines

January 9, 2018
slides of Ch 1a   (pdf 28Mo)                 
video Ch1a: link to Ekalavya  (IMSc Media Center)
video Ch1a: link to YouTube
video ch1a:  link to bilibili

Young tableaux  p.3     0:0:32

Hook length formula  7    0:05:38"
An introduction to RS  16    0:09:45
RS with Schensted's insertions  21   0:13:19
from a permutation to a pair (P,Q) of Young tableaux
Reverse algorithm  45   0:20: 41
Exchanging P and Q  52   0:22:46
a citation of D.Knuth  74   0:25:58
More about groups theory  74   0:27:11
representation of finite groups
A geometric version of RS with "light" and "shadow lines"  81   0:32:10
the skeleton of a permutation (the set of "red points")  93-94   0:37:30
Lemma about the skeleton and its proof  95-99   0:38:27
the symmetry (P,Q) and inverse permutation explained 112   0:52:12
proof of the equivalence Schensted's insertions and "geometric construction" 114   0:54:11
exercise: characterization of the skeleton of a permutation (the red points) 121   1:01:56
Rothe diagram of a permutation  123   1:02:29
Nim game on the Rothe diagram  124   1:04':23"
Kernel of a graph  129   1:05':39"
increasing and decreasing subsequences f maximal size  130   1:07:52
"geometric" proof of the propriety for increasing subsequences  133   1:15:50
"geometric" proof of the propriety for decreasing subsequences  137-145   1:19:25
Corollary: the Erdös-Szekeres theorem   1:21:46
Extension: Greene's theorem 149   1:23:08
The end  155   1:27:00

Ch1b     The RS correspondence: Fomin growth diagrams, edge local rules,
the bilateral RSK planar automaton, dual of a tableau

January11,  2018
slides of Ch1b     (pdf 29 Mo)
video Ch1b: link to Ekalavya  (IMSc Media Center)
video Ch1b: link to YouTube
video Ch1b: link to bilibili
From Ch1a  3
A few things about poset  p.6   0:01:55
the Young lattice  8   0:02:58
lattice: definition  9   0:03:42
the square lattice [n]x[n]  10-13  0:04:08
maximal chain in poset  14   0:06:25
bijection Young tableau -- maximal chain in the Young lattice  14  0:07:20
"local" alglorithm on a grid or "growth diagram"  16   0:09:11
notations: operator Ui  adding a cell in a Ferrers diagram  21   0:11:23
the six local rules  23    0:13:43   or 26-27   0:20:08
the four local rules 24   0:19:50
an example where the 6 rules appear  31-36   0:22:38
some facts about the local algorithm  37-44   0:26:47
Recalling the geometric version of RS with "light "and "shadow lines" 46  0:33:03
Proof of the equivalence local RS (growth diagrams) and geometric RS  61   0:36:33
from the geometry of shadows lines to the tableau of Ferrers diagram   0:37:12
labeling the shadows lines 1,2,3,...   0:38:38
the two elementary obvious facts giving the proof of the equivalence  0:39:00  and  0:40:34
the end of the proof with the 6 local rules  0:41:36
The reverse RSK planar automaton  79   0:46:28
comparing local rules on vertices and local rules on edges   0:50:30
a claim: local rules on vertices or local rules on edges ?  83   0:53:45
Planar automaton  90   0:55:53
definition of a planar automaton  93-95   0:59:00
example: finite automaton  96   1:02:21
The RSK planar automaton  98   1:04:34
The bilateral RSK planar automaton  106   1:06:12
the RSK planar product of two words  111   1:09:21
Schützenberger's duality with the RSK bilateral automaton  119   1:11:17
Dual of a Young tableau  120   1:12:05
another example of evacuation and dual tableau  1:14:57
notations: transpose, complement and sharp of a permutation  158   1:15:44
two propositions of Schütenbergers on RSK and duality  159   1:16:10
Duality is an involution  159   1:16:27
More duality properties  161  1:17:04
The end  172   1:19:22

Ch1c     the cellular ansatz: planarisation of the rewriting rules, Q-tableaux, commutations diagrams
and growth diagrams, rook placements

January18,  2018
slides of Ch1c     (pdf,  17 Mo)
video Ch1c: link to Ekalavya  (IMSc Media Center)
video Ch1c: link to YouTube
video Ch1c:  link to bilibili
reminding the essential of Ch1a and Ch1b   p.3  0:39
summary of the cellular ansatz first and second step with the example UD=DU+I   9   3:14
planarization of the rewriting rules   15   10:20
an exemple of planar rewriting with w=U...UD...D   18-43   13:20
permutation as a complete Q-tableau  44   17:51
example of Q-tableau   20:03
permutation as a Q-tableau   47   20:20
Rothe diagram as a Q-tableau   50   23:00
Definition of a complete Q-tableau   51   23:35
the map phi from R (set of rewriting rules) to L (set of labels)   30:43
the condition (*) for the map phi     30:55
bijection Q-tableau - complete Q-tableau   53   31:55
rooks placement   35:05
the cellular ansatz, second part: guided construction of a bijection from the representation of U and D as operators   57    36:52
representation of the algebra UD=DU+I with operators acting on Ferrers diagrams   61  39:09
visual proof of the relation UD=DU+I   72   45:38
direct proof of the identity   n! = sum (f_lambda)^2   75   48:56
construction of the RSK correspondence by "propagation" on the grid [n]x[n] of an elementary bijection
on "commutations diagrams" explaining the relation the relation  UD=DU+I  80  52:50
definition of "commutations diagrams"with operators and "positions"    55:26
3 cases for the "commutations diagrams" bijection   84-86    1:00:16
admissible sequences  90   1:07:40
"propagation" of the "commutation diagrams" on the grid [n]x[n]   93   1:11:10

the bijection (which is the same as RS) deduced from this propagation  94   1:14:30

rook placements   98    1:17:42
planarization of the rewriting rules for a general Ferrers diagram   99-110   1:17:55
rook placements as a complete Q-tableau   111   1:18:10
expression of the normal ordering with rook placements on a Ferrers board   112-113   1:18:52
binary tree associated to a possible rewriting process  115   1:21:34
independancy of the order of the substitutions for normal ordering   117   1:23:19
Another representation of the algebra  UD=DU+I    1:23:59
Polya urns   119   1:24:13
associated bijection and inversion table of permutation  124   1:25:46
priority queue in computer science and associated bijection (exercise) 125   1:29:08
The end  126   1:31:48

Ch1d     Schützenberger jeu de taquin, Knuth transpositions, Fomin (vertex) local rules for jeu de taquin,
edge local rules for jeu de taquin, nil-Temperley-Lieb algebra

January 22, 2018
slides of Ch1d       (pdf   21Mo )
video Ch1d: link to Ekalavya  (IMSc Media Center)
video Ch1d: link to YouTube
video Ch1d: link to bilibili
reminding the essential of Ch 1a, 1b, 1c   p.3   0:22
Schützenberger jeu de taquin:example with a permutation  14   3:02
Knuth transposition  45   10:57
definition  46   11:09
The insertion tableau is invariant under a Knuth transposition  50   15:16
exemple with a permutation  52-53   17:09
the essence of the geometric proof  56-58   18:39
reading word of a Young tableau: definition  59   25:23
any permutation is Knuth equivalent to the reading word of its insertion tableau  60   26:34
proof of this lemma  61-62   28:31
two permutations are Knuth equivalent iff they have the same insertion tableau  63   32:46
regular permutations  65   34:32
Schützenberger jeu de taquin (for skew Young tableaux)  70   44:47
symmetry of the jeu de taquin  72   46:02
jeu de taquin, reading word and Knuth equivalence  76   48:12
each jeu de taquin equivalence class contains exactly one straight shape tableau  79   52:20
Jeu de taquin with Fomin growth diagrams  83   56:31
coding of the jeu de taquin with a rectangular tableau of Ferrers diagrams  88   59:04
Fomin local rules: case (1) and case (2)  89   1:00:52
Jeu de taquin with local rules on the edges  96   1:05:04
the diagonal operators  Delta(i)  97   1:05:38
local rules with the operators Delta  102   1:09:06
local rules with "labeled lines" crossing (case 2) or osculating (case 1)  103   1:10:18
dual of a Young tableau (with Fomin local rules)  106   1:12:12
dual of a Young tableau (with labeled lines local rules)  107   1:12:42
self-dual Young tableaux in bijection with domino tableaux  109   1:14:35
Betrema coloring  111     1:16:03Betrema website "Tableaux"  Betrema blog ASM &Co
Delta operator and nil-Tempeley-Lieb algebra  113   1:20:34
definition of the nil-Temperley-algebra  116   1:21:22
heaps of pieces (see course BJC Part II)  120   1:23:12
basis for nil-Temperley-Lieb algebra (see course BJC Part II, Ch6b)  124   1:24:15
A problem  128   1:25:00
The end  130   1:27:43

Ch1e     Greene theorem, from RS to RSK, edge local rules for RSK and dual RSK, bijections for rook placements 

January 25, 2018
slides of Ch1e   (pdf  27 Mo)
video Ch1e: link to Ekalavya  (IMSc Media Center)
video Ch1e: link to YouTube
video Ch1e: link to bilibili
reminding the essential of Ch 1a, 1b, 1c, 1d   p.3   0:22
Greene theorem  14   2:54
Greene theorem   17   4:00
Lemma: invariance of I_k and D_l under Knuth transpositions  22   8:05
Greene theorem for regular permuations  23   9:25
behaviour of the pair (P,Q) under the symmetries of the square  25-27   13:17
an example with the mirror image of a permutation (transpose)  28   19:31
a reseach problem  39-42   20:46
From RS to RSK  43   26:09
type of an integer matrix  44   26:27
from an integer matrix to a two line array (or generalized permutation)  48   28:04
an example: the pair (P,Q) for a matrix M  52, 53   31:02
definition of a semi-standard Young tableau  54   33:04
the RSK theorem: bijection integer matrices M and pairs (P,Q) of semi-standard Young tableaux  55   35:00
Proof of the RSK theorem  56   35:59
advances of a permutation and insertion tableau P  57   36:03
descents of a permutation and recording tableau  59   37:58
Local rules for RSK  62   42:48
local rules (on edges) for RSK  70   49:47
an example  72   51:42
local rules and growth diagrams: two examples  73-76   53:37
Dual RSK  77   59:23
from an integer matrix to a permutation  79-81  1:00:18
an example of the dual RSK  82-85  1:01:02
proof of the correspondence for dual RSK  86-87  1:05:56
local rules (onedges) for dual RSK  88  1:06:24
Bijections for rooks placements  90   1:12:08
bijection between rooks placements and oscillating tableaux  91   1:12:20
bijection between rooks placements and Hermite histories  93   1:15:01
bijection between Hermite histories and involutions with no fixed points: an example  96-114   1:17:25
bijection between "2-colored vacillating tableaux" and "2-colored involutions"  115-116   1:19:20
Rooks placements and set partitions  118   1:21:56
exercise: find a bijection between rooks placements on a staircase Ferrers board and set partitions  120   1:22:05
exercise: relation with the paper of Chen, Deng, Du, Stanley, Yan (2005) 123   1:23:19
Wick theorem in quantum mechanics (and rooks placements)  124   1:24:27
double dot operation, Wick theorem  126   1:25:49
Differential posets  130   1:29:26
the Young-Fibonacci lattice  131   1:29:29
exercise with the Young-Fibonacci lattice  132   1:30:56
differential poset: definition  133   1:31:26
two propositions about differential posets  135-136   1:31:50
The end 137   1:33:35