XAVIER VIENNOT
  • PART I
    • 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
    • list of bijections
    • index
  • PART II
    • 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
    • Some lectures related to the course
  • PART III
    • 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
    • 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 1a 

5 January 2017

slides_Ch1a      (pdf  19 Mo)         video Ch 1a     

 

commutation monoid    slide:  3 

        a commutation equivalence class  8-14 

        Cartier and Foata 16-17 

        definition: product of two class 20 

        trace monoid   21

 

heaps  of pieces  22 

        some examples  23, 24

        heaps of pieces: main definition 27 

        example: heaps of segments 28 

        heaps of subsets  31 

        pyramids of hexagones  33, 36 

        heaps of cycles 41 

        the general picture: heap over a graph  42 

heaps monoid  43 

        definition: pre-heap 44 

        elementary move and equivalence of pre-heap  46, 50 

        definition: product of two heaps 57-63 

equivalence commutations monoids and heap monoids  64 

        the map phi: definition  65 

        the map phi: exemple  66-71 

        2 Lemma about the map phi 

        definition: the map phi bar  75 

        another example: heaps of dimers  77 

content of the course  90 

the end  100

Ch1b

9 January  2017

slides_Ch1b     (pdf  23 Mo)               video  Ch 1b

 

from the previous lecture  slide: 3

equivalence commutation monoids and heaps monoids

proof of Lemma 1  22

proof of Lemma 2  31

        Cartier-Foata normal form  32

        Lemma: relation between Cartier-normal form and levels in heaps 35

        end of the proof of the equivalence commutations - heaps

lexicographic (Knuth) normal form  44

        A Lemma about lexicographic normal form  48

        maximal and minimal letter of a commutation class 65

        Pyramid: definition  69

exercise: quasi-partition of integers  71

exercises: pyramids and semi-pyramids of dimers

        exercise: semi-pyramid of dimers  76

        Dyck paths 78

        exercise: pyramids of dimers 79

        bilateral Dyck paths 78

posets 82

        covering relation 83

        Hasse diagram of a poset 84

        linear extension of a poset 87

        example: Young tableaux  91

        example: increasing binary tree  93

heaps and posets 94

        posets associated to a heap 96

heaps and linear extensions 105

complements: heaps, posets and graphs  115

        definition: strongly covering of a poset  116

the end 123

Ch 1c

12 January 2017       

slides_Ch1c     (pdf  13Mo)              video Ch1c

 

from the previous lecture 3

solution of exercise: heaps = heaps of sets 13

        median graph of a graph 16

        starfish  19

        two examples  24, 26

the original definition of heaps of pieces 27

        the definition  29

        example  30

        equivalent definitions  31, 33

        product of two heaps 35

        heaps morphism  36

        example of isomorphic heaps  38, 39

heaps of dimers and symmetric group 40

the end 49