The Art of Bijective Combinatorics Part II
Commutations and heaps of pieces with interactions in physics, mathematics and computer science
The Institute of Mathematical Sciences, Chennai, India (January-March 2017)
Ch 6 Heaps and Coxeter groups
Ch 6 a
23 February 201
slides (pdf 26 Mo) video ch6a
the heap monoid of a Coxeter group 3
definition of a Coxeter group 4
the associated Coxeter graph 6
definition: the heap of a Coxeter group 7
equivalent definition with the fibers over a vertex s and over an edge {s,t} 10
reduced decomposition 13
heaps of dimers and the symmetric group 17
a non-reduced decomposition 23-25
permutation associated to a heap of dimers 29
fully commutative elements (FC) in Coxeter groups 31
definition of a FC element and a FC heap 32
strict heaps 34
convex chain 37
Stembridge’s characterization of FC heaps 43
the list of FC-finite Coxeter groups 47
fully commutative elements for the symmetric group 49
the stair decomposition of a heap of dimers 50
definition of a stair 52
the stair decomposition 53
the bijection heaps of dimers -- heaps of segments 55
exercise 58
Dyck paths, Lukasiewcz paths
pyramids of dimers, of segments, of oriented loops (for Dyck paths)
total order of the stairs in a heap of dimers 66
the stair lemma 75
fully commutative heap of dimers 79
characterization 82
bijection FC heaps -- Dyck paths 83
exercise 86
heaps enumerated by n!
bijection FC heaps and parallelogram polyominoes (=staircase polygons) 89
reminding of chapter 2a, course IMSc 2016 97,98
q-enumeration of FC elements in Symmetric group 99
exercise 102
another characterization of FC elements for the symmetric group 102
the end 106
Ch 6 b
27 February 2007
slides (pdf 13 Mo) video Ch6b
complements: slides (pdf )
from the previous lecture 3
bijection fully commutative (FC) heaps -- (321)-avoiding permutation 12
The Temperley-Lieb algebra TL_n(beta) 20
definition with relation and generators 21
reduced words 25
reduced heaps 26
planar diagram D(H) associated to a heap H of dimers 32
proposition: bijection reduced heap -- planar diagram 35
product of planar diagrams 44
Kauffman generators 45
Basis of Temperley-Lieb algebra 48-49
planar diagram associated to a skew-Ferrers diagram 56-57
exercise: RSK and FC heaps 58
nil-Temperley-Lieb algebra 66
definition 67
representation with operators acting on Ferrers diagrams 71
the end (of the first part of the lecture) 73
complements: relation with symmetric functions
definition of the symmetric function F_sigma associated to a permutation 9
symmetric functions and (321)- avoiding permutations 13
in this case, F_sigma is a skew Schur function
bijection skew (semi-standard) Young tableau and preheap
Jacobi-Trudi identities 26
for homogeneous and elementary symmetric functions
superposition of two dual configurations of non-intersecting paths 33
duality in paths 34-37
relation Jacobi-Trudi dual configurations of paths and Fomin-Kirillov construction
for F_sigma with sigma (321)-avoiding permutation 39-41
the end 43