Séminaire interne du LIX
Année 00-01

• Distributions de valuations sur les arbres Michel Nguyen-The mercredi 25 octobre 2000, 10h30
  

  Étiquetons un arbre par des nombres aux feuilles, et des opérateurs aux nœuds internes. On peut faire correspondre à cet arbre étiqueté une expression arithmétique, dont on appellera le résultat la valuation de l'arbre. En généralisant un peu cette dernière notion, on peut considérer comme des valuations des paramètres classiques d'arbre comme la hauteur, l'ordre de Strahler, la longueur de cheminement.

  Dans le cadre des outils utilisés en analyse d'algorithmes, on étudiera la distribution limite de ces valuations pour des arbres de Catalan binaires dont la taille tend vers l'infini. On se cantonnera à dans des cas simples, avec toujours un jeu d'entiers fini pour les étiquettes aux feuilles :

  • Avec des opérateurs + et –, on reconnaît un jeu de pile ou face généralisé et on obtient une limite gaussienne.
  • Avec seulement l'opérateur –, on obtient également une limite gaussienne. Le paramètre obtenu correspond aux nombres de Narayana, intervenant notamment autour des arbres généraux et des chemins de Dyck. On exhibera les bijections combinatoires correspondantes.
  • Avec des opérateurs min et +, on obtient une distribution limite discrète. Avec des opérateurs max et +, on ne sait encore rien dire sur la distribution, même si des simulations suggèrent une limite gaussienne.

  On présentera ensuite la longueur de cheminement des arbres généraux, correspondant à une longueur de cheminement gauche chez les arbres binaires, et à l'aire sous les chemins de Dyck. Encore une fois on exhibera les bijections combinatoires correspondantes. Ce paramètre possède une distribution d'Airy, ce qu'on peut montrer par pompage de moments.

  Côté questions ouvertes, on exposera brièvement des outils probabilistes encore peu utilisés en analyse d'algorithmes, pouvant à terme aider à étudier d'autres valuations, typiquement des valuations linéaires comme v(feuille)=1, et v(T)=2v(T_gauche)+v(T_droit).

• Factorisations dans le groupe symétrique. Dominique Poulalhon vendredi 1^er décembre 2000, à 10H30

  On s'intéresse ici au nombre c_a1,...,am⁽ⁿ⁾ de factorisations d'une permutation circulaire en produit de m permutations de types cycliques donnés a₁,a₂,...,a_m. Cette étude est entre autre motivée par le fait qu'elles caractérisent les classes d'équivalence topologique de certaines fonctions méromorphes sur les surfaces de Riemann. Ceci induit une notion de genre des factorisations, genre qui s'avère être compltement déterminé par les types cycliques des facteurs, et qui a une influence déterminante sur la complexité du calcul de c_a1,...,am⁽ⁿ⁾.
  
  Après quelques rappels sur le cas simple où les facteurs sont des transpositions, qui permet de se convaincre du rôle prépondrant du paramètre genre, on présentera quelques cas particuliers connus. Puis on énoncera la formule obtenue pour le cas général avec Gilles Schaeffer, dans laquelle l'influence du genre est explicite. On donnera le schéma de la preuve ainsi que quelques corollaires, notamment des estimations asymptotiques à genre fixé.

Site maintenu par Arnaud Dartois et Clemence Magnien