XAVIER VIENNOT
  • Preface
    • Preface
    • Introduction
    • 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)

 

Preface

 

This is Part II of the so-called "video-book" "The Art of Bijective Combinatorics" ("ABjC" for short). It is based on a course given in 2017 at The Institute of Mathematical Science (IMSc), Chennai, India, at the invitation of Amritanshu Prasad (Amri).

 

Analogously to the other Parts of ABjC, there are 3 components:

- a set of 19 lectures video-recorded available on YouTube, Ekalavya  (the IMSc Media Center in India) and the Chinese chain bilibili

- the corresponding set of slides of each lecture,

- this website which enable one to navigate inside the videos, in the same way you turn around the pages of a book. For example if you click on the time given just after the slide number corresponding to one of the videos, you will get, up to one second, to exact position in the video.

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

 

In 1969 P. Cartier and D.Foata introduced the "commutation monoids", that is monoids of words defined up to a certain commutation of letters, in the monograph:

 P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, no. 85, Springer–Verlag, Berlin, New York, 1969.

 In 1985 the author introduced the notion of "heaps of pieces", as a geometric interpretation of these "commutation monoids". This interpretation is based on a powerful spatial intuition, which is missing in the vision with words, up to some commutation of letters, of the Cartier-Foata monoid. Of course everything written in terms of commutation monoids can be written in terms of heaps.

The paper is: G.X.V., Heaps of pieces. I. Basic definitions and combinatorial lemmas, in Combinatoire énumérative (Montréal, Québec,1985), vol. 1234 of Lecture Notes in Math., pp321–350, Springer, Berlin, 1986.

 

 

 

Some Figures

from the paper

Heaps of pieces I

 

 in Combinatoire

énumérative,

Montréal,

Québec  1985

LN in Maths n°1234

 

 In this paper, the author announce several papers in preparation (Heaps of pieces II, ..., V), papers which ... have never been written. Meanwhile the monograph of Cartier and Foata has been republished in the "books" section of the Séminaire Lotharingien de Combinatoire and an appendix was added in 2006 by C. Krattenthaler, The theory of heaps and the Cartier-Foata monoid.

 

It is the purpose of this course to complete the gap from the original 1986 paper, together with the exposition of many results and works which have been done since this paper, with connections and applications to physics (statistical mechanics, quantum gravity), computer science (Petri nets, asynchronous automata) and other parts of mathematics (orthogonal polynomials, totally commutative elements in Coxeter groups, chromatic polynomials and zeta function of graphs, Lie algebras, etc). The heaps methodology appears to be popular, as show by some recent (2020) work.

 

 For example, we just quote 5 recent papers written in 2020-21 where heaps plays a central role:

- A.M. Garsia and G. Ganzberger, Fibonacci polynomials, (18 pp) arXiv:2009.10213 [math.CO] Sep 2020.

- M.V. Tamm, N. Pospelov and S. Nechaev, Growth rate of 3D heaps of pieces, (14pp) arXiv: 2009.12540v2 [cond-math.stat-mech]  Oct 2020

- E. Bagno, R. Biagioli, F. Jouhet and Y. Roichman, Block number, descents and Schur positivity of fully commutative elements in B_n, (25 pp)

arXiv:2012.06412 [math.CO] Dec 2020.

- J. Cigler and C. Krattenthaler, Bounded Dyck paths, bounded alternating sequences, orthogonal polynomials, and reciprocity, (70 pp) arXiv:2012.03878 [math.CO] Dec 2020.

- L. Fredes, J.-F. Marckert, Aldous-Broder theorem: extension to the non reversible case and new combinatorial proof, (18 pp) arXiv: 2102.08639 [math.CO] Feb 2021

 

together with a chapter of the book (Lecture 4, Heaps, Continued Fractions and Orthogonal Polynomials, pp 97-135):

- A. M. Garsia and Ö. E ̆gecio ̆glu, Lectures in Algebraic Combinatorics, Lecture Notes in Math, vol 2277, Springer, Cham, 2020.

 

A course at two different levels

 I gave this course at two different levels at the same time. Most of the courses are supposed to be followed by good undergraduate students (at the Master level) and graduate students. I also gave some more advanced topics, opening some «windows» without proof, for graduate students, researchers and professors, in connection with active researches in combinatorics, and sometimes with connection in theoretical physics and computer science. Such sections are listed under the name «Complements». 

 

How to quote this video-book in the literature

The videos, slides and the address of this video-book ABjC will remain unchanged. It is possible to quote this video-book in the literature in the same way as quoting a book.  If you give only the direct link to a set of slides, or to the YouTube address of a video, the reader will miss the corresponding page giving the precise description of the slides, video and direct links in order to navigate inside the video. Also think of our Chinese colleagues, for which the link to the video is only through the popular Chinese chain "bilibili". 

 

I suggest the following:

-     if you want to quote this volume of ABjC, I suggest to quote in an analogous way to a book, with the editor (here IMSc), the place of edition (here Chennai) and the year (here 2017), for example:

The Art of Bijective Combinatorics, Part II, Commutations and heaps of pieces, IMSc, Chennai, 2017, http://www.viennot.org/abjc2.html

 the pointer is going to this web page (Preface of Part II of ABjC)

 

-     if you want to quote a precise point inside the video-book, as for example a definition, theorem or bijection, I suggest to refer to the number(s) of the corresponding slide(s). Example:  if you want to quote "1995 Stembridge’s characterization of fully commutative heaps" from Chapter 6a:

 The Art of Bijective Combinatorics, Part II, Commutations and heaps of pieces, Chapter  6a, IMSc, Chennai, 2017, p43, http://www.viennot.org/abjc2-ch6.html

the suffix abjc2-ch6.html refers to the web page dedicated to Chapter 6 of Part "II" of ABjC, this page contains the different slides and videos of the two corresponding lectures Ch6a, Ch6b. In front of slide 43 of Chapter 6a the reader will find the link  38:06 going directly to the YouTube video at slide 43.

 

 -     if you want to quote the whole collection of the 4 volumes then:

The Art of Bijective Combinatorics, IMSc, Chennai, 2016-2019, http://www.viennot.org/abjc.html

the suffix /abjc.html refers to the web page of the (general) preface of ABjC.