• 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 1  Commutation monoids and heaps of pieces: basic definitions

Ch 1aCommutation, heaps of pieces, heaps monoids, equivalence commutation and heaps monoids

5 January 2017
slides_Ch1a      (pdf  19 Mo)        
video Ch 1a  link to YouTube
video Ch 1a  link to bilibili    
video Ch 1a link to Vimeo

Commutation monoids    slide:  3     0:18
        example of a commutation equivalence class  6-14     0:43
        Cartier and Foata 16-17     4:09
monoids, free monoids  18     4:51
congruence generated by commutations of variables   19     6:29
        definition: commutation monoid, product of two commutation class   20     7:50
        trace monoids in computer science   22     9:48
 Heaps  of pieces  23     11:58
        example: heaps of dimers on a chessboard (intuitive definition)  24     12:15
example: words and heaps of dimers on the positive intergers (animation)   25     13:36
        heaps of pieces: main definition  27-28     15:01
        example: heaps of segments   29-30     19:10
        heaps of subsets  32     21:34
        pyramids of hexagones  34-37     22:49
        heaps of cycles   41-42     26:30
        the general picture: heap over a graph  43     28:15
Heaps monoids  44     29:57
        definition: pre-heap 45     30:15
        definition: elementary move and equivalence of pre-heaps  47-51     31:00
heaps as an equivalence class of pre-heaps   51     31:42
anti-heap   54     33:25
        definition: product of two heaps 58-64     34:53
discussion: commutativity, what about inverses ?     36:58
Equivalence commutations monoids and heap monoids  65     39:06 
        the map phi from words to heaps: definition  66     39:22
        the map phi: example  67-72     40:39
        2 Lemma about the map phi   75     43:58
        definition: the map phi bar  76     45:31
proposition: isomorphim between heaps monoid and commutations monoids   77     46:17
Another example: heaps of dimers on positikve integers  78     46:57
animation: two equivalent words giving the same heap of dimers   89-90     47:46
relations for braid group, symmetric group and Temperley-Lieb algebra   91     48:25
discussion     50:21
Content of the course  93     52:40
3 basic lemma   94     52:42
basic definitions and theorems   95     53:33
some applications to classical mathematics   96     53:52
some applications in theoretical physics   97     54:44
applications to more advanced mathematics   98     55:37
complementary topics   99     56:35
appearance of the 3 basic lemma in the course and its complements 100-102     58:30
some basic operators   103-106    1:00:41
The end  107     1:02:02

Ch1b   Cartier normal form, lexicographic (Knuth) normal form, semi-pyramids (of dimers), heaps, posets and linear extensions

9 January  2017
slides_Ch1b     (pdf  23 Mo)              
video Ch 1b  link to YouTube
video Ch 1b  link to bilibili 
From the previous lecture  slide: 3     0:10
Equivalence commutation monoids and heaps monoids   15     3:44
Proof of Lemma 1  22     7:04
Proof of Lemma 2  31     8:24
        Cartier-Foata normal form: definition  32     8:40
proof of the lemma defining Cartier-Foata normal form   33     11:40
Cartier-Foata normal form: an example   34     14:54
discussion     18:13
        Lemma: relation between Cartier-normal form and levels in heaps  35     20:46
        end of the proof of the equivalence commutations - heaps   39     23:27
exercise: clommutation monoids are simplificable  43     25:37
Lexicographic (Knuth) normal form  44     26:50
definition: minimal letter of a commutation equivalence class   46     27:34
        A lemma about lexicographic normal form  48     28:46
an example (with minimal letter)   49-64  29:57
        maximal and minimal letter of a commutation class 65     32:05
an example  (with maximal letter)   66-68     32:20
        Pyramid: definition  69     33:32
Exercise: quasi-partition of integers  71     34:23
definition: quasi-partition   73     35:12
exercise 1: bijection quasi-partitions and heaps of dimers (using lexicographic normal form)   74     37:31
Exercises: pyramids and semi-pyramids of dimers   75     38:52
        definition: semi-pyramid of dimers  76     38:56
        exercise 2: bijection semi-pyramids of dimers and Dyck paths (using exercise 1)  79     40:15  and  41:47
definition: Dyck paths 78     41:10
        exercise 3: bijection pyramids of dimers and bilateral Dyck paths   80-81     42:20
Posets 82     45:04
definition: poset   83     45:12
        covering relation   84     46:07
        Hasse diagram of a poset   85     46:57
definition: linear extension of a poset   87     47:45
        example: Young tableaux  89-91     49:01
        example: increasing binary tree  92-93     50:05
Heaps and posets   94     51:09
intuitive idea of a poset associated to a heap   95     51:16
        definition: poset associated to a heap 96     52:30
discussion   54:36
an example with heap of segments   97-99     56:50
discussion   57:20
an example with heap of cycles   100-102     58:05
D.Knuth and the french name "empilement"     58:18
minimal and maximal pieces   103     58:58
discussion     59:55
Heaps and linear extensions 105     1:01:04
proposiiton: bijection words in a commutation class and linear extensions   106     1:01:10
an exampe   107-109     1:02:13
an another example   110-113     1:03:40
summary of relations: graph, poset, commutation and heap monoid, word and linear extension   114     1:04:50
Complements: heaps, posets and graphs  115     1:06:22
proposition: every poset can be realized as a heap of pieces   116     1:06:30
        definition: strongly covering of a poset  116     1:07:14
proposition: heap monoid and heap of subset of a set   122     1:11:07
The end 123     1:11:47

Ch 1c   Equivalence heaps and heaps of subsets, 2nd (original) definition of heaps (over a graph), heaps of dimers and symmatric group

12 January 2017       
slides_Ch1c     (pdf  13Mo)              
video Ch1c  link to YouTube
video Ch1c  link to bilibili 
from the previous lecture 3      0:17
solution of exercise: heaps = heaps of sets 13      2:23
        definition: median graph of a graph 16     3:32
        definition: starfish  19     4:19
any heap is a heap of starfishes   21     5:08
any heap is a heap of cycles   22     6:20
        example 1:heap of dimers on N  24     7:26
example 2   26     8:27
the original definition of heaps of pieces   27     9:58
        second definition of heap of pieces (as a poset)  29     11:39
discussion     14:16
        example  30     16:59
discussion   19:01
        equivalent definition (heap as a poset)  31     20:02
discussion   23:20
from the second definition of heap as poset to the first definition with levels  33     27:16
equvalence of the two definitions of heaps   34     28:36
historical remarks about A. Joyal and topological extensions of the notion of heaps     28:58
        definition: product of two heaps (as posets)  35     30:56
example of product of heaps (as posets) [an error in the original slides]   36-37     33:10
discussion    34:39
        definition: heaps morphism  38     38:25
        example of isomorphic heaps  39-41     39:42
heaps of dimers and symmetric group 42     40:38
the end 49     43:32