Course  IIT  Bombay 

January-February 2013

Algebraic combinatorics and interactions

the cellular Ansatz

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".

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 theroy 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. We will apply this methodology to the 8-vertex algebra, where many open problems remain, in particular for the alternating sign matrices.

First lecture  Ch0

Monday January 7, 2013  afternoon

Introduction  and  overview of the course         slides          (pdf  7,7 Mo)

                complementary slides          (pdf  1,1  Mo, example of planarization)

Ch 1     The Robinson-Schensted correspondence

              11 january 2013               slides            (pdf  16,7  Mo, 134p.)

Young tableaux  p.2

Hook length formula  p.7

Introduction to RSK p.16

RSK  with Schensted's insertions p.22

A geomeric version of RSK with "light" and "shadow lines" p.48

proof of the equivalence insertions - geometric construction p.71

applications: increasing and decreasing subsequences  p.78

"jeu de taquin"  p.89

an example in the class p.90

another example p.102

furthet developements p126

Fomin "local" algorithm on a grid or "growth diagrams"  p.128

                16 january 2013         slides          (pdf  10,7  Mo, 110p)  (version2, corrections on p40-42

Fomin «local» algorithm on a grid or «growth diagrams», more details p.2

proof of the equivalence local RSK and geometric RSK p21

oscillating tableaux  p.39

duality  p.42

some complements:

    Knuth’s transpositions  p.90

    extension to matrices: from  RS  to  RSK  p.96

    operators deltas for Greene’s theorem  p.101

    (p,q)-grid  p.106

some references  p.108-110

Ch2   Representation with operators: from the algebra UD=DU+I to RSK

               19 january 2013              slides                  (pdf    4,8 Mo, 110p)

the Wel-Heisenberg  algeba,  normal ordering  p2

planarization on a grid of the rewriting rules  p12

rook placements  p50

bijections for rook placements  p67

representation of U and D as operators acting on Ferrers diagrams  p72

direect proof of the fact that n! is the number of Young tableaux with same shape p85

construction of the RSK  bijection by «propagation» of the cell commutation diagrams bijection p85

conclusion: the philosophy of the cellular Ansatz in the case of RSK and the algebra UD=DU+I  p106

Ch3   Alternative tableaux and the PASEP algebra DE+ED+E+D

                 21  january 2013           slides       (part I)          (pdf   9,9  Mo, 117p)

the PASEP p2

the matrix Ansatz  p19

the PASEP algebra  DE=ED+E+D  p26

allternative tableaux  p50

the exchange-fusion algorithm  p57

the inverse exchange-fusion algorithm  p76

Genocchi sequence of a permutation p91

some parameters   p98

references  p108

                   23  january  2013    slides     (part II)  (pdf   5,2  Mo, 74p))               

permutations tableaux  p2

orthogonal polynomials in relation with the PASEP  p27

the FV bijection  permutations -- Laguerre histories p30

weighted Motzkin paths  p31

Laguerre histories: definition  p36

the FV bijection: description with binary trees  p41

reciprocal bijection  p53

the FV  bijection: description in terms of words, q-Laguerre   p62

               30  january  2013        slides      (part III)      (pdf    9  Mo,  117p)

alternative tableaux  (recall) p3

representation of the PASEP algebra  DE=ED+E+D with combinatorial opetators  p9

The FV bijection Laguerre histories -- permutations  (recall Ch3b)  p19

The FV bijection with operators p34

direct proof for the number of alternating tableaux = (n+1)!  p41

analogy with the Weyl-Heisenberg algebra (Ch 2) p48

from computer science: data structure dictionary  p52

from computer science: data structure priority queue, Polya urns  p66

commutation diagrams p77

commutation diagrams bijection  p83

construction of the bijection  permutations -- alternative tableaux from the representation p85

inverse bijection  permutations -- alternative tableaux  p99

two bijections, one theorem  p107

references  p111

Ch 4  TASEP  and the Catalan garden

                   1 February 2013

         Ch4a  The Catalan garden        slides   (pdf  7  Mo   38p)     2  videos: bijections with violins

Leonhard and Catalan numberrs p4

from triangulations to binary trees p5

from binary trees to Dyck paths  p19

binary trees and complete binary trees p24

chords diagram  p27

staircase polygons, parallelogram polyominoes and 2-colored Motzkin paths  p30

         Ch4b  TASEP and Catalan alternative tableaux   slides  (pdf  5,1 Mo  68p)

Catalan alternative tableaux  p2

bijection Catalan alternative tableaux -- binary trees p8

stationary probabilities for TASEP   p26

Catalan pemutation tableaux  p39

characterization of Catalan alternative tableaux  p44

TASEP with Catalan tableaux and staircase polygons  p57

          Ch4c     Catalan alternative tableaux and Loday-Ronco algebra of binary trees    slides    (pdf  4,8 Mo  75p)

increasing binary trees, canopy and up-down sequence  p2

«jeu de taquin» for increasing binary trees  p13

«jeu de taquin»: from increasing binary trees to Catalan alternative tableaux  p30

complements: alternative binary trees  p50

definition of the product of two binary trees in the Loday-Ronco algebra   p51

Loday-Ronco product with Catalan alternative tableaux   p57

proof of the equivalence of the two products  p63

the ≠ product  for binary trees  p71

complements:

    2 talks by J.-C. Aval on Hopf algebra, alternative Catalan tableaux and Loday-Ronco algebra

   LR1.pdf            LR2.pdf

Ch5  Combinatorial theory of orthogonal polynomials and PASEP   

                              6 February 2013                   slides    (pdf  18,4 Mo  112p)

some trigonometry  p2

combinatorial interpreation of some orthogonal polynomials p10

formal orthogonal polynomials, definition, moments p16

Askey tableau p21

combinatorial proof of some identities  p26

Favard theorem p30

pavages  p32

moments and weigthed Motzkin paths  p37

examples: Tchebycheff polynomials I and II  p43

tridiagonal  matrices  p47

equivalence with analytic continued fractions  p49

Flajolet fundamental Lemma  p54

Laguerre  histories  p68

Hermite histories  p82

Charlier histories  p98

Sheffer orthogonal polynomials  p104

data structures in computer science  p109

some references  p112

                                8  February 2013                  slides      (version2, pdf  11,8 Mo  121p)

Hankel determinants: definition  p2

LGV  Lemma  p4

an example  p10

Hankel determinant of moments p14

PASEP and orthogonal polynomials p22

subdivided Laguerre histories  p28

contractions  p39

q-analog of histories: inversion number and major index of a permutation  p46

q-analog of Hermite histories,  q-Hermite (I)  p61

q-analog of Laguerre histories, q-Laguerre (I) and PASEP   p71

q-Hermite (II)  and  q-Laguerre (II)   p85

PASEP  and orthogonal polynomials  p100

Askey-Wilson integral  p113

some references  p119

Ch 6  Q-tableaux and planar automata

                       13  February 2013               slides     (Ch6a, version 17 Feb,   pdf  7,1 Mo  119p)

alternating sign matrices and a quadratic algebra  p3

the general theory:  complete Q-tableaux  p41

complement: proof of the proposition about «normal ordering» for a quadratic algebra Q  p47

Q-tableau: definition  p54

Q-tableaux: 4 examples  p57

planar automata: definition  p76

planar automata: examples  p81

the RSK planar automaton  p100

«figures» accepted by planar automata ?  p107

conclusion  p113

                                Ch 6b   The  XYZ  algebra  and  its  associated  Q-tableaux

                   15  February 2013            slides           (version 17 Feb,  pdf    7,9 Mo  103p)

the XYZ algebra  p6

B.A.BA  configurations  p8

alternating sign matrices  (as XYZ-tableaux)  p19

rhombus tilings  p33

plane  partitions  p45

dimer tilings on a square lattice  p49

Aztec tilings  p54

geometric interpretation of XYZ-tableaux  p62

non-intersecting paths  p68

bijection rhombus tilings --- non-intersecting paths  p72

bijection  plane partitions --- non-intersecting paths p77

osculating paths  p84

FPL fully packed loops  p89

some bijections  p103

                                      Ch 6c  complements 

                        15-18  February 2013             slides           (version 17 Feb,  pdf   4,6 Mo   48p)

symmetries for plane partitions  p3

TSSCPP, totaly symmetric sef-complementary plane partition  p12

The Razumov-Stroganov (ex-) conjecture  p20

open questions:  correlation in XXZ spin chains  p35

complement of a BABA configuration: the bijection ASM -- FPL p39

open questions: 8-vertex model  p47

Ch 7   Reverse Q-tableaux, reverse Q-algebra

and demultiplication of equations in quadratic algebra

                        18 February 2013                slides        (pdf    7,2 Mo    106p)

reverse  Q-tableaux  p2

reverse quadratic algebra and reverse planar automata  p8

tree-like  tableaux  p20

rewriting planar automata  p34

the RSK planar automaton p42

the reverse RSK planar automaton p51

the bilateral planar automaton  p59

demultiplication of the commutation relations in the quadratic algebra  UD:DU+I   p69

another demultiplication in the quadatic algebra UD:DU+I   p76

demultiplication in the XYZ algebra and  the ASM  algebra   p80

bijection ASM -- pair (P,Q)  p95

the philosophy of the cellular Ansatz  p96

the  (happy) end of the course  p105