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

 

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

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

 

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 of Ch1d: link to Ekalavya  (IMSc Media Center)

video of Ch1d: link to YouTube

 

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:03   Betrema 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 of Ch1e: link to Ekalavya  (IMSc Media Center)

video of Ch1e: link to YouTube

 

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