Chapter 1 of Part III of The Art of Bijective Combinatorics: RSK the Robinson-Schensted-Knuth correspondence

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