Programme du Groupe de
travail
Arbres et Chemins
LaBRI, Bordeaux, 25-26 novembre 2004
Retour à la page principale.
Jeudi 25 novembre (après-midi)
- 14h00-15h00 : Jérémie Bouttier (CEA Saclay / Universiteit van Amsterdam)
Des cartes planaires eulériennes aux arbres étiquetés : les mobiles
Résumé : L'énumération bijective de familles de cartes est un
thème ayant connu de multiples développements récents. On considère ici le
problème très général du comptage des cartes planaires biparties en
fonction des nombres de sommets de chaque degré et couleur : la méthode
dite de la conjugaison d'arbres y a été adaptée avec succès par
Bousquet-Mélou et Schaeffer. Nous présentons une autre construction, duale
(c'est-à-dire portant plutôt sur les cartes planaires eulériennes avec
contraintes sur les degrés des faces), généralisant la bijection de
Schaeffer entre quadrangulations et arbres bien étiquetés. Les objets
ainsi associés aux cartes eulériennes sont des arbres dont certains
sommets et arêtes sont étiquetés par des entiers selon des règles
précises. Nous baptisons ces objets les mobiles.
- 15h00 - 15h30 : Pause café
- 15hh30 - 16h30 : Elahe Zohoorian-Azad (Institut Elie Cartan, Nancy)
Loi limite pour la taille du facteur droit standard d'un mot de Lyndon au hasard.
Résumé : Considérons l'ensemble des mots finis sur un alphabet totalement
ordonné à q lettres. On démontre que la distribution de la
longueur du facteur droit standard d'un mot de Lyndon aléatoire de
longueur n, divisé par n, converge vers:
μ(dx)=1/q δ1(dx) + (q-1)/q 1[0,1)(x)dx
quand n tend vers l'infini. La convergence des moments en découle.
- 16h30 - 17h00 : Pause café
- 17h00 - 18h00 : Gregory Miermont (Université Paris Sud)
p-arbres et leurs limites continues.
Résumé : Un p-arbre est une généralisation naturelle d'un arbre de Cayley
(étiqueté) enraciné, dépendant d'une mesure de probabilité p sur
{1,2,...,n}. Sous certaines hypothèses sur p, ces arbres convenablement
renormalisés convergent quand n tend vers l'infini vers une famille
d'objets limites appelés arbres continus aléatoires inhomogènes (ICRT),
paramétrisée par des suites θ de carré sommable. Sous certaines
hypothèses, nous déterminons les processus dits de contour et de largeur
de ces arbres, et nous obtenons un analogue d'un théorème de Ray-Knight
conditionné pour l'excursion brownienne, dû à Jeulin et Yor.
Vendredi 26 novembre (matin)
- 9h30 - 10h30 : Luc Devroye (Université Mc-Gill / Université de Francfort)
La hauteur pondérée des arbres aléatoires
Résumé : En associant aux arêtes d'un arbre
des vecteurs aléatoires, on peut obtenir,
en un seul coup, la hauteur de plusieurs modèles
d'arborescences aléatoires. Nous utilisons les
propriétés des fonctions de Cramer
multidimensionnelles pour prouver ce résultat.
(Travail en collaboration avec Nicolas Broutin.)
- 10h30 - 11h00 : Pause café
- 11h00 - 12h00 : Olivier Bernardi (LaBRI, Bordeaux)
Sur les triangulations planaires de haut degré
Résumé : On considère un problème d'énumération de cartes planaires. Plus
précisément on s'intéresse au comptage de familles de triangulations
dont le degré des sommets est supérieur à une certaine valeur. Ce type
de problème, concernant des familles de cartes contraintes par des
conditions de degré portant simultanément sur les faces et les
sommets, met souvent en défaut les techniques usuelles d'énumération
des cartes.
L'approche choisie ici est intrinsèquement mécanique. Elle consiste
à
décomposer les cartes récursivement par suppression de la racine. Ces
décompositions se traduisent en équations sur les séries génératrices
des familles de cartes considérées. La résolution des équations
obtenues utilise des techniques apparentées à la méthode du noyau.
Cette étude permet de prouver des résultats d'algébricité pour les
triangulations dont le degré des sommets est supérieur (strictement)
à une certaine valeur d = 2, 3, 4.
Ouèbemaster pour les journées
bordelaises: Nicolas Bonichon