Étude de la quadrangulation infinie uniforme

Cartes planaires

Les cartes sont des objets assez intuitifs, mais il importe de prendre quelques précautions pour en donner une définition rigoureuse. Ainsi, parmi les différents points de vue possibles, on peut définir les cartes de manière purement combinatoire par des classes de conjugaisons associées à certaines paires de permutations, ou encore de manière plus algébrique par des revêtements ramifiés de la sphère. Ces définitions ont l’avantage d’être compactes, mais elles nous seront peu utiles pour notre propos. En effet, ce manuscrit est consacré à l’étude de certains aspects métriques des cartes, difficilement reconnaissables dans des définitions formelles. De même, notre étude se limitera aux cartes planaires, et nous ne parlerons pas de cartes en genre quelconque. Nous pouvons cependant citer les ouvrages [LZ04, MT01] pour le lecteur voulant se renseigner sur ces aspects des cartes. Le point de vue que nous privilégions est le suivant : une carte planaire est le plongement propre d’un graphe connexe fini dans la sphère S2 , considéré à homéomorphisme conservant l’orientation près. Notons que le graphe sous-jacent d’une carte est seulement supposé connexe et fini ; il peut donc avoir des arêtes multiples et des boucles. Nous allons toujours considérer des cartes planaires enracinées, pour lesquelles une arête orientée appelée racine de la carte est distinguée.

Considérons une carte planaire m. Une face de m est une composante connexe de S2 \ m, et le degré de cette face est le nombre d’arêtes orientées de m que l’on rencontre en faisant le tour de son bord. Le fait de considérer les arêtes orientées dans la définition du degré d’une face est fondamental, et il arrive effectivement que des arêtes non-orientées soient comptées deux fois dans le degré d’une face . Parmi les sous-ensembles remarquables de cartes, une attention particulière est portée aux triangulations, dont toutes les faces sont de degré 3, ainsi qu’à leur généralisation, les p-angulations, dont les faces sont toutes de degré p.

Avant d’aller plus loin, nous pouvons tenter de retracer les grandes lignes de l’histoire de la théorie des cartes en mathématiques mais aussi en physique, afin de mieux comprendre l’interêt suscité par ce domaine de recherche. Les cartes planaires sont apparues en théorie des graphes, avec le théorème des quatre couleurs. C’est en effet en voulant démontrer ce théorème que Tutte, dans les années soixante, a véritablement fondé l’étude énumérative des cartes. Dans sa série de travaux [Tut62a, Tut62b, Tut62c, Tut63], il développe une méthode pour résoudre les équations satisfaites par les séries génératrices de certaines familles de cartes planaires. Cette méthode, baptisée méthode quadratique, continue encore à être fertile comme le prouvent les articles récents de Gao, Wanless et Wormald [GW02, GWW01]. Les travaux de Tutte ont aussi trouvé un écho important en mécanique statistique dans les années soixante dix grâce à leur liens avec les intégrales de matrices. Les premiers articles parus dans cette veine ont été publiés par t’Hooft [tH74] ainsi que par Brézin, Itzykson, Parisi et Zuber [BIPZ78]. Cela a donné naissance à de nombreux travaux en théorie des représentations et en géométrie algébrique comme on peut par exemple le voir avec le livre [LZ04].

L’intérêt des probabilistes pour les cartes est encore plus récent et prend sa substance dans la question suivante : à quoi ressemble une géométrie planaire typique ? Avant d’expliquer un peu plus en détail cette question qui commence l’article d’Angel et Schramm [AS03], nous devons dire que c’est encore une question qui trouve son origine dans la physique. Avec la théorie de la gravité quantique en 2 dimensions, les physiciens essayent de développer une théorie quantique de la gravité en généralisant à des surfaces le concept d’intégrale de Feynman sur les chemins. Là où l’intégrale de Feynman se fait par rapport à des mesures sur des chemins, l’équivalent en gravité quantique se fait par rapport à des mesures sur des surfaces. Ces mesures sont encore au pire mal définies, et au mieux mal comprises. Les cartes s’avèrent alors particulièrement utiles en tant que modèles simples de géométries sphériques. En effet, on peut toujours munir l’ensemble des sommets d’une carte de la distance de graphe dgr, et la carte est alors un espace métrique discret. Les cartes donnent alors un ensemble de modèles de géométries sphériques, et on peut étudier les mesures sur cet ensemble comme le suggère en particulier le livre [ADJ97]. La démarche est alors classique en théorie des probabilités : on fait grandir un objet combinatoire aléatoire tout en le changeant d’échelle pour trouver une convergence vers un objet aléatoire continu. L’exemple caractéristique de cette démarche est la construction du mouvement brownien plan, qui est la limite d’échelle de la marche aléatoire simple sur Z2 . La loi du mouvement brownien plan est donc en quelque sorte la «mesure uniforme sur les chemins continus du plan», mesure qui apparaît dans l’intégrale de Feynman.

Bijection de Schaeffer

Le fait que les nombres de Catalan apparaissent dans les formules d’énumération de cartes enracinées peut s’interpréter par l’existence de bijections entre les cartes et différentes sortes d’arbres. Cori et Vauquelin [CV81] sont les premiers à avoir fait un pas dans cette direction. Schaeffer a ensuite développé dans sa thèse [Sch98] toute une panoplie de bijections entre les cartes et les arbres. Nous allons décrire ici celle qui servira tout au long de ce document. Cette bijection, qui fait le lien entre les quadrangulations et les arbres bien étiquetés, est appellée bijection de Schaeffer. Comme souvent pour de telles bijections, un exemple sera le plus parlant. Prenons un arbre bien étiqueté θ = (τ, ℓ), de taille n et considérons un plongement de τ dans le plan. Les régions du plan délimitées par deux arêtes consécutives autour d’un sommet sont appelées des coins. La première étape consiste à numéroter ces coins par leur ordre d’apparition dans le contour horaire, en commençant par le coin racine. Notons c1, c2, . . . , ck la suite des coins de l’arbre dans cet ordre. Fixons un point du plan qui n’appartient pas à l’arbre, que nous appelons ∂, donnons-lui l’étiquette 0 et numérotons son coin c0. Pour chaque coin ci de l’arbre, on construit alors une arête avec les règles suivantes :
1. Si i = 1, on relie c1 à c0. Ceci donne une arête (∂, ∅), que nous orientons de ∂ vers∅.
2. Si l’étiquette du sommet correspondant à ci est l, on relie ci et le dernier coin d’étiquette l − 1 parmi c0, . . . , ci−1.

La bijection de Schaeffer s’est avérée remarquable d’efficacité dans l’étude métrique des cartes grâce à la propriété suivante : dans une carte, la distance de graphe entre un sommet quelconque v et le sommet racine ∂ correspond à l’étiquette ℓ(v) dans l’arbre associé. La connaissance des étiquettes d’un arbre donne donc beaucoup de renseignements sur les distances dans la carte associée. Il faut cependant souligner que les étiquettes de l’arbre ne portent pas toute l’information relative aux distances dans la carte : il ne suffit pas de connaitre l’étiquette de deux sommets pour en déduire leur distance dans la carte si aucun de ces sommets n’est le sommet racine ∂.

Avec cette métrique, toutes les quadrangulations finies sont des points isolés tandis que les quadrangulations infinies sont les points d’accumulation des quadrangulations finies. Sans rentrer dans les détails, il est assez intuitif de voir qu’avec cette définition, les quadrangulations infinies peuvent être interprétées comme les classes d’équivalence des plongements de graphes localement finis dans la sphère, à homéomorphisme conservant l’orientation près. Nous renvoyons le lecteur aux articles [AS03] et [BS01] pour une discussion plus précise sur ce point de vue qui comporte quelques pièges.

Bien que nous ayons détaillé uniquement le cas des quadrangulations, définir cette métrique sur d’autres classes de cartes comme les p-angulations ne pose pas de problème particulier. Les méthodes de travail sont alors similaires en tout point. Une métrique équivalente à dQ peut être définie facilement en considérant les arêtes de la carte plutôt que les faces dans la définition des boules BQ. La boule de rayon r d’une carte q serait alors l’union de ses arêtes ayant un sommet à distance strictement plus petite que r de la racine. Cette seconde métrique est cependant plus utile pour étudier des cartes pour lesquelles les faces n’ont pas de rôle particulier ou pour lesquelles le degré des sommets est important. C’est par exemple une métrique beaucoup plus naturelle pour étudier les cartes planaires sans contraintes qui peuvent avoir des faces de degré arbitraire, et donc contenant des sommets arbitrairement loin de la racine.

Quadrangulation infinie uniforme

Pour tout entier n notons νn la mesure de probabilité uniforme sur l’ensemble Qn des quadrangulations à n faces. On peut considérer ces mesures comme des mesures sur Q en donnant un poids nul au complémentaire de Qn. Dans [Kri06], Krikun prouve que cette suite de mesures converge faiblement vers une mesure de probabilité ν pour la topologie locale. Une quadrangulation de loi ν est appelée quadrangulation infinie uniforme.

Une des difficultés pour prouver la convergence (1.2) vient du fait que q⋆ \ BQ,r(q⋆) a plusieurs composantes connexes. Dans BQ,r(q ⋆ ), il y a donc plusieurs morceaux à ajouter pour obtenir une quadrangulation q. Cependant, avec une probabilité proche de 1, si q est une quadrangulation à n faces avec n très grand, une seule des composantes connexes de q\BQ,r(q) devient infinie. Ceci incite à considérer les enveloppes plutôt que les boules dans la convergence (1.2). C’est la démarche adoptée par Krikun [Kri06], qui définit l’enveloppe d’une quadrangulation de la manière suivante : si q ∈ Q et r > 0, l’enveloppe Bb Q,r(q) est le complémentaire dans q de la plus grande composante connexe de q \ BQ,r(q) (si il se trouve qu’il existe plusieurs composantes connexes de taille maximale, on en choisit une avec une règle déterministe). La Figure 1.7 donne un exemple d’enveloppe. Il est alors assez simple de voir que pour toute quadrangulation q et tout r > 0, l’enveloppe Bb Q,r(q) est une quadrangulation à bord simple dans le sens où une seule de ses faces n’est pas nécessairement de degré 4, et que cette face est bordée par un cycle d’arêtes sans pincements γr, joignant entre eux des sommets à distance r et r + 1 de la racine. Le lecteur peut se reporter à la Figure 1.7 pour une illustration de ceci.

Une des propriétés prouvées par Krikun dans [Kri06] qui retiendra notre attention un peu plus tard concerne la longeur des frontières des enveloppes. Plus précisément, il montre que si q est une quadrangulation de loi ν, alors pour tout r > 0, q \ BQ,r(q) a ν-presque sûrement une unique composante connexe infinie, et que la variable aléatoire |γr| /r2 converge en loi vers une loi gamma de paramètre 3/2. La figure 1.8 montre une vue de profil d’une quadrangulation et permet de mieux comprendre comment est placé le cycle γr au sein de celle-ci.

Comme nous l’avons dit, le cas des triangulations a été évoqué avant les travaux de Krikun par Angel et Schramm [AS03], qui introduisent une triangulation infinie uniforme du plan. La démonstration est similaire dans sa partie combinatoire, mais à la place de prouver que l’analogue de la mesure limite (1.3) est bien une mesure de probabilité, Angel et Schramm démontrent que la suite des mesures uniformes sur les triangulations de taille n est tendue en étudiant les degrés des sommets, ce qui permet aussi de conclure à la convergence de cette suite pour la topologie faible. Dans un deuxième article, Angel [Ang03] étudie certaines propriétés de cette loi. Il démontre en particulier grâce à une technique d’échantillonnage de la triangulation infinie uniforme que les boules de rayon r autour de la racine ont un volume qui croît presque surement comme r 4 à des termes logarithmiques près. Angel démontre de plus dans cetarticler qu’un analogue au cycle γr existe et qu’il est aussi de taille r 2 . Finalement, Angel étudie la percolation par sites sur une triangulation infinie uniforme et montre que la probabilité critique est presque surement 1/2. Angel étudie d’autres propriétés de la percolation par sites sur la triangulation infinie uniforme dans la prépublication [Ang05]. Avant de s’intéresser d’avantage aux quadrangulations, il semble utile de mentionner l’article de Benjamini et Schramm [BS01], qui démontre que les limites locales de graphes sont récurrentes si les graphes ont des sommets de degré uniformément bornés. Cette hypothèse fait bien sûr défaut dans le cas des limites de triangulations ou de quadrangulations, mais [AS03] donne des estimations des degrés des sommets pour les triangulations.

Table des matières

1 Introduction
1.1 Cartes planaires
1.2 Un peu de combinatoire
1.2.1 Arbres spatiaux
1.2.2 Énumération
1.2.3 Bijection de Schaeffer
1.3 Limites locales
1.3.1 Topologie sur les quadrangulations
1.3.2 Quadrangulation infinie uniforme
1.3.3 Arbre bien étiqueté infini uniforme
1.3.4 Une autre quadrangulation infinie uniforme
1.3.5 Les deux quadrangulations infinies uniformes ont la même loi
1.4 Limites d’échelle
1.4.1 Limite d’échelle d’arbres uniformes
1.4.2 Serpent brownien
1.4.3 Carte brownienne
1.4.4 Volume infini
1.5 Conclusion et perspectives
2 The two UIPQ have the same law
2.1 Introduction
2.2 Preliminaries
2.2.1 Spatial trees
2.2.2 Planar maps and quadrangulations .
2.2.3 Schaeffer’s correspondence
2.3 Uniform infinite quadrangulations
2.3.1 Direct approach
2.3.2 Indirect approach
2.4 Equality of the two uniform infinite quadrangulations
2.4.1 A property of Schaeffer’s correspondence
2.4.2 Asymptotic behavior of labels on the spine
2.4.3 Asymptotic properties of small labels
2.4.4 Proof of the main result
3 Scaling limits for the UIPQ
3.1 Introduction
3.2 Preliminaries
3.2.1 Trees and quadrangulations
3.2.2 Schaeffer’s correspondence
3.2.3 Uniform infinite well-labeled tree and quadrangulation
3.2.4 The Brownian snake
3.2.5 Convergence towards the Brownian snake
3.2.6 Bessel processes
3.3 Scaling limit of the uniform infinite well-labeled tree
3.3.1 The eternal conditioned Brownian snake
3.3.2 Convergence of the rescaled uniform infinite well-labeled tree
3.4 Some asymptotic properties of the uniform infinite quadrangulation
3.4.1 Profile
3.4.2 Points of escape to infinity
Conclusion

Télécharger le rapport complet