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