10 décembre 2012

1 commentaire — commenter cet article

À quoi ressemble un planisphère vraiment aléatoire ?

Nicolas Curien

Chercheur CNRS au LPMA (UMR 7599) (page web)

Une introduction illustrée à la théorie mathématique des cartes planaires aléatoires.

Cartes planaires.

Saisissez-vous d’une feuille de papier et d’un crayon. Sur la page blanche, placez quelques points (appelés sommets) et reliez-les par des routes (appelées arêtes) avec la condition que deux arêtes ne peuvent pas se croiser [1] et que les chemins, qui sont des successions d’arêtes, permettent d’aller de n’importe quel sommet à n’importe quel autre. Votre croquis peut également représenter un planisphère où des pays imaginaires (les faces) sont délimités par des frontières (les arêtes). Le concept mathématique correspondant à ce type de dessins est d’ailleurs nommé d’après cette analogie : vous venez de dessiner une carte planaire.

Fig. 1 Deux représentations de la même carte planaire.

En réalité, une même carte planaire correspond à plusieurs dessins différents : tout tracé qui peut être déformé (continûment) en votre croquis représente la même carte, voir Fig. 1 ci-dessus. Un peu comme si les frontières séparant les pays (les faces) étaient faites de caoutchouc déformable.

Deux résultats « enfantins ».

Les cartes planaires ont des propriétés fascinantes. Par exemple, dans votre carte, comptez le nombre de sommets, ajoutez-y le nombre de faces (y compris la face extérieure) et soustrayez le nombre d’arêtes. Vous devez obtenir $2$ indépendamment de la carte dessinée. Ce fait prouvé par Euler en 1758 constitue l’un des premiers résultats sur les cartes planaires. Donnons un autre théorème qui paraît enfantin : il est possible de colorier n’importe quelle carte planaire avec seulement $4$ couleurs (disons rouge, bleu, vert et jaune) de manière à ce que deux faces adjacentes (des pays limitrophes) aient des couleurs différentes.

Fig. 2 Quatre couleurs suffisent à colorier n’importe quelle carte. Remarquez que l’on peut colorier la face extérieure en bleu.

Malgré les apparences, ce théorème est très difficile à prouver et la [démonstration] originale d’Appel et Haken datant de 1976 est encore l’objet de débats car elle fait appel à l’ordinateur : comment prouver que le programme informatique ne comporte pas d’erreur et que l’ordinateur effectue bien les calculs demandés ? Les cartes planaires interviennent dans de nombreux domaines des mathématiques en particulier en combinatoire où elles sont encore aujourd’hui l’objet d’actives recherches.

Un modèle de géométrie aléatoire.

Dans certaines tentatives « d’unification » de la relativité générale et de la mécanique quantique, les physiciens théoriciens ont eu recours à une notion de « géométrie aléatoire planaire ». Ils ont proposé l’idée que les cartes planaires peuvent servir à construire un tel modèle. Expliquons ceci. L’ensemble des cartes [2] planaires à $n$ arêtes est un ensemble fini (ce n’est pas évident), plus précisément de cardinal [3] \[c_{n} = \frac{2\cdot 3^n}{(n+2)(n+1)} {2n \choose n}.\]
Pour $n\geq 1$, choisissez au hasard une carte planaire $ \mathsf{C}_n$ à $n$ arêtes uniformément parmi tous les $c_{n}$ choix possibles, c’est-à-dire que chaque carte à $n$ arêtes a la même probabilité d’être sélectionnée. Cette carte aléatoire $ \mathsf{C}_n$ va maintenant être considérée comme un modèle géométrique en la munissant de la distance de graphe : la distance entre deux sommets $u$ et $v$ de la carte est définie comme le plus petit nombre d’arêtes à traverser pour aller de $u$ à $v$. En d’autres termes, chaque arête est vue comme ayant longueur $1$.

Fig. 3 Deux cartes à $n$ arêtes avec diamètre $0$ (à gauche) et $n$ (à droite).

Le but est maintenant de comprendre les propriétés à grande échelle de notre espace métrique [4] aléatoire $ \mathsf{C}_n$ quand $n$ tend vers l’infini. Étudions par exemple son diamètre $\Delta_n$, c’est-à-dire la distance maximale entre deux sommets de la carte $ \mathsf{C}_n$. Bien entendu $ \Delta_n$ est une quantité aléatoire et peut varier en principe entre $0$ et $n$ (voir Fig. 3). Dans un article maintenant célèbre, Chassaing et Schaeffer [CS04] ont montré qu’avec une probabilité écrasante quand $n \to \infty$, la variable aléatoire $ \Delta_n$ est de l’ordre de $n^{1/4} = \sqrt{\sqrt{n}}$,
\[\begin{equation} \label{1/4} \Delta_{n} \ \ \approx \ \ n^{\color{red}1\color{red}/\color{red}4}. \end{equation}\]
L’exposant $1/4$ est surprenant et très différent du $1/2$ auquel on s’attend si l’on pense à des cartes « régulières » comme la grille du cahier d’écolier [5]. D’autres propriétés de ces espaces métriques aléatoires peuvent être étudiées, comme les géodésiques, c’est-à-dire les plus courts chemins ou « autoroutes ». En termes simples et forcément simplistes, la géométrie d’une carte planaire aléatoire est proche de celle d’une feuille de papier froissée ou d’une région montagneuse : les autoroutes passent toutes par un nombre restreint de plis ou vallées, voir Fig. 4.
Tous ces résultats suggèrent qu’il existe une « limite continue » une surface aléatoire qui serait obtenue (en un certain sens que nous ne préciserons pas) en divisant toutes les longueurs dans $ \mathsf{C}_{n}$ par $n^{1/4}$ et en faisant tendre $n$ vers l’infini. Ce résultat remarquable fut prouvé [6] l’année dernière indépendamment par Jean-François Le Gall [LG11] et par Grégory Miermont [Mie11]. L’espace aléatoire limite est appelé la Carte Brownienne : c’est une surface continue aléatoire qui peut être vue comme la sphère de dimension $2$ munie d’une métrique aléatoire qui la transforme en un objet fractal de dimension $4$ ! Cliquez [ici] pour une représentation en 3D d’une approximation de cette surface aléatoire.

Fig. 4 Une représentation dans $ \mathbb{R}^3$ d’une grande carte aléatoire : une géométrie hérissée de piques !

Les cartes sont des arbres étiquetés.

Terminons cet article par la présentation d’une bijection combinatoire magique appelée Cori-Vauquelin-Schaeffer du nom de ses inventeurs [CV81] [Sch98] et qui est l’outil principal pour étudier les cartes planaires aléatoires.
Commençons par remarquer qu’à toute carte planaire à $n$ arêtes on peut associer une carte planaire à $n$ faces où toutes les faces ont quatre côtés [7], on parlera de quadrangulation, voir Fig. 5 et 8. La méthode est simple : dans chaque face de la carte planaire initiale, placez un sommet blanc que vous reliez à tous les sommets adjacents de la face. Après avoir effacé les arêtes initiales vous obtenez une quadrangulation où chaque face correspond à une arête de la carte initiale, voir Fig. 5.

Fig. 5 Dualité entre cartes à $n$ (lignes pleines) arêtes et quadrangulations à $n$ faces (lignes pointillées).

Avec ce procédé [8] on transforme n’importe quelle carte à $n$ arêtes en une quadrangulation à $n$ faces. Nous allons maintenant voir que les quadrangulations ne sont rien d’autre que des arbres étiquetés. Nous appelerons arbre (pour arbre orienté enraciné), un arbre généalogique avec un ancêtre, puis les enfants de cet ancêtre ordonnés (du benjamin vers l’aîné, de gauche à droite) et ainsi de suite. Un étiquetage de cet arbre est une fonction sur les sommets de l’arbre à valeurs dans $ \mathbb{Z}$ tel que l’étiquette de l’ancêtre est $0$ et tel que deux sommets voisins (l’un est le père de l’autre) ont des étiquettes qui diffèrent de $1$ de $0$ ou de $-1$, voir Fig. 6.

Fig. 6 Un arbre étiqueté, son contour et ses coins.

Derrière un arbre étiqueté à $n$ arêtes comme celui présenté dans la Fig. 6 se cache une quadrangulation à $n$ faces. La voyez-vous ? Pour la découvrir nous allons démarrer de la racine de l’arbre et faire son contour dans le sens des aiguilles d’une montre, c’est-à-dire tourner autour de l’arbre en imaginant que c’est un mur, voir Fig. 6 droite. Lors de ce contour, tous les sommets de l’arbre sont visités et certains sommets sont rencontrés plus d’une fois, chacune de ces rencontres correspond à un coin différent du sommet (coin rouge dans la Fig. 6 droite). Le procédé pour construire la quadrangulation cachée est le suivant : chaque coin d’étiquette $i$ est relié au prochain coin dans le contour d’étiquette $i-1$. Mais il y a un hic : que faire avec les coins d’étiquette minimale ($-2$ dans notre exemple) puisqu’il n’y a pas de coin d’étiquette strictement inférieure dans la suite du contour ? Solution : tous ces coins sont reliés à un sommet fictif $\partial$ placé en dehors de l’arbre.

Fig. 7 Les trois premières arêtes dans la construction de Schaeffer. La troisième nécessite l’introduction du sommet $\partial$.

Il est alors possible de vérifier que toutes les arêtes peuvent être tracées sans croisement et qu’après effacement de l’arbre initial le dessin obtenu... est une quadrangulation ! Il est aussi possible d’inverser le procédé et de transformer toute quadrangulation en un arbre étiqueté par le truchement d’une construction aussi magique que la précédente, voir [CS04].

Fig. 8 La quadrangulation finale avec et sans son arbre étiqueté.

Grâce à cette construction l’étude des cartes planaires aléatoires est alors « ramenée » à l’étude des arbres étiquetés aléatoires qui sont beaucoup plus simples à comprendre. On peut vérifier par exemple (faites-le sur la Fig. 8) que si $v$ est un sommet de l’arbre d’étiquette $\ell(v)$ alors la distance de graphe entre $v$ et le sommet « spécial » $ \partial$ dans la quadrangulation associée est égale à \[ \mathrm{d_{gr}}(v, \partial) \ \ = \ \ \ell(v) - \min \ell +1, \] où $\min_{} \ell$ est la plus petite étiquette de l’arbre. Ainsi les distances dans la quadrangulation sont intimement liées aux étiquettes de l’arbre associé. Cela permet de comprendre l’apparition du mystérieux facteur $n^{1/4}$ dans la formule $\eqref{1/4}$ : un arbre aléatoire choisi uniformément parmi les arbres à $n$ arêtes a typiquement des branches de longueur d’ordre $\sqrt{n}$. Puisque le long de chaque branche de cet arbre les étiquettes évoluent comme des marches aléatoires, elles atteignent donc des valeurs d’ordre $\sqrt{\sqrt{n}} = n^{1/4}$ ... ! Pour plus de détails sur le sujet nous renvoyons le lecteur au cours de Jean-François Le Gall et Grégory Miermont [LGM10].

P.S. :

Merci à François Béguin pour des commentaires avisés sur une première version de cet article. Merci également à Bruno Duschene, « TheBarber », Abderezak Ould Houcine et Christophe Boilley pour leurs relectures attentives.

Notes

[1Interdiction de construire des ponts !

[2Pour les puristes, nous considérerons à partir de maintenant les cartes comme enracinées, c’est-à-dire munies d’une arête orientée distinguée.

[3Rappelons que ${2n \choose n} = \frac{(2n)!}{n! n!} $ où $n! =1 \times 2 \times 3 \times ... \times n$.

[4C’est-à-dire un espace muni d’une distance.

[5Une grille carrée de taille $\sqrt{n}$ par $\sqrt{n}$ qui contiendrait $\approx n$ carrés et dans laquelle les distances (par exemple entre le coin inférieur gauche et supérieur droit) sont d’ordre $\sqrt{n}=n^{\color{red}1\color{red}/\color{red}2}$.

[6Pour une classe particulière de cartes planaires où toutes les faces sont des quadrangles, voir plus loin.

[7Chaque face est bordée par $4$ arêtes avec la convention suivante : si une arête est complètement incluse dans une face, elle compte double.

[8Procédé réversible si les cartes considérées sont enracinées.

Affiliation de l'auteur

Nicolas Curien : CNRS, Université Paris 6

Commentaires sur l'article

Pour citer cet article : Nicolas Curien, « À quoi ressemble un planisphère vraiment aléatoire ? »Images des Mathématiques, CNRS, 2012.

En ligne, URL : http://images.math.cnrs.fr/A-quoi-ressemble-un-planisphere.html

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :