Laboratoire d'informatique de l'École polytechnique

Séminaire par Christina Goldschmidt (Oxford): «Se garer sur un arbre»

Speaker: Christina Goldschmidt (Oxford)
Location: Salle Philippe Flajolet, bâtiment Alan Turing
Date: Mer. 23 nov. 2016, 11h00-12h00

Résumé : Le but de cet exposé est l’étude d’une extension des fonctions de parking, introduite par Lackner et Panholzer. Supposons d’abord que l’on prend un arbre enraciné aléatoire uniforme avec étiquettes dans [n] := {1, 2, ..., n} et arêtes orientés vers la racine. Chaque noeud de l’arbre a la place pour une voiture. Un nombre m ≤ n de voitures arrivent, une par une, et la voiture i souhaite se garer au noeud Si, où S1, S2, ..., Sm sont des variables aléatoires uniformes dans [n]. Si une voiture souhaite se garer à une place déjà occupée, alors elle suit l’unique chemin orienté vers la racine jusqu’au premier moment où elle rencontre une place libre (dans ce cas elle s’y gare) ; si elle n’en trouve pas, elle quitte l’arbre. Soit An, m l’événement que toutes les voitures trouvent des places dans l’arbre. Lackner et Panholzer ont démontré (en utilisant des méthodes de la combinatoire analytique) qu’il existe une transition de phase dans ce modèle. Soit m = [αn] pour α ∈ (0, 1). Alors si α ≤ 1/2 on a $P(A_{n,m}) = \frac{\sqrt{1-2\alpha}}{1-\alpha}$, tandis que si α > 1/2 on a P(An, m) → 0. (En fait, ils démontrent des comportements asymptotiques bien plus fins en n pour α ≤ 1/2). Dans cet exposé, je donnerai une explication probabiliste de ce phénomène, et une preuve alternative en utilisant la méthode “objectif” d’Aldous et Steele. S’il y a assez de temps à la fin, je discuterai quelques généralisations. Travail en commun avec Michał Przykucki (Oxford).