Course X.V. IMSc 2017
Course IMSc Chennai, India
January-March 2017
Ch3 Heaps and Paths, Flows and Rearrangements monoids
Ch3a
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
Ch3b
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
