A Catalan staircase

alternative tableau

(in Maule 79th SLC)

email: X.V.

first name (at) name (dot) org

You are on the first page of the of X.V. (new) website: www.viennot.org

During the reconstruction the "old" website www.xavierviennot.org is still active.

This website contains the slides and links to the videos of the course I have given during four consecutive years at IMSc, the Institute of Mathematical Science, Chennai, India.

"The Art of Bijective Combinatorics"

The combinations of the slides, the videos and this website form a kind of "video-book" which is in construction, even if all the slides and links to the 77 lectures are there.

Preface

Part I: An introduction to enumerative, algebraic and bijective combinatorics (January-March 2016)

Part II: Commutations and heaps of pieces with interactions in physics, mathematics and computer science (January-March 2017)

Part III: The cellular ansatz: bijective combinatorics and quadratic algebra (January-March 2018)

Robinson-Schensted-Knuth, Asymmetric Exclusion Process, Tilings, Alternating Sign Matrices ... under the same roof

Part IV: A combinatorial theory of orthogonal polynomials and continued fractions (January-March 2019)

Epilogue

A mirror image in India of this website is here, kindly supported by the Institute of Maths Science (IMSc) at Chennai.

After March 16, 2019, I may not be able to update this mirror image . You may visit future versions on the original webiste www.viennot.org

last update: 27 September 2021

photo by Sergey Dovgal, CIRM, Luminy, June 2021

NEW: papers

A note: Some remarks on Baxter permutations and Baxter matrices (5 pages, 27 Sept 2021)

following Don Knuth's note "Baxter matrices" (05 Sept 2021, revised 11 Sept 2021)

An Interview with Toufik Mansour, Editor-in-Chief of ECA

ECA 2:1 (2022) Interview #S3I4

published on ECA (Enumerative Combinatorics and Applications)

30 April 2021

NEW: recent lectures

Lattice paths and heaps

colloque Lattice paths, combinatorics and interactions

Marches aléatoires, combinatoire et interactions

CIRM, Luminy, 25 June 2021

slides (pdf, 45 Mo)

augmented set of slides with the original slides of the video

+ some slides (in blue background) with references and comments on the questions at the end of the talk.

CIRM video

More details with detailed links in the video on the special page CIRM21

abstract:

Recently several papers appears on ArXiv, on various topics apparently unrelated such as: spin system observable (T. Helmuth, A. Shapira), Fibonacci polynomials (A. Garsia, G. Ganzberger), fully commutative elements in Coxeter groups (E. Bagno, R. Biagioli, F. Jouhet, Y. Roichman), reciprocity theorem for bounded Dyck paths (J. Cigler, C. Krattenthaler), uniform random spanning tree in graphs (L. Fredes, J.-F. Marckert). In each of these papers the theory of heaps of pieces plays a central role.

We propose a walk relating these topics, starting from the well-known loop erased random walk model (LERW), going around the classical bijection between lattice paths and heaps of cycles, and a second less known bijection due to T. Helmuth between lattice paths and heaps of oriented loops, in relation with the Ising model in physics, totally non-backtracking paths and zeta function in graphs.

For Dyck paths, these two bijections involve heaps of dimers and heaps of segments. A duality between these two kinds of heaps appears in some of the above papers, in relation with orthogonal polynomials and fully commutative elements. If time allows we will finish this excursion with the correspondence between heaps of segments, staircase polygons and q-Bessel functions.

An introduction to enumerative and bijective combinatorics with binary trees

conference given for TESSELATE - STEMS 2021, CMI, Chennai, India, 9 January 2021 (via Zoom Internet)

slides_STEMS2

slides_part I (pdf, 36Mo) slides_part II (pdf 22Mo)

slides (solution to the exercises)

video link to YouTube (1h35)

more details on the special page STEMS21

abstract

Trees and branching structures are everywhere in nature. Their mathematical abstraction leads to the notion of binary trees, a basic notion in computer science. The simple question "how many binary trees with n nodes", will give us the opportunity to travel from old and classical combinatorics to nowadays enumerative combinatorics. Its «philosophy» can be summarized in the following:« replacing calculus by figures and bijections, or conversely making calculus from the visual figures ».

Une bijection insolite pour les arbres binaires / A strange bijection for binary trees (part I)

GT LaBRI, Bordeaux, 9 December 2019

slides (pdf, 28 Mo)

GT LaBRI, Bordeaux, 16 December 2019 (part II)

slides(pdf, 27 Mo)

a video of the Tamil bijection

abstract

We present a bijection, probably new, between binary trees and pairs of vectors (w,h). The first component is the so-called canopy of the binary tree, introduced by Loday and Ronco in relation with some Hopf algebras of trees and permutations. This bijection can be defined directly, but is in fact a by-product of a more general methodology called « demultiplication of equations in a quadratic algebra ». This methodology can also produce the famous Robinson-Schensted correspondence between permutations and pairs of Young tableaux. We will introduce various concepts such as normal ordering, Wang tilings, Q-tableaux, reverse Q-tableaux, reverse quadratic algebra, planarization of the quadratic equations, demultiplication of equations, from which we will deduce the two above bijections. If time permits we will present other bijections, classical and new, obtained by this same methodology.

reference: Chapters 2 and 4, part III of "ABjC"

Tianjin lectures 2019

A series of lectures on enumerative, algebraic and bijective combinatorics giving an introduction to the video-book "The Art of Bijective Combinatorics" (ABjC)

Department of Applied Mathematics, Tianjin Universisty, Tianjin, China, September 9-20, 2019

Many thanks to Professor (William) Yongchuan Chen for the invitation.

Lecture 1 September 9, 2019, Proofs without words: the example of the Ramanujan continued fraction

A typical sample of enumerative and bijective combinatorics using symbolic method with the notion of heaps of pieces.

Lecture 2 September 11, 2019, An introduction to algebraic combinatorics with RSK (the Robinson-Schensted-correspondence)

RSK revisited: Fomin "growth diagrams", "geometric version", "edge local rules" and beyond.

Lecture 3 September 16, 2019, Quadratic algebra and bijective combinatorics: from RSK to the PASEP in physics and beyond

(an introduction to the "cellular ansatz" methogology)".

Lecture 4 September 18, 2019, An introduction to the combinatorial theory of orthogonal polynomials and continued fractions

Lecture 5 September 20, 2019, Tilings, determinants and non-crossing paths

more details on this Tianjin page

The video of Chapter 0, Part I of ABjC, introducing enumerative, algebraic and bijective combinatorics is available

here on the Chinese website bilibili with subtitles in Chinese thanks to Professor Shishuo Fu.

Laguerre heaps of segments for the PASEP

algebra and combinatorics seminar IISc, Bangalore, March 8, 2019

slides (pdf, 29 Mo)

abstract:

The PASEP (partially asymmetric exclusion process) is a toy model in the physics of dynamical systems strongly related to the moments of some classical orthogonal polynomials (Hermite, Laguerre, Askey-Wilson). The partition function has been interpreted with various combinatorial objects such as permutations, alternative and tree-like tableaux, etc. We introduce a new one called "Laguerre heaps of segments", which seems to play a central role in the network of bijections relating all these interpretations.

A survey of the combinatorial theory of orthogonal polynomials and continued fractions.

colloquium IISc, Bangalore, March 7, 2019

slides (pdf, 23 Mo)

abstract:

The theory of orthogonal polynomials started with analytic continued fractions going back to Euler, Gauss, Jacobi, Stieljes ... The combinatorial interpretations started in the late 70's and is a an active research domain. I will give the basis of the theory interpreting the moments of general (formal) orthogonal polynomials, Jacobi continued fractions and Hankel determinants with some families of weighted paths. In a second part I will give some examples of interpretations of classical orthogonal polynomials and of their moments (Hermite, Laguerre, Jacobi, ...) with their connection to theoretical physics.

Proofs without words: the example of the Ramanujan continued fraction

colloquium IMSc, Chennai, February 21, 2019

slides (pdf, 28 Mo) video link to YouTube (from IMSc Matsciencechanel Playlist)

abstract:

Visual proofs of identities were common at the Greek time, such as the Pythagoras theorem. In the same spirit, with the renaissance of combinatorics, visual proofs of much deeper identities become possible. Some identities can be interpreted at the combinatorial level, and the identity is a consequence of the construction a weight preserving bijection between the objects interpreting both sides of the identity.

In this lecture, I will give an example involving the famous and classical Ramanujan continued fraction. The construction is based on the concept of "heaps of pieces", which gives a spatial interpretation of the commutation monoids introduced by Cartier and Foata in 1969.

Zeta function on graphs revisited with the theory of heaps of pieces

ICGTA19, International Conference on Graph Theory and Applications, Amrita Vishwa Vidyapeetham Coimbatore, India, 5th January 2019

slides (second version after the talk, pdf, 39Mo)

abstract

An identity of Euler expresses the classical Rieman zeta function as a product involving prime numbers. Following Ihara, Selberg, Hashimoto, Sunada, Bass and many others, this function has been extended to arbitrary graphs by defining a certain notion of « prime » for a graph, as some non-backtracking prime circuits. Some formulae has been given expressing the zeta function of a graph. We will revisit these expressions with the theory of heaps of pieces, initiated by the speaker, as a geometric interpretation of the so-called commutation monoids introduced by Cartier and Foata. Three basic lemma on heaps will be used: inversion lemma, logarithmic lemma and the lemma expressing paths on a graphs as a heap. A simpler version of the zeta function of a graph proposed recently by Giscard and Rochet can be interpreted as heaps of elementary circuits, in relation with MacMahon's Master theorem.

Slides and video related to this talk can be found in the video-book « The Art of Bijective Combinatorics », Part II, Chapter 5b.

Empilements de Laguerre pour le PASEP

Groupe de travail Combinatoire, LaBRI, Bordeaux, 24 Septembre 2018

slides (in english, pdf 21 Mo, v2 some corrections after the talk)

résumé

Le PASEP ("partially asymmetric exclusion process) est un modèle très connu en physique des systèmes dynamiques ayant une combinatoire sous-jacente très riche et particulièrement étudiée par l'équipe bordelaise. Josuat-Vergès a donné une belle interprétation combinatoire de la fonction de partition du modèle à 3 paramètres en termes de permutations, en utilisant une combinaison de 4 bijections. Nous en donnons une autre preuve en introduisant un nouvel objet dans le jardin combinatoire du PASEP: les empilements de Laguerre, c'est-à-dire certains empilements de segments pointés, en bijection avec les permutations. Nous montrons le lien avec les tableaux de Dyck, les "histoires de Laguerre" et la structure de donnée "dictionnaire" en informatique.

The essence of bijctions: from growth diagrams to Laguerre heaps of segments for the PASEP

KrattenthalerFest, 81th SLC (Séminaire Lotharingien de Combinatoire) 11 September 2018

concert Christian

slides (pdf, 34Mo) a video (recorded on 14 March 2019 at IMSc, Chennai) of the same lecture is available on the page Epilogue

abstract

The PASEP (partially asymmetric exclusion process) is a toy model in the physics of dynamical systems with a very rich underlying combinatorics in relation with orthogonal polynomials culminating in the combinatorics of the moments of the Askey-Wilson polynomials. I will begin with a tour of the PASEP combinatorial garden with many objects such as alternative, tree-like and Dyck tableaux, Laguerre and subdivided Laguerre histories, all of them enumerated by n!. Using several bijections relating these objects, Josuat-Vergès gave the most simple interpretation of the partition function of the 3 parameters PASEP in terms of permutations related to the moments of the Al-Salam-Chihara polynomials.

This beautiful interpretation can be "explained" by introducing a new object called "Laguerre heaps of segments" having a central position among the several bijections of the PASEP garden. I will discuss some relations between these bijections and extract what can be called the "essence" of these bijections, some of them having the same "essence" as the Robinson-Schensted correspondence expressed with Fomin growth diagrams, dear to Christian.

Growth diagrams and edge local rules

GASCom 2018, Athens, Greece, 18 June 2018

slides (pdf,33 Mo)

paper (extended abstract, 10p. in Proceedings GASCom 2018)

abstract

Fomin growth diagrams for the Robinson-Schensted correspondence and for the jeu de taquin are some rules allowing the construction of the 4th Ferrers diagram once 3 Ferrers diagrams around an elementary cell are known.We propose here to replace these rules by some local rules on edges instead of local rules on vertices.

Keywords

Fomin growth diagrams, edge local rules, Schützenberger jeu de taquin, RSK product of two words, duality of Young tableaux.

Growth diagrams, local rules and beyond

21st Ramanujan Symposium: National Conference on algebra and its applications,

Ramanujan Institute, University of Madras, Chennai, India, 28 February 2018

slides part I (pdf, 17 Mo)

slides part II (pdf, 15 Mo)

abstract

Robinson-Schensted-Knuth correspondence (RSK), Schützenberger "jeu de taquin", Littlewood-Richarson coefficients are very classical objects in the combinatorics of Young tableaux, Schur functions and representation theory. Description has been given by Fomin in terms of "growth diagrams" and operators satisfying the commutation rules of the Weyl-Heisenberg algebra. After a survey of Fomin's approach, I will make a slight shift by introducing an equivalent description with "local rules on edges", and show how such point of view can be extended to some other quadratic algebras.

79th SLC (Séminaire Lotharingien de Combinatoire), Bertinoro, Italy, 11 September 2017

Maule: tilings, Young and Tamari lattices under the same roof

slides part I(pdf, 25 Mo) tilings, Young and Tamari lattices as maules

slides part II (pdf, 26 Mo) Tamari(v) as a maule + comments and references added after the talk

Same lectures is given at IMSc, Chennai, India in two video-recorded Maths seminars 19 and 26 February 2018

(slightly augmented) set of slides and video links are available on this page.