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 monoid**s", 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.*

**A companion paper** to the 1986 paper *Heaps of pieces. I. Basic definitions and combinatorial lemmas, *is the following:

G. Viennot, *Problèmes combinatoires posés par la physique statistique*, Astérisque, SMF, tome 121–122 (1985), **Séminaire Bourbaki**, 36ème année 1983/84, exposé 626, Feb 1984, p225–246. Available here on Numdam .

It is the purpose of this course to complete the gap from the original 1985 and 1986 papers, 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-21) work.

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

- Tyler Helmuth and Assaf Shapira, Loop-erased random walk as a spin system observable, (17pp) arXiv:2003:19928v2 [matrh.PR] Aug 2020

- 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

- P.-L. Giscard, Counting walks by their last erased self-avoiding polygons using sieves, (48pp) arXiv: 2001.02084 [math.CO] Nov 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.

Xavier Viennot

email: first name (at) name (dot) org