Télécharger le fichier original (Mémoire de fin d’études)
Arbres combinatoires
Arbres et sous-arbres
Définition 1.1 (Graphe). Un graphe T est la réunion disjointe
– d’un ensemble fini V appel´ ensemble des sommets et
– et d’un ensemble fini E d’éléments de la forme {v, v′} avec v, v′ ∈ V , appel´ ensemble d’aretes.
On dit que {v, v′} est une arete entre v et v′. Pour tout v ∈ V on note Ev l’ensemble des aretes contenant v. On appelle valence de v et note val(v) le cardinal de Ev.
Dans un graphe T , un chemin est une application injective t : [1, k] → T telle que pour j ∈ [1, k − 1],
– si t(j) est un sommet, alors t(j + 1) est une arete et t(j + 1) ∈ Et(i) et
– si t(j) est une arete, alors t(j + 1) est un sommet et t(j) ∈ Et(j+1).
On dit que ce chemin relie t(1) a` t(k). On confondra souvent par abus le chemin et son image.
Définition 1.2. Un graphe est dit connexe si toute paire de sommets distincts est reliée par un chemin.
Dans un graphe T , un cycle est une application injective t : Z/kZ → T telle que pour j ∈ [1, k − 1],
– si t(j) est un sommet, alors t(j + 1) est une arete et t(j + 1) ∈ Et(j) et
– si t(j) est une arete, alors t(j + 1) est un sommet et t(j) ∈ Et(j+1).
Définition 1.3 (Arbre). On appelle arbre tout graphe connexe et sans cycle.
FIGURE 1.1 – Un exemple d’arbre o`u les sommets sont schématiquement représentés par des points et les aretes entre sommets par des segments reliant les points correspondants.
La non existence de cycle est équivalente `a l’unicité des chemins reliant deux sommets fixés (voir par exemple [Di, Theorem 1.5.1]).
Définition 1.4. Si T est un arbre, on notera [v1, v2] l’unique chemin de T reliant v1 `a v2.
Le chemin t sera souvent noté aussi [t(1), t(3), t(5), . . . , t(k))] si t(1) et t(k) sont des sommets ou ]t(2), t(4), t(6), . . . , t(k − 1))[ si t(1) et t(k) sont des aretes.
Notons qu’un sous-graphe connexe d’un arbre est un graphe connexe et sans cycles. C’est donc un arbre. On parle alors de sous-arbre.
Dans un arbre, on appelle feuille tout sommet de valence 1. On appelle sommets internes les sommets de valence plus grande. On note IV l’ensemble des sommets internes (IV pour ”Internal Vertex”).
Topologie
Un graphe T sera muni de la topologie pour laquelle les fermés sont les sous-graphes de T .
Alors, les parties connexes T ′ de T sont celles telles que deux eléments distincts de T ′ peuvent toujours etre reliés par un chemin dont l’image est contenue dans T ′
Définition 1.5 (Composante connexe). Si T ′ est une partie d’un graphe T , on appelle composante connexe de T ′ toute partie connexe de T ′ maximale pour l’in-clusion.
Définition 1.6 (Branche). Si v est un sommet d’un arbre T et si ⋆ ∈ T − {v}, on appelle branche de ⋆ sur v, et on note Bv(⋆), la composante connexe de T − {v} qui contient ⋆.
Soit v ∈ V . Comme T est un arbre, pour tout elément ⋆ ∈ T −{v}, on trouve un unique chemin reliant v `a ⋆. Ce chemin, par définition, contient une unique arete e ∈ Ev. Cela montre que toute branche sur v est de la forme Bv(e) avec e ∈ Ev.
Une des principales caractéristiques des branches, c’est qu’elles contiennent au moins une feuille.
Lemme 1.7. Dans un arbre ayant au moins deux sommets, toute branche contient au moins une feuille.
Démonstration. Prenons un sommet v et une arete e ∈ Ev d’un arbre ayant au moins deux sommets. Si Bv(e) ne contenait pas de feuilles, on pourrait créer des chemins de longueur infinie. En effet, comme e est une arete, il y a nécessairement au moins un chemin reliant v a` un autre sommet v′(par le chemin (e)) et si ce sommet n’est pas une feuille, il possède une autre arete et on peut recommencer cette étape a` partir du sommet v′. La possibilité d’un chemin infini contredit la finitude du nombre de sommet d’un arbre.
Définition 1.8 (Anneau). Si v1 et v2 sont deux sommets internes de T , l’anneau A :=]]v1, v2[[ est l’intersection des deux branches Bv1 (v2) et Bv2 (v1). On définit aussi [[v1, v2]] := A.
Notons que A = A ∪ {v1, v2}. Plus généralement, on peut donner la définition suivante.
Définition 1.9. Si V ′ est un ensemble de sommets internes de T , on pose
]]V [[:= Bv(w) et [[V ]] := ]]V [[.
v,w∈V
v=w
Il se peut que ]]V [[ soit l’ensemble vide.
Caractéristique
Dans ce qui suit, nous introduisons un objet dit caractéristique qui est sem-blable a` la caractéristique d’Euler et nous servira quand nous aurons introduit les revetements d’arbres de sphères a` énoncer une formule de Riemann-Hurwitz.
Définition 1.10 (Caractéristique d’une partie). La caractéristique d’un sommet v d’un graphe T est χT (v) := 2 − val(v).
La caractéristique d’une partie T ′ de T est l’entier relatif
χT (T ′) := χT (v).
V ∩T′
v∈X
On notera simplement χ(T ′) lorsqu’il n’y aura pas d’ambiguité. Voir Figure 1.3 pour un exemple. Lemme 1.11. Pour tout arbre T , on a χT (T ) = 2.
Démonstration. Observons d’abord que dans un graphe, chaque sommet v est reli´ a` val(v) aretes et chaque arete est reliée `a 2 sommets. Par conséquent, val(v) = 2card(E). v∈V
Par ailleurs, dans un arbre, on a la relation cardV = cardE + 1 (voir par exemple [Di, Corollaire 1.5.3]). Par conséquent χT (T ) = 2 − val(v) = 2cardV − 2cardE = 2. v∈V
Rappelons que l’adhérence d’une partie est le plus petit fermé la contenant (cf figure 1.3).
Définition 1.12. Si T ′ ⊆ T , on note
– T ′ l’adhérence de T ′ dans T et
– ∂T T ′ := T ′ − T ′ la frontière de T ′ dans T .
Lemme 1.13. Si T ′ est un ouvert connexe de T , alors la frontière ∂T T ′ est l’en-semble des sommets v ∈ T − T ′ appartenant a` une arete de T ′. L’adhérence T ′ est un sous-arbre de T dont l’ensemble des sommets internes est IV ∩ T ′.
Démonstration. L’adhérence de T ′ est le plus petit sous-graphe de T contenant T ′. Il doit contenir tous les sommets v ∈ T appartenant a` une arete de T ′. Il n’y a pas besoin de rajouter d’autres sommets ou d’autres aretes pour obtenir un graphe. Cela montre que ∂T T ′ est l’ensemble des sommets v ∈ T − T ′ appartenant `a une arete de T ′.
L’adhérence d’un ouvert connexe est un sous-graphe connexe de T . C’est donc un sous-arbre de T . Les sommets de′ ′ ′ ∂T T ′ sont des feuilles de T sinon T ′ = T ′−∂T T ′ ne serait pas connexe. Comme T est ouvert, pour tout sommet v de T , on a Ev ⊂ T ′. Par conséquent la valence de v dans ′ T est la meme que celle de v dans ′ T . Cela montre que les sommets internes de T sont les sommets internes de T contenus dans T ′.
Lemme 1.14. Si T ′ est une partie non vide, ouverte et connexe de T , alors χT (T ′) = 2 − card∂T T ′.
Démonstration. Dans T ′, chaque sommet v de T ′ a valence val(v) et chaque sommet de ∂T T ′ a caractéristique 1. D’après le lemme 1.11, on a 2=χT( ′) = χT (v) + χT (v) = χT (T ′) + card∂T T ′. T v∈V ∩T ′ v∈∂T T ′
Lemme 1.15. Soit T’ une partie non vide, ouverte et connexe de T. On a
1. χT(T′) ≤ 2;
2. χT (T ′) = 2 ssi T ′ = T ;
3. χT (T ′) = 1 ssi T ′ est une branche de T .
4. χT (T ′) = 0 ssi T ′ est un anneau de T .
Démonstration. D’après le lemme précedent, χT (T ′) = 2 − card∂T T ′.
1) évident.
2) χT (T ′) = 2 ssi ∂T T ′ = ∅ ssi T ′ est `a la fois ouverte et fermée ssi T ′ = T .
3) Si T ′ est une branche sur un sommet v, alors ∂T T ′ = {v} et donc χT (T ′) = 1.
Réciproquement, si χT (T ′) = 1, alors ∂T T ′ contient un unique sommet v. On note e = {v, v′} l’arete de T ′ contenant v et on pose B := Bv(e). Comme T ′ est connexe, contenue dans T − {v} et contient e, on a T ′ ⊆ B. Etant donné que T ′ ∩ B = ∅, la branche B est la réunion disjointe des deux ouverts T ′ et B − T ′ = B − T ′. Comme B est connexe, on a B − T ′ = ∅ et donc B = T ′.
4) Si T ′ est un anneau ]]v1, v2[[, alors ∂T T ′ = {v1, v2} et donc χT (T ′) = 0. Réciproquement, si χT (T ′) = 0, alors ∂T T ′ contient exactement deux sommets v1 et v2. Les deux sommets v1 et v2 étant dans la frontière de T ′, on a forcément T ′ ⊆ A :=]]v1, v2[[. Comme précédemment,′ on peut alors écrire A = T ′ ⊔ (A − ′) et en déduire que A − T ′ = A − T = ∅. Par conséquent, A = T ′.
Application d’arbres combinatoires
Définition 1.16 (Application d’arbres). Une application F : T → T ′ est une application d’arbre si
– T et T ′ sont des arbres ;
– l’image d’un sommet est un sommet : F (V ) ⊆ V ′ ;
– l’image d’une arete entre deux sommets est l’arete entre les images de ces sommets : si {v, w} ∈ E, alors F ({v, w}) = {F (v), F (w)} ∈ E′.
Dans la suite de cette partie, F : T → T ′ est une application d’arbres. Observons que si U est un sous-graphe de T , alors F (U ) est un sous-graphe de T ′ et inversement, si U ′ est un sous-graphe de T ′, alors F −1(U ′) est un sous-graphe de T . En particulier, la préimage des fermés sont des fermés :
Proposition 1.17. Les applications d’arbres sont continues, et l’image d’un sous-arbre est un sous-arbre.
Démonstration. L’image d’un connexe par une application continue est un connexe.
FIGURE 1.4 – Un exemple d’application d’arbres : l’image d’un sommet est le sommet qui se trouve sur la meme ligne horizontale que celui-ci. Notons qu’il n’y a pas forcément surjectivit´ !
Arbres de sphères
Par la suite, X, Y et Z désigneront des ensembles finis contenant au moins 3 eléments.
Définition 1.18 ( Arbre marqué). Un arbre T marqué par X est un arbre dont les feuilles sont les eléments de X.
Un arbre marqué par X sera noté T X . Tout objet Obj reli´ `a T ⋆ sera noté Obj⋆.
Par exemple EY est l’ensemble des aretes de T Y .
Définition 1.19 (Arbre de sphères marqué). Un arbre de sphères T X (marqué par X) est la donnée de :
– un arbre combinatoire T X et
– pour tout sommet interne v de T X ,
– une sphère topologique Sv et
– une injection iv : Ev → Sv.
Lorsque l’arbre combinatoire ne possède qu’un unique sommet interne, on parle de sphère marquée (par X).
Pour e ∈ Ev, on dira que iv(e) est le point d’attache de e sur v. Pour simplifier les notations on notera souvent ev := iv(e) et meme parfois iv(v′) := ev si v′ ∈ Bv(e). On définit Xv := iv(Ev) l’ensemble des points d’attache sur la sphère Sv.
Remarque 1.20. Se donner les applications iv : Ev → Sv, c’est la meme chose que de se donner des applications av : X → Sv telles que av(x1) = av(x2) si et seulement x1 et x2 sont dans la meme branche sur v, c’est `a dire av(x) := iv(e) si x appartient a` Bv(e). On notera parfois T := (T, (av)v∈IV ).
Exemple. [Sphères marquées] Un arbre marqué par X ne possédant qu’un seul sommet interne est équivalent `a la donnée de ce sommet et d’une injection de X dans ce dernier. On parle alors de sphère marquée.
Revetement d’arbres de sphères
Définitions et degré
Un revetement d’arbre de sphères est l’enrichissement d’une application d’arbre combinatoire par la donnée en chaque sommet d’un revetement ramifié dont le lieu de ramification est contenu dans l’ensemble des points d’attache des aretes.
Définition 1.21 (Revetement). Un revetement d’arbre de sphères F : T Y → T Z est la donnée de :
– une application d’arbres F : T Y → T Z qui envoie feuilles sur feuilles et sommets internes sur sommets internes ( F (Y ) ⊆ Z et F (IV Y ) ⊆ IV Z ) et
– pour tous sommets internes v ∈ IV Y et w := F (v) ∈ IV Z , un revetement topologique ramifié fv : Sv → Sw tel que
1. la restriction fv : Sv − Yv → Sw − Zw est un revetement ;
2. fv ◦ iv = iw ◦ F sur Ev ;
3. si e = {v1, v2} ∈ EY est une arete entre deux sommets internes, alors degev1 fv1 = degev2 fv2 . Exemple. [Revetement de sphères] Un revetement d’arbre de sphères F : T Y → T Z tel que T Y et T Z sont des sphères marquées (d’uniques sommets respectifs v et v′) est équivalent `a la donnée d’un revetement ramifié entre les uniques sommets in-ternes de T Y et T Z qui tel que les points d’attache d’aretes sont les pré-images des points d’attache d’aretes et qu’ils contiennent les points de ramification. On parle alors de revetement de sphères marquées et on confond F et le triplet (fv, aYv , aZv′ ).
Pour tout sommet interne v ∈ IV Y , on notera pour simplifier deg(v) := deg(fv). De meme pour tout x ∈ Sv on notera deg(x) := degxfv. La condition 3 assure que l’on peut définir un degr´ pour toute arete e entre deux sommets internes v1 et v2 de T Y , que l’on notera deg(e) := degev1 fv1 = degev2 fv2 .
Toute feuille y ∈ Y est reliée `a un unique sommet interne v par une arete e, on peut donc définir
deg(y) := deg(e) := degev fv.
Ceci définit une application degr´ pour l’application F : Y → Z.
Définition 1.22. On appelle sommet critique (resp. feuille critique) de F tout sommet de T Y (resp. toute feuille y ∈ Y ) ayant un degr´ supérieur `a 1. On appelle alors mult (y) := deg(y) − 1 la multiplicité de y. On note CritF l’ensemble des feuilles critiques de F.
Table des matières
Introduction
1 Objets non dynamiques
1.1 Arbres combinatoires
1.1.1 Arbres et sous-arbres
1.1.2 Topologie
1.1.3 Caractéristique
1.2 Application d’arbres combinatoires
1.3 Arbres de sphères
1.4 Revetement d’arbres de sphères
1.4.1 Définitions et degré
1.4.2 Conséquences de la formule de Riemann-Hurwitz
1.4.3 Revetements holomorphes
2 Dynamique
2.1 Système dynamique et arbres stables
2.2 Dynamique d’arbres combinatoires
2.3 Dynamique sur les arbres de sphères
3 Convergence
3.1 Convergence de sphères marquées
3.2 Convergence de revetement de sphères marquées
3.2.1 Définitions et premières propriétés
3.2.2 Lemme des branches
3.2.3 Lemmes des anneaux
3.3 Cas du degré 2
4 Classes d’isomorphismes d’arbres de sphères
4.1 Classes d’isomorphismes d’arbres combinatoires et partitions
4.2 Classes d’isomorphismes d’arbres de sphères et topologie
4.3 Compacité, variété projective
5 Classes d’isomorphismes de revetements
5.1 Isomorphismes de revetements d’arbres
5.2 Revetements marqués, topologie
5.3 Compacité
6 Dynamique
6.1 Arbres compatibles
6.2 Compactification de ratF,X
7 Liens et applications
7.1 Limites renormalisées
7.2 Exemple `a partir de la remarque de Milnor
7.3 Exemple d’Epstein-Petersen
7.4 Compactification de Milnor
7.5 Exemples de J. Kiwi
7.6 Limites renormalisées et espaces de Berkovich
7.6.1 Sur les espaces de Berkovich
7.6.2 Résolution des singularités et séries de Puiseux dans Pern(0)
7.7 Stretching et arbres de sphères
7.7.1 Arbres et polynˆomes
7.7.2 Arbres d’anneaux de Hermann
7.8 Arbres de sphères et multicourbe pincée
