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
GT LaBRI, Bordeaux, 16 December 2019 (part II)
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
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.
