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