skip to content

Alternative tableaux, permutations and partially asymmetric exclusion process

Presented by: 
X Viennot [LaBRI/CNRS/Bordeaux 1]
Wednesday 23rd April 2008 - 14:00 to 15:00
INI Seminar Room 1

We introduce a new combinatorial object called "alternative tableau". This notion is at the heart of different topics: the combinatorics of permutations and of orthogonal polynomials, and in physics the model PASEP (partially asymmetric exclusion process).

The model PASEP have been recently intensively studied by combinatorists, in particular giving combinatorial interpretations of the stationary distribution (works of Brak, Corteel, Essam, Parvianinen, Rechnitzer, Williams, Duchi, Schaeffer, Viennot, ...). Some interpretations are in term of the so-called "permutation tableaux", introduced by Postnikov, followed by Steingrimsson and Williams, in relation with some considerations in algebraic geometry (total positivity on the Grassmannian).

Permutations tableaux have been studied by Postnikov, Steingrimsson, Williams, Burstein, Corteel, Nadeau and various bijections with permutations have been given. The advantage of introducing alternative tableaux is to give a complete symmetric role for rows and columns. We give a bijection between the two kinds of tableaux and a direct bijection between permutations and alternative tableaux. We also give combinatorial interpretation of the stationary distribution of the PASEP in term of alternative tableaux.

Then we show the relation between alternative tableaux and the combinatorial theory of orthogonal polynomials developed by Flajolet and the author. In particular the Françon-Viennot bijection between permutations and "Laguerre histories" (i.e. some weighted Motzkin paths) plays a central role here and enable us to construct another bijection between permutations and alternative tableaux.

This last bijection is in the same vein as the construction of the classical Robinson-Schensted-Knuth correspondence by "local rules" as originally defined by Fomin. The bijection can also be presented in analogy with Schützenberger "jeu de taquin". We finish the talk by giving "la cerise sur le gâteau": the surprising connection between the two bijections relating permutations and alternative tableaux.

Related Links

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons