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 The flow monoid, paths and flow monoid, rearrangement and heaps of cycles, the third basic lemma: the bijection paths -- heaps
30 January 2017
slides_Ch3a (pdf 16 Mo )
video Ch3a link to YouTube
video Ch3a link to bilibili
Cartier and Foata 3 0:22
The flow monoid 4 0:48
definition of the flow monoid F(X) 5-6 0:57
notation: flows and biwords 7-8 3:08
an example: flow as a heap of «half-edges» 9 5:39
the fllow monoid as a direct product of free monoids 10 7:17
notation: deg+(s) and deg-(s) 12 10:02
definition: the rearrangement monoid R(X) 13 12:19
discusison
rearrangement as "permutation" with repetition of letters 14 15:45
rearrangement: an example 15 (and 9) 17:02
Paths and flows monoid 16 17:13
path: definition and notations 17 17:30
weight of a path 18 21:08
the map f from path to flow 19 23:12
Algorithm «following a flow» 22 26:53
example 24-33 28:40
reconstructing the path from the flow 34-35 32:52
caracterisation of the starting and ending point of the path conditions (i), (ii), (iii) ) 36 34:38
discussion
the case of a circuit 37 39:37
reciprocal proposition for conditions (i), (ii), (iii) 38 39:48
"open hike" (Giscard, Rochet) 38 42:10
Rearrangements and heaps of cycles 39 42:57
the heaps of cycles monoid HC(X) 42-44 43:33
definitions: circuit, cycle and elementary circuit 43 44:00
definition: heap of cycles 44 45:37
an example of heap of cycles 45-49 46:40
definiiton: the map f from rearrangements to heaps of cycles 50 47:10
basic lemma: isomorphism f between the rearrangements monoid R(X) and the heaps of cycles monoid HC(X) 51 49:53
construction of the reciprocal map g 52-53 52:00
discussion (with student Bishal Deb and others, view of the classroom) 53:18
Paths and heaps of cycles 54 1:03:53
reminding notations on paths 55 1:04:19
visual intuitive idea of the fact that path = heap of cycles + self avoiding path 56 1:04:29
"philosophical" discussion about paths 1:05:48 view of the classroom 1:06:52
visual intuitive idea of the fact that path = heap of cycles + self avoiding path 57-64 1:10:04
the third basic lemma of the course relating paths and heaps of cycles 65 1:11:31
the special case of circuits (path going from u to v with u=v) 68 1:16:18
An example with Dyck paths 69 1:16:34
animation of the bijection with violin (violin: G.Duchamp) 70 1:16:41
The end 71 1:17:45
Ch 3b the bijection χ between paths and heaps, loop-erased process (LERW), example with Dyck paths, tree-like paths,
spanning tree of a graph, Wilson's algorithm for random spannning tree
2 February 2017
slides_Ch3b (pdf 19 Mo)
video Ch3b link to YouTube
video Ch3b link to bilibili
From the previous lecture 3-13 0:13
Variation of the proof rearrangements = heaps of cycles 14 11:38
discussion 14:44
(partial) endofuntion above a flow, support of a fllow 16 15:28
discussion 18:01
rearrangement and trees in the endofunction 17 19:59
discussion: correction to slide 17 21:03
an example 18 26:47
discussion (counter example to proposition of slide 17) 28:04
end of the proof 19 29:08
Remark on species endofunctions 20 31:17
an exercise 25 33:21
Paths and heaps of cycles 26 34:19
the bijection khi 27-28 34:34
definition of the bijection khi 29-31 38:53
loop-erased process (LERW, Lawler) 31 42:35
description of the reverse bijection 33-36 48:01
second proof 37 57:23
the bijection khi for circuits: pointed pyramids of cycles 38-39 59:09
An example with Dyck paths 40 1:00:52
animation with violin (G. Duchamp) 41 1:02:32
description of the reverse bijection 44-58 1:04:56
relation with lexicographic normal form 59 1:08:46
exercise 1: bilateral Dyck paths 61 1:09:08
exercise 2: non-backtracking paths 62 1:11:13
tree-like paths 63-65
tree-like paths: definition (Godsil) 63 1:13:37
exercise 3: bijection tree-like paths and paths on a tree 65 1:17:45
Complements: LERW (loop erased random walks, Lawler) 66 1:21:08
LERW and SLE2 (Schramm- Loewner) 68 1:22:00
LERW, abelian sanpile model and dimer model 69 1:23:04
first amazing fact (reversing the path) 70 1:23:32
proof 71-72
spanning tree of a graph 73-74 1:27:17
second amazing fact: random spanning tree and LERW 75 1:27:45
spanning tree associated to a path 78 1:29:09
research problem 1 79 1:29:53
Complements: Wilson’s algorithm for random spanning tree of a graph 80 1:31:25
description of the algorithm 81-88 1:31:29
3 animations of the algorithm on the video (by Mike Rostock) 89 1:33:24 ; 1:33:59 and 1:34:24 (best)
research problem 2 90-91 1:37:48
The end 92 1:39:42