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