2010 – 2011

Le séminaire a eu lieu les jeudis 7 octobre 2010, 2 décembre 2010, 3 janvier 2011, 7 avril 2011 et 26 mai 2011.

7 octobre 2010 

Quantifier la distribution de la hauteur d'un arbre est un problème de base partagé par les probabilistes et les combinatoriciens. D'un point de vue probabiliste, d'intéressantes connexions ont été établies avec le mouvement Brownien, les processus de branchement, et le modèle dit "de l'arbre continu" (CRT). L'objectif de cet exposé est une présentation synthétique de méthodes asymptotiques fondées sur l'analyse complexe et la combinatoire analytique: ces méthodes analytiques ont en effet permis d'obtenir une caractérisation très complète de la hauteur dans les principales familles d'arbres combinatoires (arbres de Catalan, binaires ou généraux ; arbres d'Otter). Lois limites locales ou centrales, convergence de moments et bornes de grandes déviations en résultent. On croisera au passage l'ensemble de Mandelbrot, les transformations de fonctions elliptiques théta, ainsi que la théorie élémentaire de l'itération analytique. [Présentation fondée notamment sur des travaux commun avec Broutin, Gao, Odlyzko, et Richmond.]
  • Philippe Biane (IGM-MLV),
    Polynômes orthogonaux et équations de Painlevé discrètes.
    Transparents. Synthèse. 
Les polynômes orthogonaux ont de riches propriétés combinatoires. Dans cet exposé je considérerai des polynômes orthogonaux sur le cercle unité, proches de ceux d'Askey-Wilson mais qui ne s'y ramènent pas. Les coefficients de leurs relations de récurrence ne sont pas donnés par une formule explicite mais sont déterminés par une autre relation de récurrence qui est en fait une équation de Painlevé discrète (j'expliquerai dans l'exposé ce que sont les équations de Painlevé). Cette équation de récurrence provient d'une structure géométrique remarquable qui fait intervenir les systèmes de racines affines $D_5$ et $A_3$, plongés de façon orthogonale dans $E_8$.
  • Mireille Bousquet-Mélou (Labri-Bordeaux),
    Sur les chemins auto-évitants.
    Transparents. 
Un chemin auto-évitant sur un réseau de dimension d est une marche qui ne visite jamais deux fois le même sommet. Ces objets naturels sont étudiés en combinatoire, en probabilités, et en physique statistique, mais leurs propriétés sont mal connues, surtout en petite dimension $(d=2,3)$. On présentera d'abord une courte synthèse des résultats et conjectures existants — remarquables pour la dimension 2. Puis on discutera de la recherche de familles exactement résolubles de tels chemins.

2 décembre 2010

  • François Bergeron (UQAM Montréal),
    Combinatoire de Catalan et espaces de polynômes harmoniques diagonaux.
    Transparents. Synthèse. 
Au cours des vingt dernières années, l'étude des espaces de polynômes harmoniques diagonaux a mené à une étude fine de la combinatoire des fonctions de stationnement (parking functions), et de paramètres sur celles-ci. Nous allons présenter certains de ces développements, avec des extensions qui font intervenir l'ordre de Tamari ainsi que ses extensions aux cas de chemins de Dyck généralisés. Nous conclurons en abordant de nouveaux problèmes combinatoires soulevés par cette étude.
  • Andrea Sportiello (Université de Milan et LIPN),
    Autour de la conjecture de Razumov-Stroganov.
    Transparents. Synthèse. 
Il existe trois familles de structures aléatoires, issues de la combinatoire énumerative et de la physique statistique : (1) Un modèle physique concernant la chaine de spins quantiques de type XXZ qui peut être formulée en termes de "boucles denses de type O(1)", sur un cylindre semi-infini. (2) Des objets combinatoires appelés Matrices à Signes Alternant (MSA), introduits par Robbins et Rumsey il y a 25 ans, qui peuvent être interpretés comme des configurations du modèle à six sommets, un modèle intégrable dans le sens de Baxter. (3) Un modèle de pavages d'un hexagone par des losanges, pavages qui peuvent également être interpretés comme des surfaces aléatoires en trois dimensions de type Partitions Planes (plus precisement, Partitions Planes Totalement Symétriques Auto-Complémentaires, PPTSAC).

Ces modèles s'énumèrent de la même manière (autrement dit, normalisation de la fonction d'onde sur la chaine XXZ longueur n = #MSA sur un carré de taille n = #PPTSAC sur un hexagone de taille 2n), de plus certains dénombrements plus raffinés sont les mêmes. En particulier, les deux premiers modèles ont des dénombrements identiques quand on se restreint aux "classes de topologie" (structures de couplage), qui sont non-locales, et en nombre $\exp(~4^n)$. Cette propriété a été conjecturée par Razumov et Stroganov en 2001, et prouvée par Cantini et moi-même, en 2010. Deux ingrédients de la preuve sont l'analyse d'une chaîne de Markov à opérateurs dans une algèbre de Temperley-Lieb associée au modèle de boucles denses, et la généralisation d'une certaine bijection naturelle sur l'ensemble des MSA introduite par Wieland et appelée "gyration".
L'exploration d'un chemin permet d'en donner un codage par un mot. L'exploration d'un arbre plan permet d'en donner un codage par un chemin. L'exploration d'une carte planaire permet d'en donner un codage par un arbre.

Ces assertions couvrent plusieurs énoncés précis de bijections entre différentes familles de chemins, d'arbres et de cartes, donc certaines obtenues encore tout récemment. Ces bijections ont de multiples applications, de la génération aléatoire au dessin automatique de graphes, en passant par la conception de structures de données compactes et l'étude des distances dans les grandes cartes aléatoires.

Mon but sera cependant plutôt de montrer l'élégance de ces résultats et des formules qui en résultent. Ceci sera l'occasion de vanter quelques outils bijectifs classiques: mots bien parenthésés, lemme cyclique, parcours en largeur et en profondeur, orientations minimales.

3 janvier 2011

  • Brigitte Vallée (GREYC-Caen),
    Théorie de l’information : Sources, Séries de Dirichlet, Analyse réaliste d’algorithmes.
    Transparents. 
En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Une clé, comme un mot, est une suite finie de symboles sur un alphabet. En algorithmique du texte, on étudie les propriétés fines des mots, et leur influence sur l'efficacité des algorithmes. C'est alors le nombre de comparaisons entre symboles qui va être la bonne mesure de coût. La manière dont les mots sont produits, les corrélations possibles entre symboles vont jouer alors un rôle essentiel; cependant, on se limite le plus souvent à des modèles simples, qui conduisent donc à des analyses peu réalistes. En algorithmique générale, la structure d'une clé est "transparente" et n'est pas prise en compte dans l'analyse : on compte pour un coût unitaire la comparaison entre deux clés. Cela conduit à des énoncés classique du type "la complexité moyenne de l'algorithme QuickSort est en O($n \log n$), celle de QuickSelect est en O($n$)". Cette mesure de coût est souvent peu réaliste, dès que les clés ont une structure complexe, dans le contexte des bases de données ou de la langue naturelle, par exemple. 

Pour effectuer une analyse plus réaliste, il faut d'abord prendre en compte la structure d'une clé, et la considérer vraiment comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors ... de l'algorithmique du texte. Ensuite, il faut définir un cadre adapté qui modélise la "source"qui "produit" le mot. Notre programme, décrit dans l'exposé, est donc le suivant (a) Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques. (b) Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet. (c) Utiliser les propriétés analytiques des séries génératrices des sources pour obtenir l'asymptotique des principales structures ou algorithmes construits sur les mots de la source : arbres binaires de recherche, arbres digitaux, et algorithmes QuickSort et QuickSelect.
  • Arun Ram (Univ. Melbourne-Australie),
    Polytopes, shuffles, quivers and flags.
    Transparents. 
There are two geometries that show remarkable similarities: that of quiver varieties and that of affine flag varieties. By work of Braverman-Gaitsgory and Gaussent-Littelmann and Kashiwara-Saito and Kamnitzer-Baumann one sees the crystals, in the sense of Kashiwara, coming from both quivers and flags. In the picture of Leclerc-Geiss-Schroer one sees how elements of the shuffle algebra come from quiver varieties. In joint work with A. Ghitza and S. Kannan we are seeing shuffle elements coming from affine flag varieties. Following my recent joint work Ghitza and S. Kannan, I will explain the purely combinatorial approach for seeing the moment polytopes and the shuffle elements.
  • Robert Cori (Labri-Bordeaux),
    Développements récents dans le modèle combinatoire du tas de sable sur un graphe.
    Transparents. Synthèse. 
Dans le modèle combinatoire du tas de sable on affecte à chaque sommet d'un graphe un entier positif ou nul censé représenter un nombre de grains situés sur le sommet en question. Une règle d'éboulement permet de faire passer des grains d'un sommet à ses voisins. Deux généralisations du modèle avec l'affectation d'entiers pouvant être négatifs ont été considérées par différents auteurs. La première peut être interprétée par des particules et anti-particules qui se détruisent mutuellement lors d'un éboulement. La seconde comme des soldes de comptes en banque qui peuvent être redistribués aux voisins ou bien faire l'objet d'un versement collectif. Il sera question dans cet exposé de résultats récents obtenus dans le cadre de ces deux modèles et en particulier d'un article de M. Baker et S. Norine dans Advances in Mathematics datant de 2007 et intitulé Riemann-Roch and Abel-Jacobi theory on a finite graph qui a particulièrement interessé l'orateur.

7 avril 2011

  • Philippe Di Francesco (IPhT-CEA Saclay),
    The proof of the ASM-DPP conjecture.
    Transparents. 
We prove a 28-years old conjecture by Mills-Robbins-Rumsey (1983) relating some refined enumerations of Alternating Sign Matrices (ASM) and Descending Plane Partitions (DPP). These are performed by reformulating the enumeration problems in terms of statistical models, namely the 6Vertex model for ASMs and Rhombus tilings/Dimers or Lattice Paths for DPPs. The conjecture then boils down to a determinant identity, which is proved by use of generating function techniques. Remarkably, the main player is the transfer matrix for discrete 1+1-dimensional Lorentzian quantum gravity, which generates random Lorentzian triangulations of the two-dimensional space-time. (This is joint work with Roger Behrend and Paul Zinn-Justin).
Dans cet exposé je présenterai les automates en tant qu'objets combinatoires. On s'intéressera à des problèmes d'énumération et de génération aléatoire, en utilisant des techniques de combinatoire analytique et de combinatoire bijective. La motivation de ces travaux est de faire de l'analyse d'algorithmes en théorie des langages, mais je me concen\ trerai dans cet exposé sur la combinatoire qui est derrière ces objets. Il s'agit de différents travaux réalisés avec F. Bassino, J. David, D. Gouyou-Beauchamps, P.-C. Héam, A. Martino, E. Ventura, S. Schmitz et P. Weil.
  • Florent Hivert (LITIS-Rouen),
    Autour de la Formule des équerres pour les arbres.
    Transparents. 
Soit $T$ un arbre binaire à $n$ noeuds. On s'intéresse au nombre d'étiquetages décroissants de $T$ par les entiers de 1 à $n$, chaque entier apparaissant une fois et une seule. La formule des équerres pour les arbres, exprime le nombre de ces étiquetages comme le quotient de $n!$ par le produit du nombre de noeud de chacun des sous-arbres. Il est frappant de remarquer que cette formule très simple à prouver par récurrence admet un grand nombre de raffinement et de multiples facettes. Nous présenterons les liens avec la résolution de certaines équations fonctionnelles, la combinatoire du produit de mélange et le calcul dendriforme ainsi que quelques identités sur les fractions rationnelles.

26 mai 2011

  • Pierre Cartier (IHES),
    Algèbres de Hopf combinatoires.
    Transparents. 
Les opérations de contraction et d'insertion dans les graphes — selon la prédiction de G.-C. Rota — conduisent à des algèbres de Hopf. On décrira deux exemples principaux, liés aux diagrammes de Feynman et à la monodromie d'équations différentielles. On explicitera les théorèmes de structure sous-jacents.
  • Xavier Viennot (Labri-Bordeaux),
    Algèbres quadratiques, Robinson-Schensted, matrices à signes alternants et au-delà.
    Transparents. 
La plus simple algèbre de Weyl-Heisenberg, bien connue en physique, est définie par les opérateurs $U$ et $D$ (création et suppression de particules) avec la relation de commutation $UD=DU+Id$. Un des derniers articles de P. Flajolet (avec P. Blasiak) donne des modèles combinatoires pour la réduction sous "forme normale" de polynômes dans une telle algèbre quadratique. Nous introduisons un autre modèle combinatoire, initialisé par S. Fomin, et permettant de retrouver à partir de cette algèbre quadratique, la très classique correspondance de Robinson-Schensted entre les permutations et les paires de tableaux de Young de même forme. Partant de cet exemple fondamental, nous esquisserons une théorie générale, l' "Ansatz cellulaire", permettant d'associer à certaines algèbres quadratiques Q des objets combinatoires (les Q-tableaux) , ainsi que des constructions "semi-automatiques" de bijections, comprenant en particulier la correspondance de Robinson-Schensted et les célèbres matrices à signes alternants. Une approche équivalente est basée sur la nouvelle notion d'"automate planaire".
Depuis une vingtaine d'années, le calcul formel a beaucoup progressé dans l'algorithmisation des mathématiques. En particulier, quelques idées simples mais fécondes permettent maintenant de calculer automatiquement des sommes ou des intégrales de fonctions très diverses. Nous montrerons ces idées ainsi que des progrès récents qui permettent encore d'élargir la classe de fonctions manipulables algorithmiquement.