Course  X.V.  IMSc 2017


Course  IMSc  Chennai, India

January-March 2017

Ch3  Heaps and Paths,  Flows and Rearrangements monoids


             30 January 2017

                              slides_Ch3a        (pdf   16 Mo )             video Ch3a

Cartier and Foata  3

the flow monoid  4

        definition of the flow monoid  F(X)  6

        notation: flow, biword and heap of «half-edges»  9

        the rearrangement monoid  R(X)  13

        rearrangement: an example  15

paths and flows monoid  16

        path: definition and notation  17

        weight of a path  18

        the map  f  from path to flow

algorithm  «following a flow»  22

        example  24-33

        reconstructing the path from the flow  34-37

rearrangements and heaps of cycles  39

        the heaps of cycles monoid  HC(X)  42-44

        basic lemma: isomorphism  f  between rearrangements  R(X) and heaps of cycles  HC(X)  51

        construction of the reciprocal map g  52-53

paths and heaps of cycles  54

        visual intuitive idea of the fact that path = heap of cycles + self avoiding path  56-64

        the third basic lemma of the course relating path and heaps of cycles  65

        the special case of circuits  (path going from u to v with u=v)  68

an example with Dyck paths

        animation of the bijection with violin  (violin: G.Duchamp)  70

the end  71


           2 February  2017

                             slides_Ch3b        (pdf  19 Mo   )             video Ch3b

from the previous lecture  3-13

variation of the proof rearrangements = heaps of cycles 14

        correction to slide 17

remark on species endofunctions  20

        an exercise 25

paths and heaps of cycles  26

        the bijection  khi  27

        definition of the bijection khi  29-31

        description of the reverse bijection  33-36

        second proof  37

        the bijection khi for circuits  38

a example with Dyck paths  40

        animation with violin  (G. Duchamp)  41

        description of the reverse bijection 44-58

        relation with lexicographic normal form  59

        exercise 1 bilateral Dyck paths  61

        exercise 2 non-backtracking paths 62

        exercise 3 tree-like paths  65

complements: LERW  (loop erased random walks)  66

        first amazing fact (reversing the path)  70

        spanning tree of a graph

        second amazing fact: random spanning tree and LERW  75

        spanning tree associated to path  78

        research problem  79

complements: Wilson’s algorithm for random spanning tree of a graph  80

        description of the algorithm  81-88

        animation of the algorithm on the video  (by Mike Rostock)  89

        research problem 2  90-91

the end  92

go to:

the IMSc 2016 bijective course website

courses  website

main Xavier Viennot  website