course  X.V.  IMSC 2017


Course  IMSc  Chennai, India

January-March 2017

Enumerative and algebraic combinatorics,

a bijective approach:

commutations and heaps of pieces

(with interactions in physics, mathematics and computer science)



Ch 1  Commutation monoids and heaps of pieces: basic definitions

    5 January 2017

                               slides_Ch1a      (pdf    18,9Mo)         video Ch 1a     

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


    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


             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

go to:

the IMSc 2016 bijective course website

courses  website

main Xavier Viennot  website