Chapter 1a: RSK The Robinson-Schensted-Knuth correspondence

This series of lectures is at the crossroad of algebra, combinatorics and theoretical physics. I shall expose a new theory I call "cellular Ansatz", which offers a framework for a fruitful relation between quadratic algebras and combinatorics, extending some very classical theories such as the Robinson-Schensted-Knuth (RSK) correspondence between permutations and pairs of standard Young tableaux. In a first step, the cellular Ansatz is a methodology which allows, with a cellular approach on a square lattice, to associate some combinatorial objects (called Q-tableaux) to certain quadratic algebra Q defined by relations and generators. This notion is equivalent to the new notions (with a background from theoretical computer science) of "planar automata" or "planar rewriting rules". A Q-tableau is a Young (Ferrers) diagram, with some kind of labels in the cells of the diagram. The first basic example is the algebra defined by the relation UD=qDU+Id (or Weyl-Heisenberg algebra, well known in quantum physics). The associated Q-tableaux are the permutations, or more generally placements of towers on a Young diagram (Ferrers diagram). The second basic example is the algebra defined by the relation DE=qED+E+D which is fundamental for the resolution of the PASEP model ("partially asymmetric exclusion process"), a toy model in the physics of dynamical systems far from equilibrium, with the calculus of the stationary probabilities. Many recent researches have been made for the associated Q-tableaux, under the name or "alternative tableaux", "tree-like tableaux" or "permutations tableaux". Note that these last tableaux were introduced ("Le-diagrams") by Postnikov in relation with some positivity problems in algebraic geometry. Another algebra is the so-called XYZ algebra, related to the 8-vertex model in statistical physics, and is related to the famous alternating sign matrices, plane partitions, non-crossing configurations of paths and tilings on a planar lattice, such as the well-known Aztec tilings. In a second step, the cellular Ansatz allows a "guided" construction of bijections between Q-tableaux and other combinatorial objects, as soon one has a "representation" by combinatorial operators of the quadratic algebra Q. The basic example is the Weyl-Heisenberg algebra and we can recover the RSK correspondence with the Fomin formulation of "local rules" and "growth diagrams", from a representation of Q by operators acting on Ferrers diagrams (i.e. the theory of differential posets for the Young lattice). For the PASEP algebra, we get a bijection between alternative tableaux (or permutations tableaux) and permutations. The combinatorial theory of orthogonal polynomials (Flajolet, Viennot) plays an important role, in particular with the moments of q-Hermite, q-Laguerre and Askey-Wilson polynomials. Particular case is the TASEP (q=0) and is related to Catalan numbers and the Loday-Ronco Hopf algebra of binary trees. I shall finish by considering a third step in the cellular Ansatz, with the introduction of the idea of "demultiplication" of the relations defining the quadratic algebra Q, leading to guess a combinatorial representation of the algebra Q. In the case of the Weyl-Heisenberg algebra, we get back again the RSK correspondence, which translated in terms of planar automata leads to the new notion of bilateral RSK automata, related to the notion of duality in Young tableaux. We will also apply this methodology to the 8-vertex algebra, where many open problems remain, in particular for the alternating sign matrices.