10h30 et 14h: L'Ansatz cellulaire. Xavier Viennot, LaBRI, Bordeaux.
Le mot « Ansatz », venant de l'allemand et signifiant début, naissance ou racine, est un terme souvent utilisé par les physiciens comme une supposition qui marche (par exemple: Ansatz de Bethe, Ansatz matriciel). Dans ces deux exposés, je propose d'introduire une méthodologie permettant de construire « automatiquement » des bijections à partir de relations algébriques.
Jusqu'à présent, l'unique exemple était la classique correspondance RSK (Robinson-Schensted-Knuth) entre les permutations et les paires de tableaux de Young de même forme. Cette bijection peut se définir sous diverses formes équivalentes (insertion de Schensted, version géométrique par ombres et lumières, « jeu de taquin » de M. P. Schützenberger, etc.). S. Fomin en a donné une version « cellulaire » avec des règles locales sur une grille carrée pour ses « diagrammes de croissance ». L'idée est de définir deux opérateurs U et D sur les diagrammes de Ferrers vérifiant la relation de commutation UD=DU+Id. En « planarisant » les calculs dans l'algèbre engendrée par U et D par des réécritures sur une grille, et en « propageant » l'interprétation combinatoire de la relation de commutation attachée à chaque cellule de la grille, on peut retrouver la construction de Fomin et ainsi la correspondance RSK.
Après avoir rappelé cet exemple basique, j'en construirai un nouveau: une bijection entre les permutations et les tableaux appelés « alternatifs ». Ici la relation de commutation de départ est la relation DE=ED+E+D. Cette relation est à la base de la résolution (avec le « matrix Ansatz » de B. Derrida et ses coauteurs) du modèle appelé PASEP en physique des systèmes dynamiques (ou « partially asymmetric exclusion process »). Les tableaux alternatifs ont été introduit par l'orateur, comme une variante symétrisée plus agréable des « tableaux à permutations » introduits par A. Postnikov, E. Steingrimsson et L. Williams à partir de considérations de géométrie algébrique. Une représentation des opérateurs D et E est basée sur des recherches entreprises en informatique par J. Françon, P. Flajolet et J. Vuillemin il y a une trentaine d'années : la notion d'« histoires de structures de données » pour le calcul de coûts intégrés. Ici nous aurons besoin de la structure « dictionnaire »' et de la bijection FV entre permutations et « histoires de Laguerre ». L'Ansatz cellulaire permet alors de construire une bijection entre permutations et tableaux alternatifs, qui s'avère être équivalente à d'autres bijections dues à S. Corteel et P. Nadeau. Elle peut aussi se réinterpréter en termes de nouveaux objets combinatoires: les arbres binaires alternatifs et un « jeu de taquin » pour ces arbres binaires.
Enfin je terminerai par des perspectives alléchantes pour introduire cet Ansatz cellulaire vers le sujet chaud actuel (en combinatoire et en physique théorique) que constitue les matrices à signes alternants et la conjecture de Razumov-Stroganov pour les chaînes de spins quantiques. En somme un sous-titre de ces deux exposés dédiés aux soixante ans de mon ami Philippe pourrait être: