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 1 Commutation monoids and heaps of pieces: basic definitions
Ch 1aCommutation, heaps of pieces, heaps monoids, equivalence commutation and heaps monoids
5 January 2017
slides_Ch1a (pdf 19 Mo)
video Ch 1a link to YouTube
video Ch 1a link to bilibili
video Ch 1a link to Vimeo
Commutation monoids slide: 3 0:18
example of a commutation equivalence class 6-14 0:43
Cartier and Foata 16-17 4:09
monoids, free monoids 18 4:51
congruence generated by commutations of variables 19 6:29
definition: commutation monoid, product of two commutation class 20 7:50
trace monoids in computer science 22 9:48
Heaps of pieces 23 11:58
example: heaps of dimers on a chessboard (intuitive definition) 24 12:15
example: words and heaps of dimers on the positive intergers (animation) 25 13:36
heaps of pieces: main definition 27-28 15:01
example: heaps of segments 29-30 19:10
heaps of subsets 32 21:34
pyramids of hexagones 34-37 22:49
heaps of cycles 41-42 26:30
the general picture: heap over a graph 43 28:15
Heaps monoids 44 29:57
definition: pre-heap 45 30:15
definition: elementary move and equivalence of pre-heaps 47-51 31:00
heaps as an equivalence class of pre-heaps 51 31:42
anti-heap 54 33:25
definition: product of two heaps 58-64 34:53
discussion: commutativity, what about inverses ? 36:58
Equivalence commutations monoids and heap monoids 65 39:06
the map phi from words to heaps: definition 66 39:22
the map phi: example 67-72 40:39
2 Lemma about the map phi 75 43:58
definition: the map phi bar 76 45:31
proposition: isomorphim between heaps monoid and commutations monoids 77 46:17
Another example: heaps of dimers on positikve integers 78 46:57
animation: two equivalent words giving the same heap of dimers 89-90 47:46
relations for braid group, symmetric group and Temperley-Lieb algebra 91 48:25
discussion 50:21
Content of the course 93 52:40
3 basic lemma 94 52:42
basic definitions and theorems 95 53:33
some applications to classical mathematics 96 53:52
some applications in theoretical physics 97 54:44
applications to more advanced mathematics 98 55:37
complementary topics 99 56:35
appearance of the 3 basic lemma in the course and its complements 100-102 58:30
some basic operators 103-106 1:00:41
The end 107 1:02:02
Ch1b Cartier normal form, lexicographic (Knuth) normal form, semi-pyramids (of dimers), heaps, posets and linear extensions
9 January 2017
slides_Ch1b (pdf 23 Mo)
video Ch 1b link to YouTube
video Ch 1b link to bilibili
From the previous lecture slide: 3 0:10
Equivalence commutation monoids and heaps monoids 15 3:44
Proof of Lemma 1 22 7:04
Proof of Lemma 2 31 8:24
Cartier-Foata normal form: definition 32 8:40
proof of the lemma defining Cartier-Foata normal form 33 11:40
Cartier-Foata normal form: an example 34 14:54
discussion 18:13
Lemma: relation between Cartier-normal form and levels in heaps 35 20:46
end of the proof of the equivalence commutations - heaps 39 23:27
exercise: clommutation monoids are simplificable 43 25:37
Lexicographic (Knuth) normal form 44 26:50
definition: minimal letter of a commutation equivalence class 46 27:34
A lemma about lexicographic normal form 48 28:46
an example (with minimal letter) 49-64 29:57
maximal and minimal letter of a commutation class 65 32:05
an example (with maximal letter) 66-68 32:20
Pyramid: definition 69 33:32
Exercise: quasi-partition of integers 71 34:23
definition: quasi-partition 73 35:12
exercise 1: bijection quasi-partitions and heaps of dimers (using lexicographic normal form) 74 37:31
Exercises: pyramids and semi-pyramids of dimers 75 38:52
definition: semi-pyramid of dimers 76 38:56
exercise 2: bijection semi-pyramids of dimers and Dyck paths (using exercise 1) 79 40:15 and 41:47
definition: Dyck paths 78 41:10
exercise 3: bijection pyramids of dimers and bilateral Dyck paths 80-81 42:20
Posets 82 45:04
definition: poset 83 45:12
covering relation 84 46:07
Hasse diagram of a poset 85 46:57
definition: linear extension of a poset 87 47:45
example: Young tableaux 89-91 49:01
example: increasing binary tree 92-93 50:05
Heaps and posets 94 51:09
intuitive idea of a poset associated to a heap 95 51:16
definition: poset associated to a heap 96 52:30
discussion 54:36
an example with heap of segments 97-99 56:50
discussion 57:20
an example with heap of cycles 100-102 58:05
D.Knuth and the french name "empilement" 58:18
minimal and maximal pieces 103 58:58
discussion 59:55
Heaps and linear extensions 105 1:01:04
proposiiton: bijection words in a commutation class and linear extensions 106 1:01:10
an exampe 107-109 1:02:13
an another example 110-113 1:03:40
summary of relations: graph, poset, commutation and heap monoid, word and linear extension 114 1:04:50
Complements: heaps, posets and graphs 115 1:06:22
proposition: every poset can be realized as a heap of pieces 116 1:06:30
definition: strongly covering of a poset 116 1:07:14
proposition: heap monoid and heap of subset of a set 122 1:11:07
The end 123 1:11:47
Ch 1c Equivalence heaps and heaps of subsets, 2nd (original) definition of heaps (over a graph), heaps of dimers and symmatric group
12 January 2017
slides_Ch1c (pdf 13Mo)
video Ch1c link to YouTube
video Ch1c link to bilibili
from the previous lecture 3 0:17
solution of exercise: heaps = heaps of sets 13 2:23
definition: median graph of a graph 16 3:32
definition: starfish 19 4:19
any heap is a heap of starfishes 21 5:08
any heap is a heap of cycles 22 6:20
example 1:heap of dimers on N 24 7:26
example 2 26 8:27
the original definition of heaps of pieces 27 9:58
second definition of heap of pieces (as a poset) 29 11:39
discussion 14:16
example 30 16:59
discussion 19:01
equivalent definition (heap as a poset) 31 20:02
discussion 23:20
from the second definition of heap as poset to the first definition with levels 33 27:16
equvalence of the two definitions of heaps 34 28:36
historical remarks about A. Joyal and topological extensions of the notion of heaps 28:58
definition: product of two heaps (as posets) 35 30:56
example of product of heaps (as posets) [an error in the original slides] 36-37 33:10
discussion 34:39
definition: heaps morphism 38 38:25
example of isomorphic heaps 39-41 39:42
heaps of dimers and symmetric group 42 40:38
the end 49 43:32