• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • Abstract
    • Contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • Abstract
    • Contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Lectures related to the course
  • PART III
    • Preface
    • Abstract
    • Contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • References, comments and historical notes
  • PART IV
    • Preface
    • Introduction
    • Contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • References
  • Epilogue

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