Jean-Francois Marckert (LAMA, Université de Versailles Saint-Quentin)

Arbres et Chemins.

Dans ce cours, on explore les relations liant les arbres simples de la combinatoire
(arbres binaires, planaires, étiquetés,...) et les"excursions" de marches aléatoires discrètes.

En effet, le parcours en largeur (ou en profondeur) permet d'associer à chaque arbre une
"excursion discrète". De nombreuses quantités liées aux arbres s'expriment alors comme
fonctionnelles simples des excursions. On obtient ainsi facilement les lois limites pour la
hauteur, la largeur, le profile des arbres (en utilisant le fait que les excursions discrètes
convergent vers l'excursion Brownienne).

Dans une seconde partie, on étudie les relations existant entre les différentes marches associées
aux arbres par le parcours en profondeur. On explique la raison de la "quasi-proportionnalité"
(observable par simulation) de ces marches. Ceci nous porte à montrer les points communs entre
les marches aléatoires et les marches conditionnées à etre des excursions et à étudier la suite des
records dans une marche aléatoire.