Courses  X.V.

 
 
The cellular Ansatz «Petite école de combinatoire» LaBRI, Bordeaux 2011/2012 L’ Ansatz cellulaire sous-titre: Physique combinatoire et algèbre quadratique: une approche cellulaire résumé: Dans un premier temps, l'Ansatz cellulaire est une méthodologie permettant, par une approche cellulaire sur un réseau carré, d'associer des objets combinatoires (les Q-tableaux) à certaines algèbres quadratiques Q définies par relations et générateurs. Cette notion est équivalente à la notion d'  "automate planaire" ou de "réécritures planaires". L'exemple de base est l'algèbre définie par la relation UD = DU + Id (ou algèbre de Weyl-Heisenberg, bien connue en physique). Les Q-tableaux associés sont les permutations. Un deuxième exemple est l'algèbre définie par la relation DE = qED + E + D qui est à la base de la résolution en physique des systèmes dynamiques du modèle du PASEP ("partially asymmetric exclusion process") avec le calcul des probabilités stationnaires. Des Q-tableaux associés ont fait récemment l'objet de nombreuses études combinatoires sous le nom de "tableaux alternatifs", "permutation tableaux" ou encore "tree-like tableaux". Une autre algèbre, ou algèbre du modèle "8-vertex" permet de retrouver les fameuses matrices à signes alternants, les partitions planes, les configurations de chemins ne se coupant pas ou encore des pavages sur réseaux planaires. Dans un deuxième temps, l'Ansatz cellulaire permet la construction "guidée" de bijections entre les Q-tableaux et d'autres objets combinatoires, dès que l'on a une "représentation" par opérateurs combinatoires de l'algèbre quadratique Q. L'exemple de base pour l'algèbre de Weyl-Heisenberg est la classique correspondance RSK (Robinson-Schensted-Knuth) entre permutations et paires de tableaux de Young. Pour l'algèbre du PASEP on obtient une bijection entre tableaux alternatifs et permutations. La théorie combinatoire des polynômes orthogonaux joue un rôle important, ainsi que la théorie des "histoires de fichiers" introduite  informatique pour l'analyse du cout intégré des structures de données. Nous terminerons par des extensions et problèmes ouverts, en particulier pour l'algèbre du modèle "8-vertex". 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. Chapitre 1 Q-tableaux and planar automata PEC1 (September 23, 2011, pdf 3,7 Mo) slides §1 Heisenberg operators U,D UD=DU+I normal ordering, planarization, example with permutations §2 The PASEP algebra DE=qED+E+D planarization, alternative tableaux PEC2 (September 30, 2011, pdf 3,5 Mo) slides The PASEP in physics, TASEP, stationary probabilities The matrix Ansatz §3 Alternating sign matrices (ASM) and a quadratic algebra ASM, enumeration, the ASM algebra, planarization conclusion: the idea of Q-tableaux PEC3 (October 7, 2011, pdf 2,2 Mo) slides §4 complete Q-tableaux definition, the general normal ordering lemma, proof §5 Q-tableaux defininition examples: permutations, Rothe diagram, PEC4 (October 14, 2011, pdf 3,9 Mo) slides examples of Q-tableaux: alternative tableau, ASM §6 Planar automaton definition, examples: surjective pistol and Genocchi numbers, directed animals, conclusion Chapitre 2 Q-tableaux and planar automata: extensions, examples, problems PEC5 (October 21, 2011, pdf 9,2 Mo) slides §1 The 8-vertex algebra XYZ-tableaux, inversions of ASM, B.A.BA configurations § 2 Tilings Rhombus tilings, plane partitions, dimers tiling on a square lattice, Aztec tilings §3 Geometric interpretation of XYZ-tableaux the 6- and 8-vertex model, non-intersections paths, bijections osculating paths, fully packed loops (FPL), some bijections 8-vertex model, XXZ chain model: problems PEC6 (November 4, 2011, pdf 2,5 Mo) slides §4 Reverse Q-tableaux tree-like tableaux §5 Reverse quadratic algebra, reverse planar automata PEC7 (November 18, 2011, pdf 4,4 Mo) slides §6 Permutation tableaux §7 Rewriting planar automata §8 PASEP and staircase tableaux conclusion, extensions, problems Chapitre 3 The algebra UD=DU+I and the RSK correspondence PEC8 (December 2, 2011, pdf 13,5 Mo) slides §1 Introduction. Schensted's insertions §2 A geometric version of RSK with light and shadow lines proof of the equivalence, RSK planar automata §3 Extensions oscillating tableaux, matrices: from RS to RSK PEC9 (December 9, 2011, pdf 8,1 Mo) slides §4 " Local RSK" or "growth diagrams" §5 Equivalence local RSK and geometric RSK §6 Representation of operators U,D operators on Young diagram (from S.Fomin), references §7 RSK planar automata conclusion: the philosophy of the cellular Ansatz PEC10 (May 4, 2012, pdf 2,5 Mo) slides §8 From a quadratic algebra Q to bijections for Q-tableaux formalisation of the cellular Ansatz from the RSK example Chapter 4 The PASEP algebra DE=qED+E+D and the bijection alternative tableaux -- permutations PEC11 (May 11, 2012, pdf 4,9 Mo) slides §1 Rappels: the cellular Ansatz §2 Combinatorial representation of the operators E and D §3 Laguerre histories The FV bijection, the FV bijection with operators the FV bijection with increasing binary trees, q-Laguerre, commutation diagrams §4 Quadratic algebra, operators, data structures and orthogonal polynomials PEC12 (May 25, 2012, pdf 4,8 Mo) slides §5 The "exchange-fusion" algorithm §6 The bijection Laguerre histories -- alternative tableaux from "local rules" §7 Proof of the equivalence of the two bijections the "exchange-deletion" algorithm, the inverse algorithm, proof opf equivalence, alternative "jeu de taquin" Chapter 5 Complements, further developments PEC13 (June 8, 2012, pdf 9,8 Mo) slides §1 Rappel: combinatorial theory of (formal) orthogonal polynomials definition, moments, Askey tableau, (formal) Favard theorem, moments and weighted Motzkin paths, tridiagonal matrices, equivalence with analytic continued fractions, the fundamental Flajolet Lemma §2 exemple: Hermite and Laguerre polynomials Hermite polynomials, q-analog of Hermite histories, Laguerres histories, subdivided Laguerrre histories PEC14 (June 15, 2012, pdf 9,6 Mo) slides §3 More on Laguerre histories vocabulary on permutations, enlarged and restricted Laguerre histories, bijection permutations -- subdivided Laguerre histories §4 Contraction of paths and histories, Dyck tableaux §5 q-analogs of histories inversion table, q-Hermite and q-Laguerre type I and II §6 Extensions PASEP and orthogonal polynomials, orthogonal Sheffer polynomials PEC15 (June22, 2012, pdf 8,5 Mo) slides §7 How to guess a representation of the quadratic algebra Q data structure histories in computer science, dictionary and the PASEP algebra, prioritu queue and the Heisenberg algebra §8 Demultiplication in quadratic algebra two examples with the Heisenberg algebra UD=DU+I §9 Demultiplication for the XYZ-algebra and ASM Petite_Ecole_2011_12_files/PEC1_23Sept11.pdfPetite_Ecole_2011_12_files/PEC2_30Sept11.pdfPetite_Ecole_2011_12_files/PEC3_7Oct11.pdfPetite_Ecole_2011_12_files/PEC4_14Oct11.pdfPetite_Ecole_2011_12_files/PEC5_21Oct11_v0.pdfPetite_Ecole_2011_12_files/PEC6_4Nov11.pdfPetite_Ecole_2011_12_files/PEC7_18Nov11.pdfPetite_Ecole_2011_12_files/PEC8_2Dec11.pdfPetite_Ecole_2011_12_files/PEC9_9Dec11.pdfPetite_Ecole_2011_12_files/PEC10_4Mai12.pdfPetite_Ecole_2011_12_files/PEC11_11Mai12web.pdfPetite_Ecole_2011_12_files/PEC12_25Mai12.pdfPetite_Ecole_2011_12_files/PEC13_8Juin12.pdfPetite_Ecole_2011_12_files/PEC14_15Juin12.pdfPetite_Ecole_2011_12_files/PEC15_22Juin12.pdfshapeimage_2_link_0shapeimage_2_link_1shapeimage_2_link_2shapeimage_2_link_3shapeimage_2_link_4shapeimage_2_link_5shapeimage_2_link_6shapeimage_2_link_7shapeimage_2_link_8shapeimage_2_link_9shapeimage_2_link_10shapeimage_2_link_11shapeimage_2_link_12shapeimage_2_link_13shapeimage_2_link_14