The Art of Bijective Combinatorics

Combinatorial theory of orthogonal polynomials and continued fractions

The Institute of Mathematical Sciences, Chennai, India (2016- 2019)

Epilogue

March 14 , 2019

slides of the Epilogue (pdf 38 Mo )

video Epilogue link to Ekalavya (IMSc Media Center)

video Epilogue link to YouTube (from IMSc Matsciencechanel Playlist)

video Epilogue link to bilibili

This lecture a repetition of the lecture I gave for the 60th birthday of Christian Krattenthaler, SLC81 (Séminaire Lotharigien de Combinatoire), Strobl, Austria, 11 September 2018,

+ some additionnal slides at the beginning and the end in the context of an Epilogue (which can also be considered as an introduction) to the four parts I, II, III, IV of the course at IMSc "the Art of bijective Combinatorics".

Piano recital Christian Krattenthaler playing at Mozarthaus, Sankt Gilgen, Austria, 10 September 2018

SLC81 lecture: The essence of bijections: from growth diagrams to Laguerre heaps of segments for the PASEP

dedicated to my friend Christian Krattenthaler for his 60th birthday

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.

Presentation of the course ABjC "The Art of Bijective Combinatorics" (IMSc, Chennai, 2016-2019) 3-7 2:02

Lagrange about Euler: going back to the sources 8 8:43

Krattenthalerfest, SLC 81, Strobl, Austria 9 9:50

The essence of bijections: from growth diagrams to Laguerre heaps of segments 10 11:34

Growth diamgrams (Fomin) (part III of ABjC) 13 12:04

Heaps of segments (part II of ABjC) 20 14:48

Laguerre (part IV of ABjC) 23 15:09

PASEP (part III of ABjC) 27 16:04

Combinatorial theory of orthogonal polynomials 32 20:36

The notion of histories, example: Hermite histories 42 24:49

q-analogue of Hermite histories 67 30:21

Combinatorics of the PASEP 73 32:32

Alternative tableaux 76 33:22

Enumeration of alternative tableaux 88 41:31

Interpretation of the 3-parameters partition function

first bijection tableaux -- permutations (Steingrimsson-Williams) 95 44:24

Bijection permutations -- subdivided Laguerre histories (de Médicis, X.V.) 104 50:55

Interpretation of the 3-parameters partition function

Second bijection: tableaux— permutations (Corteel, Nadeau) 121 53:30

Josuat-Vergès interpretation 124 55:47

Bijection Laguerre histories -- permutations (Françon - X.V.) 128 57:55

The essence of the parameter 31-2 134 1:02:50

The essence of bijections: growth diagrams and the RS bijection 146 1:08:07

The bijection Laguerre histories -- alternative tableaux

(from local rules related to the PASEP algebra) (X.V.) 155 1:12:55

Third bijection tableaux -- permutations

with tree-like tableaux (Aval, Boussicault, Nadeau) 172 1:16:17

Laguerre heaps of segments (X.V.) 203 1:23:28

Bijection permutations -- Laguerre heaps of segments 208 1:25:59

Bijection (restricted) Laguerre histories (of the inverse permutation) and Laguerre heaps of segments 233 1:29:14

What about the approach by physicists ? 250 1:33:38

5 parameters PASEP with the Askey-Wilson polynomials (Corteel, Williams) 256 1:34:07

Why to insist on the 3 parameters model: symmetries ...my dream ! 269 1:38:45

The Askey-wilson integral 279 1:39:59

Dyck tableaux as Laguerre subdivided histories (Aval, Boussicault, Dasse-Hartaut) 287 1:40:54

Direct biejction permutations -- Dyck tableaux 291 1:41:39

Contractions in continued fractions 305 1:42:15

Epilogue (of the Epilogue): The essence of bijecions 314 1:42:43

The bijection Dyck path -- semi-pyramid of dimers (violin: G. Duchamp) 319 1:43:40

The essence of 3 bijections in parallel (violin: G. Duchamp) 328 1:47:19

Many thanks 344

सरस्वती Saraswati, the goddess of knowledge, music, art, wisdom and learning 345