XAVIER VIENNOT
  • PART I
    • abstract
    • contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • list of bijections
    • index
  • PART II
    • abstract
    • contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Some lectures related to the course
  • PART III
    • abstract
    • contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • references, comments and historical notes
  • PART IV
    • introduction
    • contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • references
  • Epilogue

The Art of Bijective Combinatorics    Part III

The cellular ansatz:  bijective combinatorics and quadratic algebra

 

The Institute of Mathematical Sciences, Chennai, India  (January-March 2018)

Monday and Thursday, 11h30-13h, video room, first class: 4th January 2018

 

Abstract

 

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 relationUD=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.

 

  The  playlist from matsciencechannel of the 22 videos of this course is here