• 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)

Abstract

A spectacular renaissance is appearing in combinatorial mathematics, in relation with other fields such as theoretical physics, probabilities theory, algebraic geometry, analysis of algorithms in computer science or molecular biology.   The bijective point of view replaces analytic proofs of identities by the construction of correspondences between classes of combinatorial objects. "Bijective tools" are emerging, putting some order in this very active domain. The subject of this course, "commutations and heaps of pieces", is one of this bijective tools. A wide variety of results comes from 3 fundamental lemma on heaps of pieces.
In 1969, Cartier and Foata introduced some monoids defined by generators and some partial commutations relations  ab=ba. These monoids were also introduced in computer  science under the name trace monoids as a model for concurrency access to data structures and parallelism. Heaps of pieces have been introduced by the speaker in 1985 as a geometric interpretation of such monoids. The spatial visualization of elements of the monoids in terms of heaps of pieces makes it very versatile for applications. Many authors have made various interactions of heaps theory to combinatorics, algebra (representation theory of Lie algebra), classical analysis (continued fractions, orthogonal polynomials), graph theory, computer science and theoretical physics (statistical mechanics, quantum gravity, ...).
This course is the second part of the «X.V. bijective course». The first part was given in 2016 at IMSc, see the website here. This second course can be followed independently. There will be some overlaps (formal power series and generating functions; the Catalan garden) with the first course.

The  playlist from matsciencechannel of the 19 videos of this course is here