\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection, NoEqCountersInSection,published]{cedram} \usepackage{xups16-02} \setcounter{tocdepth}{2} %\XUPScorrections \graphicspath{{xups16-02_figures}} \let\subsection\Subsection \hyphenation{natu-rel-le-ment défi-ni-tion vari-a-ble vari-a-bles résul-tat limi-te métho-de davan-ta-ge indé-pen-dant indé-pen-dants} \datepublished{2024-08-06} \begin{document} \frontmatter \title[Probabilités sur le graphe complet]{Probabilités sur le graphe complet: l'exem\-ple des arbres couvrants uniforme et minimal} \author[\initial{G.} \lastname{Miermont}]{\firstname{Grégory} \lastname{Miermont}} \address{Université de Lyon, ÉNS de Lyon \& Institut Universitaire de France} \email{gregory.miermont@ens-lyon.fr} \urladdr{http://perso.ens-lyon.fr/gregory.miermont/} \thanks{Journées X-UPS 2016. Arbres et marches aléatoires. Éditions de l'École polytechnique, 2016} \begin{abstract} Ce texte propose quelques exemples d’analyse de grandes structures combinatoires aléatoires, que l’on peut définir naturellement en termes de modèles simples d’arbres couvrants sur le graphe complet. \end{abstract} \maketitle \tableofcontents \mainmatter \section{Introduction}\label{sec:introduction} \subsection{Contexte} Le thème développé dans ce texte se situe à l'interface entre différents aspects des probabilités: physique statistique, combinatoire, optimisation. Le thème de la physique statistique est de décrire l'état d'un \og grand système\fg à l'aide d'une description microscopique, au~niveau particulaire: souvent, pour simplifier ou pour des raisons physiques, on considère que ces espaces de configurations sont définis sur les sites d'un graphe fini, par exemple un sous-graphe de $\Z^d$. Quelques exemples de modèles de référence sont \begin{itemize} \item La percolation, où chaque arête du graphe est conservée avec une probabilité donnée, indépendamment entre les arêtes \item Le modèle de Lenz-Ising du ferromagnétisme, où chaque sommet est muni d'un signe $+$ ou $-$, et où chaque configuration apparaît avec une probabilité dépendant d'une énergie définie en termes du nombre de sommets adjacents de signes opposés \item L'arbre couvrant uniforme, qui est le modèle que nous allons étudier plus en détail \item La marche aléatoire auto-évitante uniforme, qui est un modèle naturel décrivant le repliement d'un polymère, traité dans les exposés de Vincent Beffara. \end{itemize} Pour une introduction accessible à certains de ces sujets, on recommande notamment la lecture des excellents articles de Raphaël Cerf, Hugo Duminil-Copin et Marie Théret sur le site web \emph{Images des mathématiques}. Par ailleurs, en optimisation combinatoire, on cherche à minimiser une fonction aléatoire de l'espace des configurations (souvent interprétée comme une énergie), avec l'idée de décrire un système physique dans un état d'équilibre. On s'intéressera ici encore au cas où l'espace des configurations est l'ensemble des arbres couvrants d'un graphe donné. Nous allons considérer de tels systèmes définis sur le graphe complet, où chaque sommet est connecté à tous les autres. Cette \og géomé\-trie\fg est beaucoup plus simple à décrire que celle du réseau $\Z^d$, par exemple par un comptage entièrement explicite des configurations possibles, d'où le lien avec la combinatoire. Mais il est instructif d'étudier les modèles ci-dessus dans ce cas simple: à la fois parce qu'ils peuvent donner une intuition précieuse sur les modèles sur réseau, mais aussi parce que leur simplicité fait surgir des objets fondamentaux que l'on retrouve en de nombreuses autres occasions en probabilités. Les deux objets-clés qui nous intéresseront dans ces notes ont été introduits par David Aldous \cite{aldous_continuum_1991-1,aldous_asymptotics_1992}. Ce sont deux modèles d'arbres aléatoires \og continus\fg de natures très différentes. Le premier (l'arbre continu aléatoire brownien) est également un acteur-clé du texte d'Igor Kortchemski. Le second est une intri\-gante structure arbo\-rescente où tout sommet est à la fois de degré infini, et n'a pourtant qu'un nombre fini de voisins à distance bornée. Nous suivrons d'assez près l'article \cite{aldous_continuum_1991-1}, ainsi que l'article de revue d'Aldous et Steele \cite{aldous_objective_2004}. \subsection{Terminologie et notations} On emploiera les notations $\N=\{1,2,\ldots\}$ et $\Z_+=\N\cup \{0\}$. Pour $n\in \N$, on notera $[n]=\{1,2,\ldots,n\}$. \subsubsection*{Graphes} Rappelons qu'un \emph{graphe} (simple) est un couple $G=(V,E)$, où $V=V(G)$ est un ensemble de \emph{sommets}, et $E=E(G)$ est un ensemble de paires $\{x,y\}$ avec $x,y\in V$ et $x\neq y$. On notera souvent $|G|=\card(G)$ le cardinal de l'ensemble des \emph{arêtes} de $G$. On dit que les sommets $x,y$ sont \emph{adjacents} si $e=\{x,y\}\in E$, ce que l'on note $x\sim y$ pour simplifier, et l'on dit que $x,y$ sont les extrémités de l'arête $e$. Le graphe est \emph{orienté} si l'on distingue un ordre $\vec{e}=(x,y)$ pour chaque arête $e=\{x,y\}\in E$. On dit alors que $x$ est l'\emph{origine}, et~$y$ la \emph{cible} de $\vec{e}$. Un chemin dans un graphe $G=(V,E)$ est une suite finie $(x_1,x_2,\ldots,x_k)$ de sommets avec \[ x_i\sim x_{i+1}\quad\text{pour tout $i\in \{1,2,\ldots,k-1\}$}, \] et on dit que $k-1$ est la \emph{longueur} de ce chemin. On dit que c'est une \emph{chaîne} si de plus tous les $x_i$ sont deux à deux distincts, et un \emph{cycle} si $x_1=x_n$ et si $x_1,\ldots,x_{n-1}$ sont deux à deux distincts. Le graphe $G$ est \emph{connexe} si pour tout $x,y\in V$, il existe une chaîne commençant en $x$ et finissant un $y$. Un \emph{arbre} est un graphe $G=(V,E)$ connexe, sans cycle. Si $V$ est fini, cela équivaut au fait que $G$ est connexe et a $\card(V)-1$ arêtes, ou encore, que $G$ est sans cycle et a $\card(V)-1$ arêtes. Ainsi, $n-1$ est le nombre minimal (\resp maximal) d'arêtes permettant de connecter $n$ sommets (\resp permettant de ne pas créer de cycle sur $n$ sommets). Un \emph{graphe enraciné} est un couple $(G,v)$ où $G=(V,E)$ est un graphe et $v\in V$. Un \emph{graphe marqué} est un couple $(G,f)$ où $f:E\to \Xi$ est une fonction positive définie sur les arêtes, à valeurs dans un ensemble de marques $\Xi$. Si $\Xi=(0,\infty)$, on parlera de \emph{graphe pondéré}. Un sous-graphe \emph{couvrant} de $G$ est un graphe $G'=(V,E')$ avec $E'\subset E$: on peut également le voir comme le graphe marqué $(V,E,f)$ avec $f(e)=\ind_{\{e\in E'\}}$. Si $G'$ est un sous-graphe couvrant qui est un arbre, on dit que $G'$ est un arbre couvrant. On notera $K_n=([n],E(K_n))$ le graphe complet à $n$ sommets étiquetés $[n]=\{1,2,\ldots,n\}$, et avec $E(K_n)=\{\{i,j\}:i,j\in [n],i\neq j\}$. \subsubsection*{Notions probabilistes} Les variables aléatoires que nous considérerons seront toujours supposées définies sur un espace de probabilités $(\Omega,\FF,\P)$. Soit $(X_n,n\geq 1),X$ des variables aléatoires à valeurs dans un espace métrique $(M,d)$. On dit que $X_n$ converge \emph{en loi} vers $X$ si pour toute fonction $f:M\to \R$ continue bornée, on a $$\E[f(X_n)]\underset{n\to\infty}{\longrightarrow} \E[f(X)].$$ Dans le cas où $M=\R^d$ normé, il suffit en fait de le vérifier pour les fonctions $f$ continues à support compact. Voici quelques faits sur la convergence en loi qui nous serviront au cours du texte. \begin{enumerate} \item Par un théorème de Skorokhod, la convergence en loi de $X_n$ vers $X$ signifie que l'on peut trouver, sur un espace de probabilités éventuellement différent, des variables aléatoires $(X'_n,n\geq 1),X'$ telles que \begin{itemize} \item pour tout $n\geq 1$, $X'_n$ a même loi que $X_n$ \item $X'$ a même loi que $X$ \item l'événement $\lim X_n'=X'$ lorsque $n\to\infty$ a probabilité $1$ (il~est presque sûr). \end{itemize} \item Si $X_n$ est à valeurs dans $\R$, il y a équivalence entre la convergence en loi de $X_n$ vers $X$ et le faut que $\P(X_n>r)$ converge vers $\P(X>r)$, pour tout $r$ tel que $\P(X=r)=0$. \item Si $X_n$ est à valeurs dans $\Z^d$ pour un entier $d\geq 1$, et si l'on a que pour une suite $a_n\to\infty$ $$\P(X_n=x)=\frac{1}{a_n^d}g\left(\sfrac{x}{a_n}\right)(1+o(1)),$$ ce uniformément pour tout $x=O(a_n)$, où $g:\R^d\to \R_+$ est une densité de probabilités (c'est-à-dire que $\int g=1$), alors on a que $X_n/a_n$ converge en loi vers $X$, variable aléatoire dont la loi est donnée par $g(x)\d x$ sur $\R^d$. \end{enumerate} \section{L'arbre couvrant uniforme}\label{sec:larbre-couvr-unif} Soit $G=(V,E)$ un graphe fini (simple, non orienté) et connexe. Un arbre couvrant est un sous-graphe $T=(V,E')$, $E'\subset E$, qui est un arbre. On note $\mathbf{A}_G$ l'ensemble des arbres couvrants de $G$, qui est évidemment fini. On dit qu'une variable aléatoire $A$ sur un espace de probabilités $(\omega,\mathcal{F},\P)$, et à valeurs dans $\mathbf{A}_G$, est un arbre couvrant uniforme de $G$ si $$\P(A=\mathbf{a})=\frac{1}{\card(\mathbf{A}_G)},\qquad \mathbf{a}\in \mathbf{A}_G.$$ Dans le cas où $G=K_n$, l'ensemble $\mathbf{A}_n=\mathbf{A}_{K_n}$ est tout simplement l'ensemble des arbres sur $[n]$. On peut se demander pourquoi l'on insiste sur le fait que ces arbres \og couvrent\fg $K_n$, la raison étant que l'ensemble des arbres couvrants d'un graphe est extrêmement étudié. Pour commencer, on peut simplement se demander combien il y en~a. \begin{theorem}[Cayley]\label{sec:larbre-couvr-unif-1} Le cardinal de $\mathbf{A}_n$ est $n^{n-2}$. \end{theorem} Il existe de très nombreuses preuves de ce résultat, et nous en rencontrerons trois chemin faisant, une partielle et deux complètes. Pour $v_0\in V$ on notera également $\bA_G(v_0)$ l'ensemble des arbres couvrants $(\ba,v_0)$ de $G$ enracinés en $v_0$, et dans ce cas, on conviendra que les arêtes $\{u,v\}$ de $\ba$ sont systématiquement munies de l'orientation $(u,v)$ telle que $d_\ba(u,v_0)=d_\ba(v,v_0)+1$, où $d_\ba(v,w)$ est la distance de graphe sur $\ba$ entre $v$ et $w$. Une feuille de $\ba$ est par définition un sommet vers lequel aucune arête ne pointe, dans cette orientation canonique. \subsection{Dénombrement} On peut déterminer le cardinal de $\mathbf{A}_G$ en termes du déterminant du laplacien du graphe: soit $M$ la matrice d'adjacence de $G=(V,E)$, qui est la matrice définie par $$M(v,v')=\mathbf{1}_{\{v\sim v'\}},\qquad v,v'\in V, $$ où l'on note $v\sim v'$ si $\{v,v'\}\in E$, et notons $D(v,v')=\deg(v)\mathbf{1}_{\{v=v'\}}$ où $\deg(v)=\card\{v'\in V:v'\sim v\}$ est le degré de $v$. Enfin, on note $\Delta^G=D-M$. Clairement, $\Delta^G$ n'est pas une matrice inversible puisque $\Delta^G \mathbf{1}=0$, où $\mathbf{1}$ est le vecteur de $\R^V$ dont toutes les composantes sont égales à $1$. En revanche, on peut montrer que si $G$ est connexe, alors la matrice $\Delta^G_{v_0}$ obtenue en retirant la ligne et la colonne correspondant à $v_0\in V$ est inversible pour tout $v_0$, et de plus \begin{theorem}[Kirchhoff]\label{sec:denombrement} On a que $|{\det}(\Delta^G_{v_0})|=\card(\mathbf{A}_G)$ pour tout $v_0\in V$. \end{theorem} Nous ne donnons pas la preuve de ce théorème ici. Une application directe au cas de $G=K_n$ et $v_0=1$ donne une première preuve du théorème de Cayley ci-dessus, par le calcul du déterminant de la matrice circulante $(n-1)\times (n-1)$: $$\Delta^{K_n}_1= \left(\begin{array}{cccc} n-1 & -1 &\ldots& -1\\ -1 & n-1 &\ldots &-1\\ \vdots&\vdots & \ddots & \vdots\\ -1 & -1 &\ldots & n-1 \end{array}\right). $$ \subsection{Simulation} Nous cherchons à présent à décrire la géométrie d'un arbre couvrant aléatoire de $K_n$. Par exemple, quel est le diamètre typique d'un tel arbre, en fonction de $n$, et comment ce diamètre évolue-t-il lorsque $n\to\infty$? Un problème naturel similaire consiste à étudier le comportement asymptotique d'une marche aléatoire $$S_n=X_1+X_2+\ldots+X_n$$ où les variables aléatoires $X_1,X_2,\ldots$ sont indépendantes et de même loi, par exemple $\P(X_1=1)=1-P(X_1=-1)=1/2$. En effet, la loi forte des grands nombres stipule que $S_n/n\to 0$ presque sûrement lorsque $n\to\infty$, tandis que le théorème central limite donne $$\P\Bigl(a\leq \frac{S_n}{\sqrt{n}}\leq b\Bigr)\underset{n\to\infty}{\longrightarrow}\int_a^b\sqrt{\frac{2}{\pi}}\,\exp(-2x^2)\, \d x$$ pour tout $ai:X_j\in \{X_0,X_1,\ldots,X_{j-1}\}\},$$ c'est-à-dire que $R_1,R_2,\ldots$ sont les instants successifs où la suite $X_0,X_1,\ldots$ répète une valeur déjà prise par le passé. L'arbre $A$ de l'algorithme peut alors s'interpréter comme le graphe dont les arêtes sont $$\{\{X_{j-1},X_j\}:j\geq 1,j\notin\{R_1,R_2,\ldots\}\}.$$ \subsubsection{Le cas du graphe complet} Nous allons donner une preuve du théorème \ref{sec:simulation-2} \emph{ uniquement dans le cas où $G=K_n$ est le graphe complet}. Dans ce cas précis, la marche aléatoire $(X_1,X_2,\ldots)$ est particulièrement simple: à l'étape $i$, on choisit un élément de $[n]$ distinct de $X_i$ uniformément au hasard. En fait, pour simplifier les choses encore un peu, nous allons supposer que $X_1,X_2,\ldots$ est une suite de variables aléatoires i.i.d.\ uniformes dans $[n]$: cela revient à dire que la marche aléatoire reste sur place avec probabilité $1/n$ à chaque étape. Clairement, cela ne modifie pas la nature de l'algorithme d'Aldous-Broder. Par ailleurs, pour fixer les idées, on prendra $X_0=1$ dans l'énoncé qui suit. Néanmoins, clairement, on peut oublier l'enracinement par symétrie. Suivant Camarri-Pitman \cite{camarri_limit_2000}, on peut donner une description exacte du déroulé de l'algorithme, au sens suivant. \begin{lemma}\label{sec:simulation-1} Soit $m\geq 1$ fixé, et $y_1,y_2,\ldots,y_m,x\in [n]$. On se donne un arbre $\ba=(V(\ba),E(\ba))$ enraciné en $1$ sur un sous-ensemble $V(\ba)$ de $[n]$, dont les feuilles sont incluses dans $\{y_1,\ldots,y_m\}$. On note enfin $A[m]$ le sous-arbre de $A$ obtenu en ne gardant que les arêtes $\{X_{j-1},X_j\}$ avec $j\in \{1,2,\ldots,R_m-1\}\setminus\{R_1,R_2,\ldots,R_{m-1}\}$. Alors si $|\ba|$ est le nombre d'arêtes de $\ba$, et si $x$ est un sommet de $\ba$, $$\P(X_{R_i-1}=y_i,1\leq i\leq m;X_{R_m}=x;A[m]=\ba)=\frac{1}{n^{m+|\ba|}}.$$ \end{lemma} \begin{proof} Notons que la contrainte que toute feuille de $\ba$ soit de la forme $y_i$ provient de la construction de l'algorithme: en effet, si $i$ n'est pas un instant de la forme $R_j-1$ pour un $j\geq 1$, cela signifie que $i+1$ est le premier instant où le sommet $X_{i+1}$ est visité, et l'arête $\{X_i,X_{i+1}\}$ est dans l'arbre construit par l'algorithme, avec l'orientation $(X_{i+1},X_i)$. Donc $X_i$ n'est pas une feuille de $A$. Notons aussi que l'on a $R_m=m+|A[m]|$ puisque $A[m]$ est constitué de $R_m-m$ arêtes (une arête pour chaque itération de l'algorithme, sauf lorsque cela implique une répétition). On montre alors le résultat par récurrence sur $m$. Pour $m=1$, l'arbre $A[1]$ est la chaîne $1=X_0,X_1,\ldots,X_{R_1-1}$. De ce fait, si $\ba$ est une chaîne $1=x_0,x_1,\ldots,x_k$, si $y_1=x_k$ est l'unique feuille de $\ba$ (enraciné en $1$), et si $x\in \{x_0,x_1,\ldots,x_k\}$, l'événement $\{X_{R_1-1}=y_1,X_{R_1}=x,A[1]=\ba\}$ est l'événement $\{X_1=x_1,\ldots,X_k=x_k,X_{k+1}=x\}$, et cela a probabilité $1/n^{k+1}=1/n^{1+|\ba|}$. Supposons le résultat connu au rang $m$. Notons alors que $A[m+\nobreak1]$ s'obtient en ajoutant la chaîne $\{X_{R_{m}},X_{R_{m}+1},\ldots,X_{R_{m+1}-1}\}$ au graphe $A[m]$. Soit alors $\ba$ un arbre enraciné en $1$ dont les feuilles sont incluses dans un ensemble $\{y_1,\ldots,y_{m+1}\}$, et soit $\ba'$ le sous-arbre engendré par la racine et les sommets $y_1,\ldots,y_m$: il s'agit de la réunion des chaînes orientées de $y_1,\ldots,y_m$ vers la racine $1$ dans $\ba$. La chaîne orientée de $y_{m+1}$ vers $1$ rencontre $\ba'$ pour la première fois en un sommet $x'$, de sorte que $\ba$ est la réunion de $\ba'$ avec une chaîne, disons $\{x'=x_0,x_1,\ldots,x_k\}$, avec $k=|\ba|-|\ba'|$. L'événement $\{X_{R_i-1}=y_i,1\leq i\leq m+1;A[m+1]=\ba,X_{R_{m+1}}=x\}$ peut alors se réécrire \begin{multline*} \{X_{R_i-1}=y_i,1\leq i\leq m;A_{m}=\ba',X_{R_m}=x'\}\\ \cap\{X_{R_m+1}=x_1,\ldots,X_{R_m+k}=x_k,X_{R_m+k+1}=x\}, \end{multline*} mais sur le premier événement, on a que $R_m=m+|\ba|$, et on voit que le premier événement ne dépend que des variables aléatoires $$X_1,X_2,\ldots,X_{m+|\ba|},$$ tandis que le second dépend de $$X_{m+1+|\ba|},X_{m+2+|\ba|},\ldots.$$ Par indépendance, on conclut que \begin{align*} \P(X_{R_i-1}&=y_i,1\leq i\leq m+1;A[m+1]=\ba,X_{R_{m+1}}=x)\\ &=\frac{1}{n^{|\ba|-|\ba'|+1}}\P(X_{R_i-1}=y_i,1\leq i\leq m;A_{m}=\ba',X_{R_m}=x')\\ &=\frac{1}{n^{|\ba|-|\ba'|+1}}\cdot\frac{1}{n^{m+|\ba'|}}=\frac{1}{n^{m+1+|\ba|}} \end{align*} où l'on a utilisé l'hypothèse de récurrence à l'avant-dernière étape. D'où le résultat. \end{proof} De ce résultat, on déduit le théorème \ref{sec:simulation-2} dans le cas particulier $G=K_n$. \begin{corollary} \label{sec:simulation} La probabilité que l'algorithme d'Aldous-Broder sur le graphe complet donne un arbre couvrant $\ba$ donné est $$\P(A=\ba)=\frac{1}{n^{n-2}}.$$ En particulier, $A$ est uniforme dans $\bA_n$ et $\card(\bA_n)\!=\!n^{n-2}$. De~plus, la suite $X_{R_1-1},X_{R_2-1},\ldots$ est i.i.d.\ uniforme sur $\{1,2,\ldots,n\}$, et indé\-pendante de $A$ \end{corollary} \begin{proof} Soit $\ba$ un arbre couvrant de $K_n$, et $m\geq n$. Si l'on somme la formule du lemme \ref{sec:simulation-1} sur toutes les familles $y_1,\ldots,y_m$ telles que $\{y_1,\ldots,y_m\}=[n]$ (on notera $\by=(y_1,\ldots,y_m)\in C_{m,n}$), alors en notant que $A[m]=A$ sur l'événement où $(X_{R_i-1},1\leq i\leq m)\in C_{m,n}$, \begin{align*} \P((X_{R_i-1},&1\leq i\leq m)\in C_{m,n};A=\ba)\\ &=\sum_{\substack{\by\in C_{m,n}\\ x\in [n]}}\P(X_{R_i-1}=y_i,1\leq i\leq m;X_{R_m}=x;A[m]=\ba)\\ &=\frac{n\card C_{m,n}}{n^{m+1}}\cdot\frac{1}{n^{|\ba|-1}}=\frac{\P((X_1,\ldots,X_m)\in C_{m,n})}{n^{n-2}}. \end{align*} Ici, on a utilisé le fait que $|\ba|=n-1$, qui vient du fait général qu'un arbre a toujours un sommet de plus que d'arêtes. Si l'on fait tendre~$m$ vers l'infini, chacun des événements $\{(X_{R_i-1},1\leq i\leq m)\in C_{m,n}\}$ et $(X_i,1\leq i\leq m)\in C_{m,n}$ a une probabilité qui tend vers $1$, $n$ étant fixé. On conclut donc par un passage à la limite que l'on a la formule attendue. La fin de l'énoncé est obtenu de façon similaire: cette fois on choisit $k\geq 1$ et des entiers $y_1,\ldots,y_k\in [n]$ et on écrit, pour tout $m\geq n$, \begin{align*} \P&((X_{R_i-1},k< i\leq m+k)\in C_{m,n}; X_{R_i-1}=y_i,1\leq i\leq k;A=\ba)\\ &=\!\!\sum_{\by'\in C_{m,n}}\P(X_{R_i-1}=y_i,1\leq i\leq k;X_{R_{k+i}-1}=y'_i,1\leq i\leq m;A=\ba)\\ &=\frac{\P((X_1,\ldots,X_m)\in C_{m,n})}{n^k\cdot n^{n-2}}, \end{align*} enfin, on prend la limite $m\to\infty$ et on conclut. \end{proof} \subsubsection{Efficacité} Combien de temps faut-il à l'algorithme pour termi\-ner? Dans le cas du graphe complet, le temps de couverture est (à~une soustraction de $1$ près, puisque l'on a $X_0=0$) $$C_n=\inf\{k\geq 1:\{X_1,\ldots,X_k\}=[n]\}.$$ On montre que ce temps $C_n$ a même loi qu'une somme de variables aléatoires indépendantes de lois géométriques, respectivement de paramètres $1,(n-1)/n,(n-2)/n,\ldots,1/n$: $$C_n=\sum_{i=1}^n\tau_i$$ où $$\P(\tau_i>k)=\Big(\frac{i-1}{n} \Big)^k,\qquad i\in [n],k\geq 0.$$ Ici, $\tau_i-1$ représente le nombre de fois où la suite $X_1,X_2,\ldots$ a répété une des $i-1$ premières valeurs déjà prises avant de découvrir pour la première fois une $i$-ième valeur. Une application d'une inégalité de Bienaymé-Chebychev montre que l'on a que $C_n/n\ln n$ converge vers~$1$ en probabilité, c'est-à-dire que pour tout $\eps>0$, $$\P \Big(\Big |\frac{C_n}{n\ln(n)}-1 \Big |>\eps \Big)\underset{n\to\infty}{\longrightarrow}0.$$ On parle du problème du \emph{collectionneur de coupons}: $C_n$ est le temps que doit mettre un collectionneur pour obtenir une collection complète de $n$ images, s'il se procure à chaque instant une image choisie uniformément au hasard dans la collection. On peut également se demander à quelle vitesse la probabilité ci-dessus tend vers $0$. Pour ce faire, on peut constater que pour tous $k,n$ fixés, l'événement $\{C_n>k\}$ est égal à $\bigcup_{i=1}^nA_i$ où $$A_i=\{i\notin \{X_1,\ldots,X_k\}\}.$$ La formule d'inclusion-exclusion donne alors que \begin{align*} \P(C_n\leq k)&=\sum_{r=0}^n(-1)^r\sum_{1\leq i_1<\ldots 0$, et soit~$A$ l'arbre généalogique d'un processus de branchement de Bienaymé-Galton-Watson, de loi de reproduction $\mu$, conditionné à avoir $n$ sommets. On étiquette ses sommets uniformément au hasard. Le graphe sur $V=[n]$ obtenu est alors un arbre couvrant uniforme de $K_n$. \end{propositio} \subsection{Géométrie asymptotique: l'arbre continu aléatoire}\label{sec:geom-asympt} Notons $A_n$ une variable aléatoire qui est un arbre couvrant uniforme de $K_n$. On insiste sur la dépendance en $n$, ce dernier para\-mètre allant être envoyé vers l'infini. Que peut-on dire de la géométrie de~$A_n$? \subsubsection{Distance entre deux points marqués}\label{sec:distance-entre-deux} L'algorithme d'Aldous-Broder permet de donner une réponse à cette question. Commençons par étudier la distance de graphe dans $A_n$ entre deux sommets choisis uniformément au hasard (ou, ce qui revient au même, entre la racine~$1$ et un sommet choisi au hasard, pour des raisons claires de symétrie). Le corollaire \ref{sec:simulation} montre que cette distance de graphe a même loi que la première répétition $R_1=R^{(n)}_1$ dans une suite $X_1,X_2,\ldots$. Il y a un lien clair avec un problème très connu en probabilités, appelé le \og paradoxe des anniversaires \fg, qui consiste à observer que la probabilité qu'au moins deux individus dans un groupe de $m$ personnes aient la même date d'anniversaire subit une transition abrupte de $0$ à $1$ lorsque $m$ passe, disons, de 20 à 26. Ici, le problème est le même: $n$ est, disons, le nombre de dates d'anniversaire possibles (365 dans le véritable problème des anniversaires), et l'on peut voir $R_1^{(n)}$ comme le premier instant où, en observant les individus d'un groupe un à un, l'on s'aperçoit de l'existence d'une coïncidence d'anniversaires. \begin{propositio} \label{sec:geom-asympt-larbre} Lorsque $n\to\infty$, la variable aléatoire $R_1^{(n)}/\sqrt{n}$ converge en loi vers une variable de loi de Rayleigh, au sens où $$\P(R_1^{(n)}> r\sqrt{n})\underset{n\to\infty}{\longrightarrow} \exp(-r^2/2),$$ où il convient d'interpréter $\exp(-r^2/2)$ comme la queue de distribution de la loi à densité $re^{-r^2/2}\d r\mathbf{1}_{\R_+}(r)$ (loi de Rayleigh). Plus généralement, pour tout $m$ on a la convergence en loi des $m$ premiers temps de répétitions $n^{-1/2}(R_1^{(n)},\ldots,R_m^{(n)})$ vers un vecteur limite $(L_1,\ldots,L_m)$, dont la loi est à densité: $$\ell_1\ell_2\ldots\ell_m\exp\left(-\sfrac{\ell_m^2}{2}\right)\d\ell_1\d \ell_2\ldots \d \ell_m\ind_{\{0<\ell_1<\ell_2<\ldots<\ell_m\}}$$ \end{propositio} \begin{proof} Remarquons que si $a$ est un entier, \begin{align*} \P(R^{(n)}_1>a)&=1\cdot(1-1/n)\cdot(1-2/n)\ldots(1-a/n)\\ &=\exp\Big(\sum_{i=1}^a\ln(1-i/n) \Big). \end{align*} Si $a$ est maintenant autorisé à dépendre de $n$, mais avec $a=O(\sqrt{n})$, on obtient $$\P(R^{(n)}_1>a)=\exp \Big(-n^{-1}\sum_{i=1}^ai+o(1) \Big)=\exp(-a^2/2n+o(1))\, ,$$ d'où le résultat. En fait, on peut être plus précis et constater que $$\P(R^{(n)}_1=a)=\frac{a-1}{n}\,\P(R^{(n)}_1>a)=\frac{a}{n}\exp(-a^2/2n+o(1)).$$ Cet argument se généralise si l'on considère les répétitions suivantes: par exemple, pour $ax)=e^{-x}$, $$\P(\be_n> (1+\eps)\ln(n))=n^{-(1+\eps)},$$ qui est sommable, et donc presque sûrement $\be_n\leq (1+\eps)\ln(n)$ pour tout $n$ assez grand. \subsubsection{Construction de l'arbre continu}\label{sec:constr-de-larbre-2} Comment interpréter ce résultat? Rappelons que l'on peut voir $A_n$, dans la construction par l'algorithme d'Aldous-Broder, comme un processus de recollement de chaînes de longueurs $R^{(n)}_1,R^{(n)}_2-R^{(n)}_1,R^{(n)}_3-R^{(n)}_2,\ldots$, la chaîne de longueur $R^{(n)}_{m+1}-R^{(n)}_{m}$ étant branchée sur un sommet uniforme sur l'arbre réduit $A_n[m]$. Nous savons que les différences de longueurs, renormalisées par $\sqrt{n}$, convergent lorsque $n\to\infty$ vers la suite $L_1,L_2-L_1,L_3-L_2,\ldots$ de limite nulle que nous avons décrite ci-dessus. Ceci donne une intuition de ce que devrait être la structure limite de $A_n$, lorsque toutes les distances sont renormalisées par $\sqrt{n}$. La description suivante est appelée la \emph{line-breaking construction} par Aldous \cite{aldous_continuum_1991-1}. Elle consiste à brancher récursivement des segments réels de longueur $L_i-L_{i-1},i\geq 1$, en recollant une des extrémités en un point uniformément choisi parmi la réunion des $i-1$ premiers segments recollés. Soit $U_1,U_2,\ldots$ une suite de variables aléatoires i.i.d.\ uniformes sur $[0,1]$, indépendantes de $L_1,L_2,\ldots$. Considérons la distance~$D_\infty$ sur $\R_+$ obtenue en \og coupant \fg $\R_+$ aux points $L_i$, c'est-à-dire que $D_\infty(x,y)=|x-y|$ s'il existe $i$ tel que $x,y\in [L_{i-1},L_i[$, et~$D_\infty(x,y)=\nobreak\infty$ sinon, où l'on note $L_0=0$ par convention. On~considère la plus petite relation d'équivalence $\approx$ sur $\R_+$ telle que $L_i\approx U_iL_i$ pour tout $i\geq 1$. Enfin, on considère le quotient métrique de $\R_+$ par~$\approx$. Il s'agit de l'espace métrique obtenu en recollant les (paires~de) points identifiés par $\approx$. Plus précisément, on note $$D(x,y)=\inf\left\{\sum_{i=1}^kD_\infty(x_i,y_i)\right\},$$ où l'infimum porte sur toutes les suites finies de points $x_1,y_1,\ldots,x_k,y_k$ avec $x_1=x$, $y_k=y$ et $y_i\approx x_{i+1}$ pour $1\leq i\leq k-1$. Il n'est pas difficile de voir que cet infimum est en fait atteint, et que $D(x,y)=0$ si et seulement si $x\approx y$. Le quotient métrique est l'espace quotient $\R_+/{\approx}$ muni de la métrique induite par la (pseudo) distance $D$, encore notée $D$. De façon intuitive, nous avons donc collé l'extrémité gauche de l'intervalle $[L_i,L_{i+1}[$ au point $U_iL_i$, qui appartient à la réunion des $i$ premiers intervalles $[L_{j-1},L_j[,1\leq j\leq i$. \begin{figure}[htb] \centering \includegraphics[scale=.9]{CRTU} \caption{Quelques milliers d'itérations de la \emph{line-breaking construction}, plongée dans $\R^3$ avec une orientation choisie uniformément au hasard pour chaque segment} \label{fig:CRTU} \end{figure} \begin{definitio} L'arbre continu aléatoire brownien est l'espace complété de $(\R_+/{\approx},D)$. On le note $\mathcal{T}$. \end{definitio} Un autre nom communément utilisé est CRT, pour \emph{Continuum Random Tree}. Pour énoncer quelques propriétés importantes de $\mathcal{T}$, donnons une définition. \begin{definitio}\label{sec:constr-de-larbre-3} Un espace métrique $(M,d)$ est un $\R$-arbre si \begin{itemize} \item pour tout $x,y\in M$, il existe un application isométrique $$\phi:[0,d(x,y)]\to M\quad\text{avec }\phi(0)=x,\phi(d(x,y))=y$$ (on dit que $\phi$ est une géodésique de $x$ à $y$), et \item il n'existe pas d'application continue injective $\mathbb{S}^1\to M$. \end{itemize} \end{definitio} En particulier, si un espace $(M,d)$ est un $\R$-arbre il est connexe (et même connexe par arcs) et sans cycle, au sens de la deuxième propriété caractéristique. On ajoute juste la propriété supplémentaire que la métrique est une métrique de longueur, c'est-à-dire que la distance entre deux points s'interprète comme la longueur d'un (plus court) chemin continu entre ces points. On peut penser à un $\R$-arbre comme à un recollement de copies isométriques de segments réels, de façon à ne pas créer de cycle, comme le fait la \emph{line-breaking construction}. \begin{theorem} \label{sec:constr-de-larbre} L'espace aléatoire $\mathcal{T}$ est un $\R$-arbre presque sûrement, et sa dimension de Hausdorff est égale à $2$ presque sûrement. \end{theorem} Aldous \cite{aldous_continuum_1991-1}, montre la première partie de l'énoncé, ainsi qu'un résultat sur la dimension de Minkowski (le nombre de boules nécessaires pour recouvrir l'arbre), le résultat sur la dimension de Hausdorff apparaît dans Duquesne-Le\,Gall \cite{duquesne_probabilistic_2005}. Nous ne redonnons pas ici la définition de dimension de Hausdorff, mais insistons sur le côté un peu surprenant que peut avoir ce résultat à première vue: en effet, le CRT semble être un objet $1$-dimensionnel, puisqu'il est obtenu à partir d'un recollement d'une quantité dénombrable de segments réels. Néanmoins, rappelons que $\TT$ est en fait la \emph{complétion} d'un tel recollement, et cette opération ajoute une quantité indénombrable de points (ces points sont nécessairement des \emph{feuilles}, c'est-à-dire des points $x$ tels que $\TT\setminus\{x\}$ est connexe). Par analogie, on pourra penser aux ensembles de Cantor, que l'on obtient en retirant une collection dénombrable d'intervalles ouverts disjoints de $[0,1]$: les extrémités gauches de ces intervalles forment un sous-ensemble dénombrable dense dans l'ensemble de Cantor correspondant, mais ce dernier est lui-même non dénombrable. Enfin, nous avons indiqué dans quelle mesure on peut considérer que $\mathcal{T}$ est un objet qu'il est naturel de considérer comme la limite d'échelle de l'arbre couvrant uniforme $A_n$. On peut donner un sens précis à cela: on dit que la suite d'espaces métriques compacts $(M_n,d_n)$ converge vers une limite $(M,d)$ au sens de Gromov-Hausdorff s'il existe un espace métrique $(Z,\delta)$ et des isométries \hbox{$\phi_n:M_n\to Z$}, $\phi:M\to Z$ telles que\vspace*{-3pt} $$\delta_H(\phi_n(M_n),\phi(M))\underset{n\to\infty}{\longrightarrow}0\, ,$$ où $\delta_H$ est la distance de Hausdorff associée à $\delta$ entre sous-ensembles fermés de $Z$, donnée par\vspace*{-5pt}\enlargethispage{\baselineskip}% $$\delta_H(A,B)=\max\Big(\sup_{z\in A}d(z,B),\sup_{z\in B}d(z,A)\Big).$$ On peut montrer \cite{burago_course_2001} que cette notion de convergence correspond effectivement à une topologie, et même une métrique, sur l'ensemble des espaces métriques compacts vus à isométrie près. De ce fait, cela a un sens de parler de convergence en loi de variables aléatoires à valeurs dans cet ensemble, muni de la distance de Gromov-Hausdorff. \begin{theorem}[Aldous \cite{aldous_continuum_1991-1}] \label{sec:constr-de-larbre-1} On a que $(A_n,n^{-1/2}d_{A_n})$ converge vers $\TT$ en loi au sens de Gromov-Hausdorff. \end{theorem} Aldous n'a pas énoncé ce résultat en termes de la distance de Gromov-Hausdorff, mais a en fait fourni une représentation (isométrique) de $\TT$ et des $A_n$ renormalisés comme sous-ensembles compacts de $\ell^1(\N)$, de sorte que la convergence a lieu en loi au sens de la distance de Hausdorff: cela implique immédiatement le résultat ci-dessus. Les arguments que nous avons introduits impliquent assez facilement un résultat analogue, si nous remplaçons $A_n$ par $A_n[m]$, et~$\TT$ par le recollement $\TT[m]$ des $m$ premiers segments de la \og line-breaking construction\fg, et ce pour tout $m$ fixé. On voit que toute la difficulté pour passer d'un tel résultat à celui exposé ci-dessus est de montrer qu'on peut trouver $m$ assez grand de sorte que $A_n[m]$ soit assez proche de $A_n$ au sens de la distance de Hausdorff, et ce uniformément en $n$, au sens suivant: pour tout $\eps>0$, $$\lim_{m\to\infty}\limsup_{n\to\infty}\P(\Delta(m,n)>\eps \sqrt{n})=0$$ où $\Delta(m,n)$ est la distance maximale d'un sommet de $A_n$ à un sommet de $A_n[m]$. Nous ne donnons pas ici la preuve de ce résultat technique, qui peut se démontrer de façon analogue aux \emph{inégalités maximales} sur les marches aléatoires. \subsection{Perspectives sur le CRT}\label{sec:perspectives-sur-le} L'arbre brownien est un objet qui intervient un peu partout en probabilités, un peu au même titre que le mouvement brownien. Suivant l'approche originale d'Aldous, nous avons motivé sa définition par une approche algorithmique du problème de l'arbre couvrant uniforme du graphe complet, en insistant sur la \emph{line-breaking construction} dont la description est peu technique --- elle revient après tout à se donner les deux suites infinies $(L_1,L_2,\ldots)$ et $(U_1,U_2,\ldots)$, dont la description est élémentaire. Néanmoins, une définition plus moderne de l'arbre brownien, qui explique son nom, se fait en termes d'un objet bien plus élaboré, que l'on peut définir en termes du mouvement brownien $(B_t,t\geq 0)$ en dimension $1$, et qui consiste à isoler une de ses excursions, c'est-à-dire la restriction de sa trajectoire à une des composantes connexes de l'ouvert $\{t\geq 0:B_t>0\}$. Nous ne rentrerons pas dans les détails de cette construction, issue des idées de Neveu--Pitman \cite{neveu_branching_1989}, Le\,Gall \cite{le_gall_uniform_1993} et Aldous \cite{aldous_continuum_1993}, et qui est plus proche dans l'esprit de l'approche des arbres décrite dans le texte d'Igor Kortchemski (ce~volume, \cite{Kortchemski}). On~pourra aussi consulter \cite{le_gall_random_2005} pour aller plus loin. La première raison qui explique le caractère naturel de l'arbre brownien est le fait qu'il peut se voir comme la limite universelle des processus de branchement, et non seulement la limite de l'arbre couvrant uniforme de $K_n$, qui, rappelons-le, peut se voir comme l'arbre généalogique d'un processus de branchement dont la loi de reproduction est une loi de Poisson (et conditionné à avoir $n$ individus). \begin{theorem}[Aldous \cite{aldous_continuum_1993}] \label{sec:perspectives-sur-le-1} Soit $\mu=(\mu(k),k\geq 0)$ une mesure de probabilités sur $\Z_+$, telle que $$\mu(1)<1,\quad \sum_{k\geq 0}k\mu(k)=1,\quad \mbox{ et }\quad\sigma^2=\sum_{k\geq 0}k^2\mu(k)-1<\infty.$$ Soit $A_n$ l'arbre généalogique d'un processus de branchement de Bienaymé-Galton-Watson de loi de reproduction $\mu$, conditionné à avoir $n$ sommets (on suppose que $n$ est restreint aux entiers tels que le conditionnement a un sens.) Alors $(A_n,(\sigma/\sqrt{n})d_{A_n})$ converge dans le même sens que le théorème \ref{sec:constr-de-larbre-1} vers le CRT $\TT$. \end{theorem} Par ailleurs, le CRT est présent, comme on l'a dit, dans l'étude asymptotique de très nombreux problèmes combinatoires. On pourra citer le problème de parking de Knuth \cite{chassaing_phase_2002}, les arbres sur réseau \cite{derbez_scaling_1998}, les processus de coalescence et de fragmentation \cite{aldous_standard_1998,bertoin_random_2006}, les modèles d'attachement préférentiel, les partitions non croisées, les laminations discrètes du cercle (voir le texte d'Igor Kortchemski \cite{Kortchemski}), et les cartes aléatoires \cite{le_gall_scaling_2012}. C'est peut-être dans ce dernier domaine, qui consiste à étudier de grands graphes aléatoires plongés dans le plan, que l'intervention du CRT est la plus surprenante, puisque ce dernier semble émerger d'une géométrie de type \og champ moyen\fg (dans le graphe complet, tous les sommets sont voisins les uns des autres), alors que les cartes planaires sont des objets intrinsèquement 2-dimensionnels.\enlargethispage{\baselineskip}% \section*{\emph{Intermezzo}: le processus des forêts coalescentes de Pitman}\label{sec:it-intermezzo:-le} Avant de changer de sujet, nous allons présenter une autre preuve de la formule de Cayley, due à Pitman, et qui jette un autre éclairage sur l'arbre couvrant uniforme de $K_n$. Une forêt sur $[n]$ est simplement un sous-graphe $([n],E)$ de $K_n$, qui est sans cycle mais plus nécessairement connexe. Une forêt est dite enracinée si chacune des composantes connexes de cette forêt, qui est évidemment un arbre, est enracinée. On notera que le nombre d'arbres (composantes connexes) d'une forêt $([n],E)$ est donné par $n-\card(E)$, puisque chaque arbre a une arête de moins que de sommets, et tout sommet de $[n]$ est dans un arbre de la forêt. On notera $\mathbf{F}_{n,k}$ l'ensemble des forêts enracinées sur $[n]$ à $k$ arbres. \begin{theorem} \label{sec:it-intermezzo:-le-1} Pour tout $n\geq 1$ et $k\in \{1,2,\ldots,n\}$, on a $$\card(\mathbf{F}_{n,k})=n^{n-k}\, \binom{n-1}{k-1}.$$ \end{theorem} On récupère la formule de Cayley puisque cela donne $$\card(\mathbf{F}_{n,1})=n^{n-1},$$ et $\mathbf{F}_{n,1}$ est l'ensemble des arbres couvrants de $K_n$, enracinés. Comme chaque arbre sur $[n]$ a $n$ choix possibles de racine, donnant autant d'arbres enracinés différents, on a que $\card(\mathbf{F}_{n,1})=n\card(\mathbf{A}_n)$, et l'on récupère le théorème \ref{sec:larbre-couvr-unif-1}. Nous allons montrer ce résultat par une construction combinatoire (et probabiliste) due à Pitman \cite{pitman_coalescent_1999}. Si $\ff\in \mathbf{F}_{n,k}$, soit $\bt_1,\ldots,\bt_k$ les composantes connexes de $\ff$ énumérées de façon arbitraire, les racines correspondantes étant désignées par $r_1,\ldots,r_k$. Supposons que $k\geq 2$. Soit $X$ une variable aléatoire uniforme dans $[n]$, et $R$ une racine uniforme parmi celles des arbres de $\ff$ qui ne contiennent pas $X$: formellement, si $i\in [n]$, on a donc $$\P(R=r_j|X=i)=\frac{1}{k-1}$$ pour tout $j\in \{1,2,\ldots,k\}$ tel que $i\notin V(\bt_j)$. Notons $\ff'$ le graphe obtenu en ajoutant l'arête $\{X,R\}$. Clairement, $\ff'$ est une forêt enracinée à $k-1$ arbres, l'arbre obtenu par la fusion de celui contenant~$X$ et celui contenant $R$ restant naturellement enraciné en la racine du premier (de sorte que $R$ perd son rôle de sommet distingué dans $\ff'$). On note $\mu(\ff,\cdot)$ la loi de la forêt aléatoire $\ff'$ ainsi obtenue, qui est donc une mesure de probabilité sur les forêts enracinées. \begin{propositio}\label{sec:it-intermezzo:-le-3} Supposons que $F_1=\ff_1=([n],\varnothing)$ soit la forêt sur~$[n]$ sans aucune arête (chaque arbre étant donc un singleton, naturellement enraciné). Soit $F_2,\ldots,F_n$ une suite de variables aléatoires obtenues successivement de $F_1$ par le procédé ci-dessus, ainsi, pour tout choix des forêts $\ff_2,\ldots,\ff_n$, on a $$\P(F_2=\ff_2,\ldots,F_n=\ff_n)=\mu(\ff_1,\{\ff_2\})\ldots \mu(\ff_{n-1},\{\ff_n\}),$$ cette probabilité étant nulle si $\ff_k\notin \mathbf{F}_{n-k+1}$ pour un $k\in \{1,2,\ldots,n\}$. Alors pour tout $k\in [n]$, $F_k$ est uniforme parmi $\mathbf{F}_{n-k+1}$. \end{propositio} \begin{proof} Le résultat est évidemment vrai pour $k=1$. Supposons qu'il soit vrai pour l'indice $k-1$. Soit $\ff$ une forêt enracinée à $n-k+1$ arbres. Calculons la probabilité que $F_k=\ff$. Pour que ceci soit vérifié, il faut que $F_{k-1}$ soit égale à une forêt $\ff(e)$ obtenue de $\ff$ en effaçant une arête $e$, et que le procédé décrit ci-dessus ait (ré)inséré cette arête. Notons $\bt(e)$ l'arbre de $\ff$ contenant $e$ et orientons naturellement $\vec{e}=(e_-,e_+)$ vers la racine $r(e)$ de $\bt(e)$, $e_-,e_+\in [n]$ étant donc l'origine et la cible de $e$. Alors $\bt(e)$ privé de $e$ consiste en en deux composantes connexes $\bt_+(e)$ et $\bt_-(e)$, où $\bt_+(e)$ contient $e_+$ et $r(e)$ et reste enraciné en $r(e)$, enraciné, tandis que $\bt_-(e)$ est naturellement enraciné en la source $e_-$ de $\vec{e}$. On a alors $$\P(F_k=\ff)=\sum_{e\in E(\ff)}\P(F_{k-1}=\ff(e),X=e_+,R=e_-),$$ où $X$ est uniforme dans $[n]$ et $R$ est une racine uniforme parmi les $n-k+1$ arbres de $\ff(e)$ ne contenant pas $X$, comme ci-dessus. Ainsi, $$\P(F_k=f)=\sum_{e\in E(\ff)}\P(F_{k-1}=\ff(e))\cdot\frac{1}{n}\cdot\frac{1}{n-k+1},$$ Or, par hypothèse de récurrence, $$\P(F_{k-1}=\ff(e))=1/\card(\mathbf{F}_{n,n-k+2})$$ ne dépend pas de $\ff$ ni de $e$, et on a que $\card(E(\ff))=k-1$ D'où \begin{equation} \label{eq:3} \P(F_k=\ff)=\frac{k-1}{n(n-k+1)\mathbf{F}_{n,n-k+2}}. \end{equation} Cette quantité ne dépend que de $n$ et de $k$, et pas de la valeur de $\ff\in \mathbf{F}_{n,n-k+1}$, et l'on déduit le résultat. \end{proof} La preuve du théorème \ref{sec:it-intermezzo:-le-1} est alors immédiate, puisque \eqref{eq:3} implique $$\card(\mathbf{F}_{n,n-k+1})=\frac{n(n-k+1)}{k-1}\,\card(\mathbf{F}_{n,n-k+2})\, ,$$ et puisque l'on a $\card(\mathbf{F}_{n,n})=1$. On propose enfin l'exercice suivant au lecteur intéressé. Supposons que $(p_1,p_2,\ldots,p_n)\in \R_+^n$ soit un vecteur de probabilités sur $[n]$, c'est-à-dire que $p_1+\ldots+p_n=1$. Effectuons la même construction que ci-dessus, mais supposons que dans la définition de $\mu$, la variable aléatoire $X$ soit choisie selon $p$, c'est-à-dire que $\P(X=i)=p_i$ pour tout $i\in [n]$. En revanche, on suppose toujours que la racine $R$ est choisie uniformément parmi les racines des arbres ne contenant pas $X$. On définit comme avant la suite $F_1,F_2,\ldots,F_n$, mais avec ce nouveau choix de la loi de $X$. On rappelle que chaque arête $e$ d'une forêt enracinée est naturellement orientée vers la racine de l'arbre la contenant, et l'on note $\vec{e}=(e_-,e_+)$. Montrer que l'on a, pour tout $n\geq 1$ et $k\in \{1,2,\ldots,n\}$, et tout $\ff\in \mathbf{F}_{n,n-k+1}$ $$\P(F_k=\ff)=\frac{1}{\binom{n-1}{k-1}}\prod_{e\in E(\ff)}p_{e_+}\, ,$$ ce que l'on peut encore noter, si $c_i(\ff)=\card(\{e\in E(\ff):e_+=i\})$ est le nombre \og d'enfants \fg de $i\in [n]$ dans $\ff$, $$\P(F_k=\ff)=\frac{1}{\binom{n-1}{k-1}}\prod_{i\in [n]}p_i^{c_i(\ff)}\, .$$ En déduire que $$\sum_{\ff\in \mathbf{F}_{n,k}}\prod_{i\in [n]}p_i^{c_i(\ff)}=\binom{n-1}{k-1},$$ et plus généralement que $$\sum_{\ff\in \mathbf{F}_{n,k}}\prod_{i\in [n]}x_i^{c_i(\ff)}=\binom{n-1}{k-1}(x_1+\ldots+x_n)^{n-k},$$ l'égalité ayant lieu dans l'anneau des polynômes $\Z[x_1,\ldots,x_n]$. \section{L'arbre couvrant minimal}\label{sec:larbre-couvr-minim} On s'intéresse à présent à un modèle d'arbre couvrant aléatoire de~$K_n$ complètement différent, et qui correspond à ce que l'on appelle un \og problème d'optimisation combinatoire\fg. Comme tout problème d'optimisation, il s'agit de minimiser une certaine fonction (\og l'énergie\fg) définie sur un espace de configurations. Dans un problème d'optimisation \og combinatoire\fg, on insiste sur le fait que l'espace de configurations est fini, mais, typiquement, beaucoup trop grand pour espérer résoudre le problème par une fouille exhaustive des configurations. Beaucoup de ces problèmes peuvent se poser en termes d'un graphe pondéré $G=(V,E,w)$, c'est-à-dire un graphe muni d'une fonction $w:E\to (0,\infty)$ de poids sur les arêtes du graphe. Parmi ceux-ci: \begin{itemize} \item trouver l'arbre couvrant dont le poids $w(\ba)=\sum_{e\in E(\ba)}w(e)$ est le plus petit possible: c'est le problème de l'arbre couvrant minimal. \item si $(V,E)$ est le graphe complet à $n$ sommets, trouver le cycle hamiltonien (visitant tous les sommets une fois et une seule), disons $C=\nobreak(x_0,x_1,x_2,\ldots,x_n=x_0)$ dont le poids $$w(C)=\sum_{i=0}^{n}w(\{x_{i-1},x_i\})$$ est le plus petit possible: c'est le problème du voyageur de commerce (\emph{travelling salesman problem} en anglais). \end{itemize} Les deux problèmes présentés sont emblématiques et sont situés en quelque sorte aux deux extrémités du spectre en termes de difficulté: le problème du voyageur de commerce est \emph{ NP-hard}, c'est-à-dire \og au moins aussi difficile que tout problème NP\fg\footnote{Un problème NP est un problème dont il est \og facile\fg de vérifier si une solution donnée est effectivement une solution, c'est-à-dire qu'il existe un algorithme effectuant cette vérification en un temps polynomial en la longueur de la solution. En revanche, \emph{trouver} une solution en un temps polynomial est beaucoup plus difficile, et, on le pense, en général impossible: c'est le fameux problème \og P~vs.~NP\fg.}. À l'inverse, le problème de l'arbre couvrant minimal est des plus simples, au sens où il peut se résoudre par des algorithmes \emph{ gloutons}, c'est-à-dire faisant à chaque étape un choix d'optimum \emph{local}, et fonctionnant de plus en temps polynomial. Néanmoins, le problème devient étonnamment riche lorsqu'on y ajoute une part d'aléa. Reprenons le cas d'un graphe général fini connexe $G=(V,E)$. Soit donc $w(e),e\in E$ une famille de poids positifs indexés par les arêtes de $G$. Si $\ba$ est un arbre couvrant de $G$, on note $$w(\ba)=\sum_{e\in E(\ba)}w(e), $$ appelé poids de $\ba$. Par la suite, on supposera \emph{toujours} que les poids sont deux à deux distincts. \begin{definitio} \label{sec:larbre-couvr-minim-1} L'arbre couvrant minimal de $G$ est l'arbre $\ba$ qui réalise le minimum des poids $w(\ba)$. \end{definitio} Il est clair que l'arbre couvrant minimal existe, puisqu'il n'y a qu'un nombre fini d'arbres couvrants. En revanche, on peut se demander s'il est bien défini de façon unique. \begin{propositio} \label{sec:larbre-couvr-minim-2} L'arbre couvrant d'un graphe pondéré dont les poids sont distincts deux à deux est unique. \end{propositio} \begin{proof} Supposons qu'il existe deux arbres couvrants minimaux distincts $\ba,\ba'$. Soit $e$ l'arête de plus petit poids qui est dans l'un mais pas dans l'autre: on suppose sans perte de généralité que~$e$ est une arête de $\ba$. Alors le graphe $\ba'\cup\{e\}$ contient un cycle $C$. Par définition, toutes les arêtes de poids plus petit que $w(e)$ qui sont dans~$\ba'$ sont aussi dans $\ba$, et par conséquent, il existe une arête $e'$ de~$C$ dont le poids est plus grand que celui de $e$ (sinon toutes les arêtes de $C$ seraient dans $\ba$, mais ce dernier ne contient pas de cycle). Fina\-le\-ment, le graphe $(\ba'\cup\{e\})\setminus \{e'\}$ est un arbre couvrant, de~poids $w(\ba')-w(e')+w(e)w(e)$, alors, comme aucune de ces arêtes ne peut être ajoutée avant l'étape $j$ de l'algorithme, on voit que $x$ et $y$ ne peuvent être connectés à cette étape, et donc $e\in E(\ba_m)$. Réciproquement, s'il existe un chemin d'arêtes de $\{e_1,\ldots,e_{j-1}\}$ connectant $x$ et $y$, c'est-à-dire que $x$ et $y$ sont dans la même composante connexe $C$ du graphe sur les arêtes $\{e_1,\ldots,e_{j-1}\}$, alors l'algorithme de Kruskal à l'étape $j-1$ produit un arbre couvrant de $C$, et connecte donc $x$ et $y$. Donc $e$ n'est pas dans $E(\ba_m)$. \end{proof} Un autre algorithme, dû à Prim, consiste à ajouter l'arête de plus petit poids disponible, mais uniquement parmi celles incidentes à une \og graine\fg fixée au départ. On fixe donc un sommet $v_0\in V$. \subsubsection*{Algorithme de Prim} \begin{enumerate} \item Initialiser $S=\{v_0\}$ et $Z=\varnothing$ et $I=1$. \item Tant que $S\neq V$ faire \begin{itemize} \item trouver l'arête $e=\{x,y\}$ de poids minimal avec $x\in S$ et $y\in V\setminus S$ \item $S\leftarrow S\cup\{y\}$ et $Z\leftarrow Z\cup \{e\}$ \end{itemize} \item Retourner $Z$. \end{enumerate} Nous laissons au lecteur le soin de démontrer que l'algorithme produit effectivement l'arbre couvrant minimal. \subsection{Le \og théorème \texorpdfstring{$\zeta(3)$}{z3}\fg de Frieze}\label{sec:le-poids-total} Supposons maintenant que les poids $w(e),e\in E(K_n)$ soient des variables aléatoires i.i.d.\ de loi exponentielle de paramètre $1$: $$\P(w(e)>r)=e^{-r}\quad \text{pour tout $r\geq 0$}.$$ La loi exponentielle étant à densité, il est effectivement vérifié presque sûrement que les poids sont deux à deux distincts, comme nous l'exigeons. Tacitement, on travaillera systématiquement en restriction à cet événement de probabilité $1$. On notera $M_n$ l'arbre couvrant minimal associé à la suite des poids ci-dessus. On peut poser au moins deux questions naturelles au sujet de cet arbre: \begin{itemize} \item quelle est la géométrie asymptotique de $M_n$ lorsque $n\to\infty$, au sens de la première partie (convergence de Gromov-Hausdorff) \item quel est le poids de $M_n$? \end{itemize} On connaît essentiellement la réponse à ces deux questions, et nous allons évoquer la seconde avec quelque détail. Le résultat suivant est dû à Frieze en 1985 \cite{frieze_value_1985}. \begin{theorem}\label{sec:le-theoreme-zeta3} On a $\E[w(M_n)]\to \zeta(3)$ lorsque $n\to\infty$, et de plus, pour tout $\eps>0$, on a que $$\P(|w(M_n)-\zeta(3)|>\eps)\underset{n\to\infty}{\longrightarrow}0.$$ \end{theorem} Il peut paraître surprenant de voir apparaître la quantité $\zeta(3)$ dans ce contexte. Mais la première surprise vient certainement du fait qu'il n'y a aucune renormalisation dans la convergence, alors que les poids sont des variables aléatoires exponentielles, et que l'arbre minimal contient $n-1$ arêtes (comme tout arbre couvrant de $K_n$). Néanmoins, le mystère est dissipé par le résultat suivant, qui sera utile par la suite. \begin{propositio} \label{sec:le-theoreme-zeta3-1} Soit $\be_1,\be_2,\ldots,\be_n$ des variables aléatoires indépendantes exponentielles de paramètre $1$. Notons $\be_{(1)}<\be_{(2)}<\ldots<\be_{(n)}$ le réordonnement croissant de $\{\be_1,\ldots,\be_n\}$. Alors $(\be_{(1)},\ldots,\be_{(n)})$ a même loi que la suite des sommes partielles renormalisées $$\sum_{i=1}^j\frac{\be_i}{n-i+1},\qquad 1\leq j\leq n$$ \end{propositio} \begin{proof} Soit $f:\R^n\to \R_+$ une fonction mesurable. Alors \begin{multline*} \E[f(\be_{(1)},\ldots,\be_{(n)})]\\[-6pt] =n!\int_{0\leq x_1\leq \ldots\leq x_n}\d x_1\ldots \d x_n e^{-(x_1+\ldots+x_n)}f(x_1,\ldots,x_n). \end{multline*} On fait le changement de variables $y_i=x_i-x_{i-1},1\leq i\leq n$ (avec la convention $x_0=0$), ce qui donne \begin{multline*} \E[f(\be_{(1)},\ldots,\be_{(n)})]\\[-3pt] =n!\int_{R_+^n}\d y_1\ldots \d y_n e^{-\sum_{i=1}^n (n-i+1)y_i} f(y_1,y_1+y_2,\ldots,y_1+\ldots+y_n), \end{multline*} et l'on conclut en utilisant le fait que $\be_1/k$ a une loi à densité $ke^{-kx}\d x\ind_{\{x\geq 0\}}$. \end{proof} On voit en particulier que tout sommet du graphe complet, qui est incident à $n-1$ arêtes, est typiquement incident à au moins une arête de poids $O(1/n)$, et ce sont certainement ces très petites arêtes qui seront préférées par l'algorithme de Kruskal. Ceci explique l'absence de renormalisation dans le théorème de Frieze. Nous allons donner l'idée d'une approche introduite par Aldous et Steele \cite{aldous_asymptotics_1992-1,aldous_objective_2004} pour calculer la limite de $\E[w(M_n)]$. Cette méthode, appelée la \emph{ méthode objective}, consiste à construire une limite (une sorte de version $n=\infty$) des objets étudiés. L'approche est longue à mettre en place, mais elle introduit en chemin des objets fondamentaux qui permettent d'obtenir une meilleure intuition du résultat et des objets avec lesquels on travaille. Nous insisterons davantage sur ces objets en eux-mêmes que sur les détails de la preuve. Pour mettre en action la méthode objective, on est amené à étudier les propriétés \emph{locales} de l'arbre couvrant du graphe complet, c'est-à-dire des propriétés que l'on peut décrire en étudiant seulement un voisinage d'une racine choisie au hasard. Pourquoi une telle approche a-t-elle une chance de marcher? Constatons que \begin{align*} \E[w(M_n)]&=\E\biggl[\sum_{e\in E(M_n)}w(e)\biggr]\\ &=\frac{1}{2}\E\biggl[\sum_{x\in [n]}\sum_{y\in [n]}w(\{x,y\})\ind_{\{\{x,y\}\in E(M_n)\}}\biggr]\\ &=\frac{1}{2n}\sum_{x\in [n]}\E\biggl[\sum_{y:\{x,y\}\in E(M_n)}nw(\{x,y\})\biggr] \\ &=\frac{1}{2}\E\biggl[\sum_{y:\{x_*,y\}\in E(M_n)} nw(\{x_*,y\})\biggr], \end{align*} où $x_*$ est une variable aléatoire uniforme dans $[n]$, indépendante de $w(e)$, $e\in E(K_n)$. Nous avons donc exprimé l'espérance de la variable \og globale\fg $w(M_n)$ comme celle de la variable \og locale\fg (autour d'un sommet $x_*$ choisi au hasard) $\sum_{y\sim x_*}nw(\{x_*,y\})$. L'idée est alors de trouver une forme de limite lorsque $n\to\infty$ de cette quantité. En~fait, pour des raisons de symétrie, on peut remplacer $x_*$ par $1$, et~nous sommes amenés à étudier la convergence en loi de \begin{equation} \label{eq:1} \frac{1}{2}\sum_{y:\{1,y\}\in E(M_n)} nw(\{1,y\}). \end{equation} Remarquons que la seule convergence en loi d'une suite de variables aléatoires $X_n$ positives ne permet pas de montrer la convergence de l'espérance: il faut pour cela montrer un résultat d'uniforme intégrabilité, c'est-à-dire que $\sup_n\E[X_n\ind_{\{X_n>a\}}]\to 0$ lorsque $a\to\infty$. Nous admettrons que ceci est vérifié pour les variables définies en \eqref{eq:1}. \subsection{La convergence locale}\label{sec:la-conv-locale} La méthode objective utilise comme principal outil la notion de \emph{ convergence locale} d'une suite de graphe, que l'on peut exprimer ainsi: on dit que la suite de graphes $G_n$ à $n$ sommets converge loca\-le\-ment vers un graphe enraciné infini aléatoire $(G,o)$ si, en choisissant~$o_n$ uniforme parmi les sommets de $G$, on a que pour tout $r$, la~boule de rayon $r$ centrée en $o_n$ dans $G_n$ converge en loi vers la boule de centre $o$ et de rayon $r$ dans $G$ (pour la distance de graphe, et on voit $B_r(G,o)$ comme un graphe en y adjoignant toutes les arêtes de~$G$ \hbox{reliant} deux sommets à distance au plus $r$ de $o$), c'est-à-dire que pour tout graphe enraciné $(g,\rho)$ on a $$\P(B_r(G_n,o_n)\approx (g,\rho))\underset{n\to\infty}{\longrightarrow} \P(B_r(G,o)\approx (g,\rho)),$$ où la notation $\approx$ signifie que les graphes (enracinés) de part et d'autre sont isomorphes. On peut se demander ce que signifie un \og graphe infini aléatoire\fg, puisque cela nécessite de préciser une notion de tribu: en fait, il est facile de voir que la convergence ci-dessus correspond à la convergence en loi pour une métrique sur les graphes connexes enracinés ayant une infinité dénombrable de sommets, par exemple $$d_{\mathrm{loc}}((G,o),(G',o'))=\left(1+\sup\{r\!\geq\! 0:B_r(G,o)\approx B_r(G',o')\}+1\right)^{-1}\!.$$ On considère la tribu borélienne associée. Si maintenant $G=(V,E,w)$ est pondéré, on peut modifier la définition précédente, en remplaçant les boules combinatoires de rayon $r$ par les boules de rayon $r$ dans la métrique induite par $w$: $d_w(x,y)=\inf\{\sum_{e\in \gamma:x\to y} w(e)\}$ où l'infimum est pris sur tous les chemins de $x$ à $y$. On notera $B_r(G,o,w)$ la boule de rayon $r$ pour cette distance, ce que l'on voit comme un graphe (non pondéré, mais que l'on peut munir naturellement de la restriction de $w$). On dit que la suite de graphes pondérés enracinés $(G_n,o_n,w_n)$ converge vers le graphe infini enraciné $(G=(V,E),o,w)$ si pour tout $r\notin\{d_w(o,v):v\in V\}$, et pour tout $n$ assez grand, il existe un isomorphisme de graphes $\phi_{n,r}:B_r(G,o)\to B_r(G_n,o_n)$, tel que $w_n(\phi_{n,r}(e))$ converge vers $w(e)$ pour tout $e$ arête de $B_r(G,o,w)$. La~raison pour laquelle on exclut le cas où $r=d_w(o,v)$ pour un $v\in V$ est que les boules de rayon $s$ proche de $r$ peuvent inclure ou exclure~$v$ selon que $sr$: on ne peut donc pas exiger d'une suite de graphes approchant $G$ que ses boules de rayon $r$ soient toutes isomorphes. Ici encore on peut munir l'ensemble des graphes enracinés pondérés infinis dénombrables d'une métrique correspondant à cette notion de convergence, par exemple\vspace*{-5pt}\enlargethispage{\baselineskip}% \begin{multline*} d_{\mathrm{loc}}((G,o,w),(G',o',w'))\\[-5pt] =\int_0^\infty \d r e^{-r}\Bigl((\inf \Bigl\{\sup_{e\in E(B_r(G,o,w))}|w(e)-w'(\phi(e))|,\phi\in \mathrm{Isom}_r \Bigr\}\wedge 1 \Bigr), \end{multline*} où $\mathrm{Isom}_r$ est l'ensemble des isomorphismes de graphes entre\vspace*{-5pt} $$B_r(G,o,w)\quad\text{et}\quad B_r(G',o',w'),$$ ce dernier pouvant être vide. \begin{definitio} \label{sec:la-conv-locale-1} On dit alors que la suite de graphes pondérés (éventuellement aléatoires) $(G_n,w_n),n\geq 1$, tel que $G_n$ a $n$ sommets, converge localement vers un graphe infini pondéré enraciné aléatoire $(G,o,w)$ si, $o_n$ étant un sommet choisi uniformément dans $V(G_n)$ conditionnellement à $G_n$, on a que $(G_n,o_n,w_n)$ converge en loi vers $(G,o,w)$ pour la distance $d_{\mathrm{loc}}$. \end{definitio} La notion de convergence locale a été formalisée par Benjamini et Schramm \cite{benjamini_recurrence_2001}, même si elle apparaît en germe dans des travaux antérieurs. Son importance dans l'étude de grands graphes aléatoires est cruciale. \subsection{Le graphe complet pondéré vu comme un arbre}\label{sec:le-graphe-complet} Revenons à notre but de décrire un espace limite au graphe complet pondéré. L'objet limite se décrit de la façon suivante. Notons $\mathcal{U}$ l'ensemble des mots d'entiers\vspace*{-5pt} $$\mathcal{U}=\bigcup_{n\geq 0}\N^n,$$ où $\N^0=\{\varnothing\}$. On notera $\mathcal{U}^*=\mathcal{U}\setminus\{\varnothing\}$. On peut interpréter $\mathcal{U}$ comme un arbre infini enraciné en $\varnothing$, et où le sommet correspondant au mot $(u_1,u_2,\ldots,u_n)$, souvent noté $u_1u_2\ldots u_n$, est vu comme le $u_n$\nobreakdash-ième enfant du mot $(u_1,\ldots,u_{n-1})$. En tant que graphe, $\mathcal{U}$ est donc muni des arêtes $\{u,uk\}$ avec $u\in \mathcal{U}$ et $k\geq 1$. De façon équivalente, l'ensemble des arêtes s'identifie canoniquement à $\mathcal{U}^*$. Donnons-nous à présent une famille $(\xi_u,u\in \mathcal{U}^*)$ de variables aléatoires, de telle sorte que pour tout $u\in \mathcal{U}$, la famille $(\xi_{uk},k\geq 1)$ ait même loi qu'un processus de Poisson $(\eta_1,\eta_2,\ldots)$ tel qu'introduit au paragraphe \ref{sec:geom-asympt-larbre}. On demande de plus que ces familles de variables aléatoires soient indépendantes entre elles. On interprète $(\xi_u,u\in \mathcal{U})$ comme des longueurs d'arêtes, au sens où $\xi_{uk}$ est la longueur de l'arête $e=\{u,uk\}$, et l'on notera indifféremment $\xi(e)$ cette quantité. Le graphe pondéré enraciné $\bT=(\mathcal{U},\varnothing,\xi)$ a été baptisé \emph{Poisson weighted infinite tree} par Aldous, ce qu'on pourrait traduire par \emph{arbre infini avec pondération poissonnienne}. L'acronyme, PWIT, est semble-t-il une facétie de l'auteur. \begin{theorem} \label{sec:le-graphe-complet-1} La limite locale du graphe complet $(K_n,nw)$ pondéré par des variables exponentielles indépendantes de paramètre $1$, renormalisées par $n$, est le PWIT. \end{theorem} Une chose remarquable est que ce théorème reste valable pour des poids i.i.d.\ qui suivent une loi admettant une densité $f$ continue dans un voisinage à droite de $0$, avec $f(0)=1$ (ou $f(0)>0$, mais cela nécessite une renormalisation par une constante multiplicative dans l'énoncé). Nous ne donnerons pas une preuve complète de ce théorème, mais nous contenterons de quelques remarques élémentaires. Tout d'abord, pour des raisons évidentes de symétrie, le choix de la racine $o_n$ n'importe pas, et peut être aussi bien choisi comme étant le sommet $1$; ce que nous supposerons. \subsubsection*{Le PWIT est bien un graphe localement fini} Nous utiliserons ici et par la suite le fait suivant. \begin{lemma} \label{sec:le-graphe-complet-2} Si $\be_1,\ldots,\be_k$ sont des variables aléatoires exponentielles de paramètre $1$ indépendantes, alors leur somme $\be_1+\ldots+\be_k$ a pour loi la loi $Gamma(k)$ dont la densité par rapport à la mesure de Lebesgue $$\frac{x^{k-1}e^{-x}}{k!}\, \d x\, \ind_{\{x\geq 0\}}.$$ \end{lemma} La preuve est une application simple de la formule de changement de variables, et est omise. Soit $u=u_1u_2\ldots u_n\in \mathcal{U}$ un mot. La loi de $d_\xi(u,\varnothing)$ celle de la somme des variables $\xi_v$ où $v$ décrit l'ensemble des préfixes de $u$, et ces variables aléatoires sont indépendantes, respectivement de lois $\mathrm{Gamma}(u_i),1\leq i\leq n$. Leur somme est donc de loi $\mathrm{Gamma}(|u|_1)$ par une application du lemme \ref{sec:le-graphe-complet-2}. Or si $X$ suit une loi $\mathrm{Gamma}(k)$ on a $$P(Xw(e)$. Ou autrement dit, si les extrémités de $e$ deviennent déconnectées si l'on enlève toutes les arêtes de poids $\geq w(e)$. Cette remarque permet de définir l'analogue de l'arbre couvrant minimal dans le PWIT: on voudrait dire que l'arête $e=\{u,uk\}$ est dans la \emph{forêt couvrante minimale} $F(\bT)$ si $u$ et $uk$ ne sont pas connectés dans le sous-graphe du PWIT obtenu en retirant toutes les arêtes de poids $\geq \xi(uk)$. Évidemment, cela est encore vide de sens, puisque le PWIT est un arbre, et donc deux sommets ne peuvent être connectés que par un seul chemin. Néanmoins, on peut rattraper cela en disant que les sommets $u$ et $uk$ ne sont pas connectés (hors de l'arête $e$) si l'une au moins des deux composantes connexes de ces deux sommets, formée des arêtes du PWIT de poids $<\xi(e)$ est finie. À l'inverse, on dira que l'arête $e$ n'est pas dans $F(\bT)$ s'il existe deux chemins infinis issus de $u$ et $uk$ et n'empruntant que des arêtes de poids $<\xi(e)$, l'idée étant que dans ce cas, $u$ et $uk$ sont connectés \og à l'infini\fg par un chemin de tels arêtes. Nous allons expliquer pourquoi cette idée a une chance de fonctionner, mais tout d'abord nous donnons le résultat. \begin{definitio} \label{sec:larbre-minimal-vu-1} Soit $\bT=(\mathcal{U},\varnothing,\xi)$ le PWIT. La forêt minimale couvrante $F(\bT)$ de $\bT$ est le sous-graphe de $\bT$ défini par les arêtes $e=\{u,v\}\in E(\bT)$ telles que l'une au moins des deux composantes connexes du sous graphe $(V(\bT),\{e'\in E(\bT):\xi(e')<\xi(e)\})$ contenant~$u$ et~$v$ est finie. \end{definitio} On a alors le résultat suivant. \begin{theorem} \label{sec:larbre-minimal-vu-2} On a la convergence locale suivante\enlargethispage{\baselineskip}% $$(K_n,M_n,nw)\underset{n\to\infty}{\longrightarrow}(\bT,F(\bT),\xi)$$ \end{theorem} Il faut expliquer ce qu'on entend dans le théorème précédent par la convergence jointe de $K_n$ et sont arbre couvrant minimal $M_n$. Ce~dernier est un sous-graphe de $K_n$, il est donc immédiat d'étendre la \hbox{notion} de convergence locale à $(K_n,M_n,w)$, si l'on voit par exemple~$M_n$ comme une fonction de marques $m:E(K_n)\to \{0,1\}$, les pondérations $w$ servant toujours à définir les distances: dans la définition ci-dessus de la distance locale, il faut se restreindre aux isomorphismes $\phi:B_r(G,o,w)\to B_r(G',o',w')$ qui préservent les marques: $m(e)=m'(\phi(e))$ pour tout $e\in E(B_r(G,o,w))$. Le théorème \ref{sec:larbre-minimal-vu-2} sera admis. On peut penser qu'il est un peu mira\-cu\-leux que deux sommets voisins incidents à l'arête $e$ du PWIT, parce qu'ils sont reliés à l'infini par des chemins n'empruntant pas~$e$ faits d'arêtes de poids $<\xi(e)$, peuvent effectivement être interprétés comme étant reliés ensemble. La raison est que, s'il existe un tel chemin, il en existe en fait énormément, et ces chemins envahissent littéralement le graphe. On a en effet le résultat suivant. \begin{lemma} \label{sec:larbre-minimal-vu-3} La composante connexe $\bT_\lambda$ du sous-graphe $$(V(\bT),\{e\in E(\bT):\xi(e)<\lambda\})$$ contenant $\varnothing$ est l'arbre généalogique d'un processus de branchement de loi de reproduction Poisson de moyenne $\lambda$. \end{lemma} \begin{proof} La propriété fondamentale du processus de Poisson, encore noté $(\eta_1,\eta_2,\ldots)$ est que $N_\lambda=\sup\{i\geq 0:\eta_i<\lambda\}$ (avec la convention $\eta_0=0$) est une variable aléatoire de Poisson de paramètre~$\lambda$. En effet, pour $n\geq 0$, on a \begin{align*} \P(&N_\lambda=n)=\P(\eta_n\leq \lambda< \eta_{n+1})\\ &=\int_{x_1+\ldots+x_n\leq \lambda\lambda}\d y\, e^{-y}\int_{y_1<\ldots0$ est une variable aléatoire. On voit donc qu'il existe une quantité de chemins vers l'infini qui croît de façon exponentielle avec la génération: en fait, si l'approximation de $K_n$ par le PWIT est bonne jusqu'à une hauteur de l'ordre de $c\ln(n)$ pour une constante $c>0$, on voit qu'une proportion positive des sommets de $K_n$ est reliée aux sommets correspondant à $u$ et $uk$ par des arêtes de poids $<\xi(e)$. Il devient alors plausible que l'on puisse en fait relier ces sommets dans $K_n$ par un tel chemin. Du théorème \ref{sec:larbre-minimal-vu-2} on en déduit la convergence en loi $$\frac{1}{2}\sum_{i:\{1,i\}\in E(M_n)}nw(\{1,i\})\underset{n\to\infty}{\longrightarrow}\frac{1}{2}\sum_{i:\{\varnothing,i\}\in F(\bT)}\xi(i),$$ où la quantité à gauche est celle qui apparaît en \eqref{eq:1}. Comme nous avons admis que nous avions aussi la convergence des espérances, il~nous reste à calculer\vspace*{-3pt} $$ \E\biggl[\sum_{i:\{\varnothing,i\}\in F(\bT)}\xi(i) \biggr]=\E \biggl[\sum_{i\geq 1}\xi(i)\ind_{\{|\bT_{\xi(i)}|<\infty\text{ ou }|\bT^i_{\xi(i)}|<\infty\}} \biggr],$$ où $\bT_{\xi(i)}$ est $\bT_\lambda$ pour la valeur $\lambda=\xi(i)$, et $\bT^i_{\xi(i)}$ est la composante connexe contenant le sommet $i\in \mathcal{U}$ de $\{e\in E(\bT):\xi(e)<\xi(i)\}$. \hbox{Notons} que les événements $\{|\bT^i_{\xi(i)}|=\infty\}$ et $\{\bT_{\xi(i)}=\infty\}$ sont indépendants conditionnellement à $\{\xi(u):u\notin i\mathcal{U}^*\}$ où $u$ décrit tous les sommets du PWIT, à l'exception des descendants stricts de $i$, car ils font intervenir des poids d'arêtes sur des générations disjointes du PWIT (à l'exception du poids $\xi(i)$ de l'arête $\{\varnothing,i\}$), et de plus la probabilité conditionnelle du premier est $\P(|\bT^i_{\xi(i)}|=\infty\, |\, \xi(u),u\notin i\mathcal{U}^*)=q(\xi(i))$, où $q(\lambda)$, défini au-dessus, est la probabilité de non-extinction de $\bT_\lambda$. On a donc\vspace*{-3pt} \begin{equation} \label{eq:2} \E \biggl[\sum_{i:\{\varnothing,i\}\in F(\bT)}\xi(i) \biggr]= \E \biggl[\sum_{i\geq 1}\xi(i)\left(1-q(\xi(i))\ind_{\{|\bT_{\xi(i)}|=\infty\}}\right) \biggr]. \end{equation} Nous utilisons une dernière propriété des processus de Poisson: qui est que\vspace*{-3pt} $$\E \biggl[\sum_{i\geq 1}H(\eta_i,(\eta_j,j\geq 1,j\neq i)) \biggr]=\int_0^\infty\d \lambda \, \E[H(\lambda,(\eta_j,j\geq 1))],$$ où $H$ est une fonction mesurable positive (pouvant aussi être fonction de variables aléatoires indépendantes de $\eta_1,\eta_2,\ldots$). On laisse au lecteur le soin de montrer cette propriété dans le cas où $H(\lambda,(t_j,j\geq 1))$ est de la forme $f(\lambda)g(t_1,\ldots,t_k)$, le résultat s'en déduisant par un argument de classe monotone. L'application de cette formule à \eqref{eq:2} donne\vspace*{-3pt} \begin{align*} \frac{1}{2}\E \biggl[\sum_{i:\{\varnothing,i\}\in F(\bT)}\xi(i) \biggr]&=\int_0^\infty \lambda(1-\P(|\bT_\lambda|=\infty)q(\lambda))\\[-5pt] &=\frac{1}{2}\int_0^\infty \lambda(1-q(\lambda)^2)\\ &=\frac{1}{2}\int_1^\infty\lambda^2 q(\lambda)q'(\lambda)\d \lambda \end{align*} où l'on a utilisé une intégration par parties, puis le fait que $q$ est constante égale à $1$ sur $[0,1]$. Comme on a $$\exp(-\lambda q(\lambda))=(1-q(\lambda)),$$ soit $\lambda=-\ln(1-q(\lambda))/q(\lambda)$, on peut faire le changement de variables $q=q(\lambda)$, ce qui donne, avec un dernier changement de variables $u=-\log(1-q)$, \begin{align*} \frac{1}{2}\int_1^\infty\lambda^2 q(\lambda)q'(\lambda)\d \lambda&=\int_0^1\frac{\log^2(1-q)}{2q}\d q =\int_0^1 \frac{u^2}{2}\frac{e^{-u}}{1-e^{-u}}\d u\\ &=\int_0^1 \frac{u^2}{2}\sum_{k\geq 1}e^{-ku}\d u=\sum_{k\geq 1}\frac{1}{k^3}=\zeta(3). \end{align*} C'est ce qu'on voulait! \subsection{Géométrie asymptotique}\label{sec:geom-asympt-1} On peut légitimement se poser la question de la convergence au sens de Gromov-Hausdorff de l'arbre minimal $M_n$, après renormalisation idoine. C'est l'objet d'un résultat récent \cite{addario-berry_scaling_2013}. \begin{theorem} \label{sec:geom-asympt-3} La suite $(M_n,n^{-1/3}d_{M_n})$ converge en loi au sens de Gromov-Hausdorff vers une limite $\mathcal{M}$, qui est un $\R$-arbre, dont la dimension de Minkowski égale $3$ presque sûrement. \end{theorem} On voit en particulier que la géométrie asymptotique de $M_n$ est très différente de celle du CRT, dont la dimension (de Hausdorff, ou de Minkowski) est $2$. En fait, on peut décrire la limite $\mathcal{M}$ en termes d'une opération un peu sophistiquée sur le CRT, mais nous n'entrerons pas dans ces considérations. \begin{figure}[htb] \centering \includegraphics[scale=.3]{mst3000ColorC} \caption{Une simulation de l'arbre couvrant minimal $M_n$ avec $n=3000$, par Louigi Addario-Berry} \label{fig:MST} \end{figure} Ce résultat fait suite aux importants travaux \cite{addario-berry_continuum_2012,addario-berry_critical_2010} dont l'objet est de décrire la limite d'échelle du \emph{graphe d'Erd\H{o}s-Rényi} \cite{erdos_evolution_1960} au paramètre critique, qui consiste à garder chaque arête du graphe complet avec probabilité $p$, et à enlever les autres. Les composantes connexes de ce graphe, lorsque $p$ est de l'ordre de $1/n$, sont étroitement liées au CRT, tandis que l'émergence de ces composantes alors que $p$ augmente est lié au déroulement de l'algorithme de \hbox{Kruskal}. Le modèle du graphe d'Erd\H{o}s-Rényi est un des modèles aléatoires les plus étudiés et utilisés dans la littérature scientifique, et il mériterait un ou plusieurs cours à lui tout seul. On consultera par exemple le très beau livre de van der Hofstad, \emph{Random graphs and complex networks}, encore en préparation mais disponible en ligne, ou \cite{addario-berry_critical_2010} pour une mise en perspective (plus ardue) de certaines des approches présentées dans ces notes. \backmatter \bibliographystyle{jepalpha+eid} \bibliography{xups16-02} \end{document}