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 3 Heaps and Paths, Flows and Rearrangements monoids
Ch 3a
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
Ch 3b
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