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 6a the heap monoid of a Coxeter group, reduced decomposition, heaps and fully commutative elements of Coxeter groups,
stair decomposition of a heap of dimers, fully commutative heaps of dimers, relation with parallelogram polyominoes,
bijection FC elements -- (321)-avoiding permutations
23 February 2017
slides (pdf 26 Mo)
video Ch6a link to YouTube
video Ch6a link to bilibili
The heap monoid of a Coxeter group 3 0:22
definition of a Coxeter group 4 0:29
the associated Coxeter graph 6 3:49
definition: the heap of a Coxeter group 7 5:11
equivalent definition with the fibers over a vertex s and over an edge {s,t} 10 9:16
Reduced decomposition 13 12:49
definition: reduced decomposition in a Coxeter group 14 12:54
Matsumoto property 15 13:24
lemma: heaps, commutation class and reduced decompositions 16 14:50
discussion 16:12
Heaps of dimers and the symmetric group 17 20:03
visualization of a decomposition 19 21:46
discussion about the notation and the visualization 23:02
visualization of the braid relation 21 26:58
visualization of a non-reduced decomposition 23-25 27:46
Elnitsky's lemma 26 28:45
permutation associated to a heap of dimers 28-29 29:58
Fully commutative elements (FC) in Coxeter groups 31 30:57
definition of a FC element and a FC heap 32 31:04
Stembridge's characterizations of a FC element in Coxeter groups 33 32:18
definition: strict heaps 34 34:01
strict heap: an example 35-36 34:35
definition: convex chain 37 34:52
convex chain: example 38-42 35:39
Stembridge’s characterization of FC heaps 43 38:06
an example of Stembridge's characterization 44-45 40:24
papers of Fan, Graham and Stembridge 46 41:12
the list of FC-finite Coxeter groups 47 42:45
affine Coxeter groups: papers of Biagioli, Jouhet, Nadeau, Bousquet-Mélou, Hanusa, Jones 48 44:22
Fully commutative elements for the symmetric group 49 45:35
The stair decomposition of a heap of dimers 50 46:03
definition of a stair 52 46:22
the stair decomposition 53 47:06
the bijection heaps of dimers -- heaps of segments 54-57 48:19
Exercise 58 49:56
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 53:38
The stair lemma 75 56:28
Fully commutative heap of dimers 79 1:02:58
characterization 82 1:04:20
Bijection FC heaps -- Dyck paths 83 1:06:13
Exercise 86 1:07:08
heaps enumerated by n! 87
Bijection FC heaps and parallelogram polyominoes (=staircase polygons) 89 1:09:44
reminding of chapter 2a, course IMSc 2016 97,98 1:12:03
q-enumeration of FC elements in symmetric group 99 1:13:05
papers of Biagioli, Jouhet, Nadeau, Bousquet-Mélou, Hanusa, Jones 100
Nadeau's theorem (ultimately periodic rational q-series) 101 1:14:53
Exercise 102 1:15:21
another characterization of FC elements for the symmetric group 102
The end 106 1:18:28
Ch 6b the Temperley-Lieg algebra, complement: relation with symmetric functions, (321)-avoiding permutations, Jacobi-Trudi identity
27 February 2017
slides (pdf 13 Mo)
complements: slides (pdf )
video Ch6b link to YouTube
video Ch6b link to bilibili
from the previous lecture 3 0:22
bijection fully commutative (FC) heaps -- (321)-avoiding permutation 12 6:14
The Temperley-Lieb algebra TL_n(beta) 20 10:17
definition with relation and generators 21 10:39
reduced words 25 14:03
reduced heaps 26 16:57
a proposition about reduced heaps 27 17:39
planar diagram D(H) associated to a heap H of dimers 28-32 19:11
proposition: bijection reduced heap -- planar diagram 35 23:26
a proposition about reduced word 39 28:50
planar diagrams enumerated by Catalan numbers 41 29:25
discussion 30:40
product of planar diagrams 42-44 32:01
Kauffman generators 45 34:20
basis of Temperley-Lieb algebra 48-49 37:54
from a reduced heap of dimers to an element of the Temperley-Lieb algebra 52-55 40:39
planar diagram associated to a skew-Ferrers diagram 56-57 41:36
exercise: RSK and FC heaps 58 43:21
nil-Temperley-Lieb algebra 66 48:20
definition 67 48:29
representation with operators acting on Ferrers diagrams 71 51:16
discussion 52:52
72 55:11
the end (of the first part of the lecture) 73 59:37
complements: relation with symmetric functions 2 59:49
preparation for the definitin of the symmetric function F_sigma 4-8 1:00:42
definition of the symmetric function F_sigma associated to a permutation 9 1:03:13
symmetric functions and (321)- avoiding permutations 13 1:07:51
in this case, F_sigma is a skew Schur function 14 1:08:01
bijection skew (semi-standard) Young tableau and preheap 15-17 1:10:52
end of the proof: F_sigma is a skew Schur function when sigma is a (321)- avoiding permutation 21 1:12:35
relation with the configuration of non-intersecting paths related to Jacobi-Trudi identities 24-25 1:12:50
Jacobi-Trudi identities 26 1:13:12
for homogeneous symmetric functions 27-29 1:13:18
for elementary symmetric functions 30-32 1:13:43
superposition of two dual configurations of non-intersecting paths 33 1:13:57
duality in paths 34-37 1:14:06
relation Jacobi-Trudi dual configurations of paths and Fomin-Kirillov construction
for F_sigma with sigma (321)-avoiding permutation 38-41 1:14:34
the end 43 1:17:20