Jérémie Bettinelli École polytechnique Laboratoire d'informatique (LIX) 91128 Palaiseau Cedex FRANCE E-mail : prenom « . » nom « at » normalesup « . » org Bureau : 2023 Téléphone : (+33) (0)1 77 57 80 61

Cette page est dédiée à quelques simulations informatiques réalisées avec MATLAB. Vous pouvez cliquer sur les images ou vidéos pour les voir en grand.

Arbre bien étiquetés

Via la bijection de Schaeffer, les cartes planaires sont codées par des arbres bien étiquetés. Il s'agit d'arbres plans dont les sommets portent des étiquettes entières, variant de -1, 0, ou 1 le long de chaque arête. Leur étude permet d'obtenir des résultats sur la limite d'échelle des cartes aléatoires.

Les images et vidéos suivantes représentent quelques arbres bien étiquetés. L'axe vertical donne la hauteur des sommets de l'arbre, un des axes horizontaux donne la valeur des étiquettes et le second axe horizontal n'est pas dans une échelle linéaire. Le nombre n au-dessus indique le nombre de demi-arêtes de l'arbre (donc deux fois le nombre d'arêtes).

n = 100

		n = 25 000

		n = 50 000

Les vues suivantes sont "de profil". On ne voit plus la structure d'arbre, on ne voit que l'étendue des valeurs prises par les étiquettes à chaque hauteur de l'arbre. Les dernières images pour n = 100 000 et n = 1 000 000 donnaient déjà une telle vue.

	n = 110 000	n = 1 000 000

Fonctions de contour

Il existe une façon naturelle de coder les arbres bien étiquetés à l'aide d'un couple de fonctions. On parcourt l'arbre dans le sens horaire en visitant chaque sommet (éventuellement plusieurs fois). La première fonction enregistre la hauteur du sommet visité, tandis que la seconde enregistre son étiquette. On peut ensuite, à l'aide de ces deux fonctions, retrouver l'arbre initial. Une fois le temps renormalisé par n, les hauteurs par n^1/2, et les étiquettes par n^1/4, un résultat classique montre que ce couple de fonctions tends en loi pour la topologie uniforme vers l'excursion brownienne normalisée et la tête du serpent brownien.

Les images suivantes présentent ce couple de fonctions : en rouge en haut, la fonction de hauteur, et en violet en bas, la fonction d'étiquettes.

	n = 110 000	n = 1 000 000

Le serpent brownien

Pour finir, au lieu de ne considérer que l'étiquette du sommet que l'on visite, on peut prendre en compte toutes les étiquettes de la lignée généalogique du sommet visité. Cela nous donne une famille de chemins. Le chemin correspondant à un sommet est de longueur la hauteur du sommet consideré, et il varie de -1, 0, ou 1 à chaque pas. Cet objet converge en loi vers le serpent brownien introduit par Le Gall. On retrouve la tête du serpent brownien en ne gardant que la valeur finale de chaque chemin. Il est aussi possible, à partir uniquement de la tête du serpent brownien, de retrouver l'intégralité du serpent.

L'image suivante montre un serpent discret. La partie ombragée au sol représente la fonction de hauteur de l'arbre associé, et l'on observe un chemin en coupant la surface à la bonne profondeur et en regardant la tranche du morceau coupé.

n = 100

Les images suivantes donnent une approximation de serpent brownien. La partie ombragée au sol représente l'excursion brownienne normalisée, et l'on observe un chemin en coupant la surface à la bonne profondeur et en regardant la tranche du morceau coupé. L'image de gauche permet de mieux percevoir le relief, tandis que l'image de droite fait mieux apparaître le caractère « touffu » de l'objet.