Tianjin lectures 2019
A series of lectures on enumerative, algebraic and bijective combinatorics
as an introduction to the video-book "The Art of Bijective Combinatorics" (ABjC)
Department of Applied Mahematics, Tianjin Universisty, Tianjin, China, September 9-20, 2019
Many thanks to Professor (William) Yongchuan Chen for the invitation.
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.
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.
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. This lecture is a sample of the methodology developed in the "video-book" "The Art of Bijective Combinatorics" (ABjC)
The same conference was given as a colloquium at IMSc, Chennai, February 21, 2019 (lecture related to Part II and IV of the ABjC video-book)
slides (pdf, 28 Mo)
video link to Ekalavya (IMSc Media Center)
video link to bilibili
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.
slides (pdf, 42 Mo)
p9-80 RS with Schensted insertion process and geometric RS more details in ABjC, Part III, Ch1a, p3-128
p81-86 about posets more details in ABjC, Part III, Ch1b, p6-15
p87-134 Fomin growth diagrams more details in ABjC, Part III, Ch1b, p16-89
p135-139 rook placements more details in ABjC, Part III, Ch1e, p90-123
quick complement at the end of the lecture:
p141-172 the RSK bilateral edge local rules more details in ABjC, Part III, Ch1b, p98-159
p173-179 Schützenberger "jeu de taquin" more details in ABjC, Part III, Ch1d, p14-44 and 70-112
p180-190 edge local rules for RSK and dual RSK more details in ABjC, Part III, Ch1e, p.43-89
related paper to the lecture:
Growth diagrams and edge local rules, extended abstract, 10p. in Proceedings GASCom 2018, Athens, June 2018
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)"
slides (pdf, 24 Mo)
In lecture 2, we introduced 3 equivalent descriptions of the Robinson-Schensted correspondence: geometric description, Fomin's growth diagrams and local rules on edges. First I will give an idea of how growth diagrams description can be obtained from a representation of the most simple Heisenberg-Weyl algebra, a quadratic algebra defined by the generators U,D with commutation relation UD =DU +Id. Then I will extent this methodology to the so-called PASEP algebra by constructing a bijection between permutations and some tableaux called alternating tableaux.
The PASEP (partially asymmetric exclusion process) is a toy model in the physics of dynamical systems. It is a Markov chain on a set of particles moving on a strip. Explicit expressions for the stationary probabilities of the most general model (with 5 parameters) has been given by physicists, using the (orthogonal) Askey-Wilson polynomials. The resolution is based on a certain "matrix Ansatz" related to a quadratic algebra defined by generators and the unique relation DE = qED + E + D.
Many works have been done by combinatorists interpretating these stationary probabilities with certain families of weighted "tableaux", in particular the alternating tableaux. Deep combinatorics appears, related to the symmetric group and moments of orthogonal polynomials.
The two examples (Robinson-Schensted correspondence and PASEP with alternating tableaux) described in this lecture are part of a more general methodology I proposed to call "the cellular ansatz" and is described in more details in the video book "The Art of Bijective Combinatorics" (ABjC, part III, IMSc, 2018).
Lecture 4 September 18, 2019, An introduction to the combinatorial theory of orthogonal polynomials and continued fractions
slides (pdf, 28Mo)
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 some examples of interpretations of classical orthogonal polynomials and of their moments (Hermite, Laguerre, ...). I will give the basis of the theory interpreting the moments of general (formal) orthogonal polynomials and Jacobi continued fractions. The particular case of the moments of the Laguerre polynomials (given by n!) is related to Tianjin Lecture 3 about the representation of the PASEP algebra defined by DE = qED + E + D with the " FV bijection" between permutations and the so-called Laguerre histories.
more details in the video book "The Art of Bijective Combinatorics" (ABjC, part IV, IMSc, 2019).
Lecture 5 September 20, 2019, Tilings, determinants and non-crossing paths
slides (pdf, 39Mo)
The so-called LGV Lemma (Lindström-Gessel-X.V.) gives an interpretation of non-crossing configurations of weighted paths with some determinants. Under the so-called "crossing condition",many classical determinants appearing in combinatorics can be interpreted and easily computed. Non-crossing configurations of paths are related to tilings in graphs. I will give a "pure" bijective proof for the classical formula giving the number of tilings of the famous Aztec diagram. The first step is to use the interpretation of Hankel determinants coming from the combinatorial theory of orthogonal polynomials exposed in Tianjin Lecture 4. The second step is to use some classical bijections coming from the "Catalan garden" (staircase polygons, Dyck paths and 2-colored Motzkin paths). This lecture is touching several classical topics in combinatorics. The surprising relations and bijections between these various topics is an illustration of the beauty of combinatorics.
more details in the video book "The Art of Bijective Combinatorics" (ABjC, part I, Ch5, IMSc, 2016).