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 1a
5 January 2017
slides_Ch1a (pdf 19 Mo) video Ch 1a
commutation monoid slide: 3
a commutation equivalence class 8-14
Cartier and Foata 16-17
definition: product of two class 20
trace monoid 21
heaps of pieces 22
some examples 23, 24
heaps of pieces: main definition 27
example: heaps of segments 28
heaps of subsets 31
pyramids of hexagones 33, 36
heaps of cycles 41
the general picture: heap over a graph 42
heaps monoid 43
definition: pre-heap 44
elementary move and equivalence of pre-heap 46, 50
definition: product of two heaps 57-63
equivalence commutations monoids and heap monoids 64
the map phi: definition 65
the map phi: exemple 66-71
2 Lemma about the map phi
definition: the map phi bar 75
another example: heaps of dimers 77
content of the course 90
the end 100
Ch1b
9 January 2017
slides_Ch1b (pdf 23 Mo) video Ch 1b
from the previous lecture slide: 3
equivalence commutation monoids and heaps monoids
proof of Lemma 1 22
proof of Lemma 2 31
Cartier-Foata normal form 32
Lemma: relation between Cartier-normal form and levels in heaps 35
end of the proof of the equivalence commutations - heaps
lexicographic (Knuth) normal form 44
A Lemma about lexicographic normal form 48
maximal and minimal letter of a commutation class 65
Pyramid: definition 69
exercise: quasi-partition of integers 71
exercises: pyramids and semi-pyramids of dimers
exercise: semi-pyramid of dimers 76
Dyck paths 78
exercise: pyramids of dimers 79
bilateral Dyck paths 78
posets 82
covering relation 83
Hasse diagram of a poset 84
linear extension of a poset 87
example: Young tableaux 91
example: increasing binary tree 93
heaps and posets 94
posets associated to a heap 96
heaps and linear extensions 105
complements: heaps, posets and graphs 115
definition: strongly covering of a poset 116
the end 123
Ch 1c
12 January 2017
slides_Ch1c (pdf 13Mo) video Ch1c
from the previous lecture 3
solution of exercise: heaps = heaps of sets 13
median graph of a graph 16
starfish 19
two examples 24, 26
the original definition of heaps of pieces 27
the definition 29
example 30
equivalent definitions 31, 33
product of two heaps 35
heaps morphism 36
example of isomorphic heaps 38, 39
heaps of dimers and symmetric group 40
the end 49