• 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 6   Heaps  and  Coxeter  groups

Ch 6a   the heap monoid of a Coxeter group, reduced decomposition, heaps and fully commutative elements of Coxeter groups,
stair decomposition of a heap of dimers, fully commutative heaps of dimers, relation with parallelogram polyominoes,
bijection  FC elements -- (321)-avoiding permutations

23 February 2017
slides       (pdf  26  Mo)        
video Ch6a  link to YouTube
video Ch6a  link to bilibili
The heap monoid of a Coxeter group   3     0:22
        definition of a Coxeter group  4     0:29
        the associated Coxeter graph  6     3:49
        definition: the heap of a Coxeter group   7     5:11
        equivalent definition with the fibers over a vertex  s  and over an edge {s,t}  10     9:16
Reduced decomposition  13     12:49
definition: reduced decomposition in a Coxeter group   14     12:54
Matsumoto property   15     13:24
lemma: heaps, commutation class and reduced decompositions   16     14:50
discussion     16:12
Heaps of dimers and the symmetric group  17     20:03
visualization of a decomposition   19     21:46
discussion about the notation and the visualization     23:02
visualization of the braid relation   21     26:58
        visualization of a non-reduced decomposition   23-25     27:46
Elnitsky's lemma   26     28:45
        permutation associated to a heap of dimers  28-29     29:58
Fully commutative elements  (FC)  in Coxeter groups   31     30:57
        definition of a FC element and a FC heap  32     31:04
Stembridge's characterizations of a FC element in Coxeter groups   33     32:18
        definition: strict heaps  34     34:01
strict heap: an example   35-36     34:35
        definition: convex chain  37     34:52
convex chain: example   38-42     35:39
        Stembridge’s characterization of FC heaps   43     38:06
an example of Stembridge's characterization   44-45     40:24
papers of Fan, Graham and Stembridge   46     41:12
        the list of FC-finite Coxeter groups  47     42:45
affine Coxeter groups: papers of Biagioli, Jouhet, Nadeau, Bousquet-Mélou, Hanusa, Jones   48     44:22
Fully commutative elements for the symmetric group  49     45:35
The stair decomposition of a heap of dimers   50     46:03
        definition of a stair   52     46:22
        the stair decomposition   53     47:06
        the bijection heaps of dimers -- heaps of segments   54-57     48:19
Exercise   58     49:56
        Dyck paths, Lukasiewcz paths 
        pyramids of dimers, of segments, of oriented loops  (for Dyck paths)
Total order of the stairs in a heap of dimers   66      53:38
The stair lemma   75     56:28
Fully commutative heap of dimers  79     1:02:58
        characterization   82     1:04:20
Bijection  FC  heaps -- Dyck paths  83     1:06:13
Exercise  86     1:07:08
        heaps enumerated by n!   87
Bijection  FC heaps and parallelogram polyominoes  (=staircase polygons)  89     1:09:44
        reminding of chapter 2a, course IMSc 2016   97,98     1:12:03
        q-enumeration of FC elements in symmetric group  99     1:13:05
papers of Biagioli, Jouhet, Nadeau, Bousquet-Mélou, Hanusa, Jones   100
Nadeau's theorem (ultimately periodic rational q-series)   101     1:14:53
Exercise  102     1:15:21
        another characterization of FC elements for the symmetric group  102
The end  106     1:18:28

Ch 6b   the Temperley-Lieg algebra, complement: relation with symmetric functions, (321)-avoiding permutations, Jacobi-Trudi identity

27 February  2017
slides    (pdf  13  Mo)             
complements:      slides      (pdf )
video Ch6b  link to YouTube
video Ch6b  link to bilibili
from the previous lecture   3     0:22
bijection fully commutative (FC) heaps --  (321)-avoiding permutation   12     6:14
The Temperley-Lieb algebra  TL_n(beta)  20     10:17
        definition with relation and generators  21     10:39
        reduced words  25     14:03
        reduced heaps  26     16:57
a proposition about reduced heaps   27     17:39
        planar diagram  D(H) associated to a heap  H  of dimers  28-32     19:11
        proposition:  bijection  reduced heap -- planar diagram  35     23:26
a proposition about reduced word   39     28:50
planar diagrams enumerated by Catalan numbers   41     29:25
discussion   30:40
        product of planar diagrams  42-44     32:01
        Kauffman generators  45     34:20
        basis of Temperley-Lieb algebra  48-49     37:54
from a reduced heap of dimers to an element of the Temperley-Lieb algebra   52-55     40:39
        planar diagram associated to a skew-Ferrers diagram  56-57     41:36
exercise: RSK and FC heaps  58      43:21
nil-Temperley-Lieb algebra  66      48:20
        definition  67     48:29
        representation with operators acting on Ferrers diagrams  71     51:16
discussion     52:52
72     55:11
the end  (of the first part of the lecture)  73     59:37
complements: relation with symmetric functions   2     59:49
preparation for the definitin of the symmetric function F_sigma   4-8     1:00:42
definition of the symmetric function F_sigma  associated to a permutation  9     1:03:13
symmetric functions and (321)- avoiding permutations   13     1:07:51
        in this case, F_sigma is a skew Schur function    14     1:08:01
        bijection  skew (semi-standard) Young tableau and preheap   15-17     1:10:52
end of the proof: F_sigma is a skew Schur function when sigma is a (321)- avoiding permutation   21     1:12:35
relation with the configuration of non-intersecting paths related to Jacobi-Trudi identities   24-25    1:12:50
Jacobi-Trudi identities  26     1:13:12
        for homogeneous  symmetric functions   27-29     1:13:18
for elementary symmetric functions   30-32     1:13:43
        superposition of two dual configurations of non-intersecting paths  33     1:13:57
        duality in paths  34-37     1:14:06
        relation Jacobi-Trudi dual configurations of paths and Fomin-Kirillov construction
                      for F_sigma with sigma (321)-avoiding permutation  38-41     1:14:34
the end  43     1:17:20