\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 $a<b$. Ainsi, la marche aléatoire $S_n$ est \og typiquement
\fg de l'ordre de $\sqrt{n}$ au sens où la probabilité que $S_n$
n'est pas dans $[-K\sqrt{n},K\sqrt{n}]$ tend vers $0$ lorsque
$K\to\infty$ uniformément en $n$.

\subsubsection{L'algorithme d'Aldous-Broder}

Pour pouvoir répondre à ce genre de question pour un arbre uniforme,
il ne suffit évidemment pas de connaître le nombre de possibilités,
comme il serait insuffisant dans le cas de la marche aléatoire de
savoir que $S_n$ est déterminée par les $2^n$ valeurs que peut prendre
$(X_1,X_2,\ldots,X_n)$. On est donc amené à essayer de décrire la
structure d'un arbre couvrant uniforme, et pour cela on va avoir
recours à un algorithme permettant d'en simuler un. Ce dernier a été
proposé par Aldous \cite{aldous_random_1990} et Broder au début des
années 1990.

\begin{theorem}\label{sec:simulation-2}
Soit $v_0\in V$ fixé. On se donne une
marche aléatoire $X_0=v_0,X_1,X_2,\ldots$ au plus proche voisin dans $G$, issue
de $v_0$, c'est-à-dire que pour tout $x_0=v_0,x_1,\ldots,x_i$ dans
$V$,
$$\P(X_{i+1}=y|X_0=x_0,X_1=x_1,\ldots,X_i=x_i)=\frac{1}{\deg(x_i)}\mathbf{1}_{\{y\sim
x_i\}},$$ dès lors que l'événement par lequel on conditionne est de
probabilité non nulle. Soit $T_v=\inf\{i\geq 0:X_i=v\}$ le premier
temps d'atteinte de $v\in V$ par cette marche. Alors le graphe
aléatoire $A=(V,\{\{X_{T_v-1},X_{T_v}\}:v\in V\setminus \{v_0\}\})$,
vu comme enraciné en $v_0$, est un arbre couvrant uniforme parmi
l'ensemble $\bA_G(v_0)$ des arbres couvrants de $G$ enracinés en
$v_0$.
\end{theorem}

On notera que les temps $T_v$ sont tous finis presque sûrement, par un
résultat classique sur les chaînes de Markov, dont nous n'aurons pas
besoin explicitement dans ces notes et que nous ne discuterons pas
davantage. Il faut prendre garde dans l'énoncé précédent qu'il n'est
pas vrai en général que le graphe $A$ \og dé-raciné \fg est uniforme
dans~$\mathbf{A}_G$. Cela devient néanmoins vrai si l'on a aussi
choisi le sommet~$v_0$ aléatoirement, selon la loi
$\pi(v)=\deg(v)/\sum_{w\in V}\deg(v)$ sur~$V$.

Donnons un point de vue un peu différent sur ce résultat, qui met en
évidence son caractère algorithmique.

\subsubsection*{Algorithme d'Aldous-Broder}
\begin{enumerate}
\item Initialiser $S=\{v_0\}$, $Z=\varnothing$, $I=0$, $y=v_0$.
\item Tant que $S\neq V$, faire
\begin{itemize}
\item $I\leftarrow I+1$,
\item si $X_I\notin S$ alors $Z\leftarrow Z\cup \{\{y,X_I\}\}$,
\item $S\leftarrow S\cup \{X_I\}$
\item $y\leftarrow X_I$
\end{itemize}
\item Retourner $Z$.
\end{enumerate}

Autrement dit, on construit un sous-graphe de $G$ en traçant les
arêtes visitées par la marche aléatoire les unes après les autres,
sauf aux moments où l'on retourne sur un sommet déjà visité auparavant: en de
tels instants, on se place en ce sommet, mais sans ajouter l'arête qui y
mène. L'algorithme termine pour la même raison que précédemment, au
premier instant $C$ où $\{v_0,X_1,X_2,\ldots,X_C\}=V$ (ce temps~$C$
est appelé \emph{temps de couverture} issu de $v_0$).

Notons $R_0=0$, et par
récurrence, pour tout $i\geq 0$, soit
$$R_{i+1}=\inf\{j>i: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 <i_r\leq
n}\P(A_{i_1}\cap\ldots\cap A_{i_r})\\
&=\sum_{r=0}^n(-1)^r\Big(\begin{matrix}{n}\\{r}\end{matrix}\Big) \Big(1-\frac{r}{n} \Big)^k.
\end{align*}
Prenons maintenant $k=k_n=\lfloor n\ln(n)+nx\rfloor$ avec $x\in \R$. Alors
pour tout $r\geq 0$, on a lorsque $n\to\infty$
$$\Big(1-\frac{r}{n} \Big)^k=\exp(k\ln(1-r/n))=n^{-r}e^{-rx}(1-o(1))\,
,$$ où le signe $-$ devant $o(1)$ est là pour insister sur le fait que cette
quantité positive est majorée par $n^{-r}e^{-rx}$ pour tout $n$, et
donc
$$\P(C_n\leq n\ln
n+nx)=\sum_{r=0}^n\frac{(-1)^r}{r!}\frac{n!}{(n-r!)}n^{-r}e^{-rx}(1-o(1))\,
.$$
Comme $n!/(n-r)!= n^r(1-o(1))$, on déduit aisément
$$\P \Big(\frac{C_n-n\ln n}{n}\leq x \Big)\underset{n\to\infty}{\longrightarrow}\sum_{r\geq 0}\frac{(-1)^r}{r!}e^{-rx}=\exp(-e^{-x}).$$
Ainsi, la suite de variables aléatoires $(C_n-n\ln n)/n,n\geq 1$
converge en loi vers la \emph{loi de Gumbel} dont la fonction de
répartition est $$\P(\mathcal{G}\leq x)=\exp(-e^{-x}).$$ Cette loi
apparaît naturellement dans des problèmes d'étude de maxima de
variables aléatoires indépendantes (valeurs extrêmes). Noter la
dissymétrie marquée de cette fonction, puisque l'on a
$$\exp(-e^{-x})=1-e^{-x}(1+o(1))$$ lorsque $x\to\infty$, tandis que
$\exp(-e^{-x})$ tend vers $0$ \og doublement exponentiellement \fg
lorsque $x\to-\infty$. Autrement dit, s'il est plausible que la
collection soit complète au temps $n\ln n+3n$ (probabilité de l'ordre
de $1-e^{-3}$), il est en revanche franchement invraisemblable qu'elle
le soit au temps $n\ln n-3n$ (probabilité de l'ordre de
$\exp(-e^{3})$). On~parle d'une \og transition abrupte \fg (\emph{ cutoff} en anglais).

\begin{figure}
\centering
\includegraphics[scale=.45]{gumbel}
\caption{La fonction de répartition et la densité de la loi de Gumbel}
\label{fig:gumbel}
\end{figure}

L'algorithme d'Aldous-Broder n'est pas le meilleur connu en termes de
rapidité d'exécution: un autre algorithme également très simple, dit
\emph{algorithme de Wilson}, le surpasse de ce point de vue
\cite{wilson_generating_1996}. Néanmoins, pour notre propos, c'est l'algorithme
d'Aldous-Broder qui donne le point de vue le plus simple sur l'arbre
couvrant uniforme.

\subsection{Une autre interprétation}\label{sec:une-autre-interpr}

Comme nous l'avons dit, l'arbre couvrant uniforme du graphe complet
que nous avons décrit ci-dessus n'est rien d'autre qu'un arbre
uniforme parmi les $n^{n-2}$ arbres possibles avec sommets étiquetés
par~$1,2,\ldots,n$. Il y a d'autres manières que l'algorithme
d'Aldous-Broder d'envisager cet arbre d'un point de vue probabiliste,
dont le recours aux arbres associés aux processus de branchement
(Bienaymé-Galton-Watson). Rappelons que si $\mu$ est une mesure de
probabilités sur $\N$, que l'on voit comme la loi de reproduction pour
des individus d'une population asexuée, on peut lui associer un
processus dans lequel chaque individu donne naissance indépendamment
des autres à un nombre d'individus aléatoire de loi $\mu$. À ce
processus est à son tour associé l'arbre généalogique correspondant.

On renvoie au texte d'Igor Kortchemski (ce volume) pour la propriété
suivante. Nous reviendrons brièvement sur cette interprétation au
paragraphe \ref{sec:perspectives-sur-le}.

\begin{propositio}
Soit $\mu$ la loi de Poisson de paramètre $\lambda>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 $a<b$, avec $b=O(\sqrt{n})$,
\begin{align*}
\P&(R^{(n)}_1=a,R^{(n)}_2=b)=\P(R^{(n)}_2=b|R^{(n)}_1=a)\P(R_1^{(n)}=a)\\
&=(b/n)\cdot(1-(a-1)/n)\cdot(1-a/n)\ldots (1-(b-1)/n) \P(R_1^{(n)}=a)\\
&=(a/n)(b/n)\exp(-b^2/2n+o(1)).
\end{align*}
On déduit le résultat pour $m=2$ par les caractérisations de la
convergence en loi rappelés dans l'introduction, et ceci se généralise
sans difficulté à $m$ quelconque. Il convient néanmoins de montrer que
l'expression de $\ell_1,\ldots,\ell_m$ donnée dans l'énoncé est bien
une densité pour tout $m$, ce que nous laissons en exercice.
\end{proof}

La loi jointe des variables aléatoires $L_1,L_2,\ldots$ apparaissant
dans l'énoncé précédent peut se décrire très simplement en termes d'un
processus de Poisson, c'est-à-dire une suite $\eta_1,\eta_2,\ldots$ de
variables aléatoires telles que la suite $(\eta_i-\eta_{i-1},i\geq 1)$ (avec
la convention $\eta_0=0$) est formée de variables aléatoires i.i.d.\ de
loi exponentielle de paramètre $1$, c'est-à-dire
$\P(\eta_1\geq t)=\exp(-t)$. On a en effet que
$$(L_1,L_2,\ldots)\overset{(\text{loi})}{=}(\sqrt{2\eta_1},\sqrt{2\eta_2},\ldots)\,
.$$
Nous laissons cette preuve en exercice.
On constate donc que les variables aléatoires $L_1,L_2,\ldots$ ont
tendance à s'accumuler, au sens où les écarts $L_{n}-L_{n-1}$
convergent vers $0$ presque sûrement, en contraste avec les $\eta_n$. Pour
s'en convaincre, on peut utiliser la loi des grands nombres, qui
montre que $\eta_n\sim n$ presque sûrement, et écrire, avec la représentation ci-dessus,
$$L_n-L_{n-1}=\sqrt{2\eta_{n-1}}\, \Big(\sqrt{1+\be_n/2\eta_{n-1}}-1 \Big)=O(\ln(n)/n^{1/2})$$
où $\be_n=\eta_n-\eta_{n-1}$, et où l'on a utilisé le fait que
$$\limsup\frac{\be_n}{\ln(n)}\leq 1,\qquad \text{presque
sûrement}.$$
Ce dernier fait est une conséquence aisée du lemme de Borel-Cantelli: on a en
effet, comme $\P(\be_i>x)=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(\ba')$. Contradiction avec la minimalité
de~$w(\ba')$.
\end{proof}

\subsection{L'algorithme de Kruskal, et applications}\label{sec:lalg-de-krusk}

L'algorithme de Kruskal (qui, semble-t-il, remonte en fait à \hbox{Boruvka})
est un algorithme \og glouton\fg. Nous l'énonçons dans le cas d'un
graphe fini connexe pondéré général $G=(V,E,w)$.
L'algorithme consiste, partant du graphe
vide, à ajouter une à une les arêtes du graphe par ordre
croissant de poids, sauf lorsque l'ajout de l'arête en question crée
un cycle. En pseudo-code, cela donne l'algorithme suivant.

\subsubsection*{Algorithme de Kruskal}
\begin{enumerate}
\item Numéroter les arêtes de $G=(V,E)$ en $e_1,e_2,\ldots$ de
sorte que $w(e_1)<w(e_2)<\ldots$.
\item Initialiser $S=Z=\varnothing$ et $I=1$.
\item Tant que $S\neq V$ faire
\begin{itemize}
\item Si $(V,Z\cup\{e_I\})$ est sans cycle, alors $S\leftarrow S\cup e_I$,
$Z\leftarrow Z\cup\{e_I\}$
\item $I\leftarrow I+1$.
\end{itemize}
\item Retourner $Z$.
\end{enumerate}

\begin{theorem}
\label{sec:lalg-de-krusk-2}
L'algorithme de Kruskal produit l'unique arbre couvrant minimal de $G$
pondéré par $w$.
\end{theorem}

\begin{proof}
Soit $G=(V,E)$ le sous-graphe de $K_n$ produit par l'algorithme.
Par définition, $G$ n'a aucun cycle, et donc définit une \hbox{forêt}
couvrante du graphe complet, c'est-à-dire que chaque composante
connexe est un arbre. Par ailleurs, soit $V_1$ l'ensemble des
sommets de $G$ connectés à $1$, et supposons par l'absurde que
$V_1\neq [n]$. L'ensemble (non vide) des arêtes ayant une extrémité
dans $V_1$ et l'autre dans $[n]\setminus V_1$ a un élément de plus
petit poids, et clairement, cette arête aurait dû être ajoutée à
l'étape de l'algorithme où elle est considérée. Donc $G$ est un
arbre couvrant de $K_n$.

Il reste à montrer que $G$ est un arbre couvrant minimal. Pour cela,
montrons par récurrence que pour tout $i\in
\{0,1,\ldots,\card(V)-1\}$, le~graphe $G(i)$ construit au $i$-ème
instant de l'algorithme \emph{où une arête est ajoutée} peut être
prolongé en un arbre couvrant minimal.

Pour $i=0$ c'est évident en prenant n'importe quel arbre couvrant
minimal. Si cela est vrai au rang $i<\card(V)-1$, soit $G'(i)$ un
arbre couvrant minimal contenant $G(i)$. Soit $e$ la $i+1$-ème arête
ajoutée dans l'algorithme de Kruskal. Si $e$ est dans $G'(i)$ alors
$G'(i)$ contient aussi $G(i+1)$ et on peut poser
$G'(i+1)=G'(i)$. Sinon, l'ajout de~$e$ à~$G'(i)$ crée un cycle
$C$. Il existe forcément une arête $e'\neq e$ de ce cycle qui n'est
pas dans $G(i)$: en effet, dans le cas contraire, l'apparition de
$e$ à l'étape $i+1$ aurait créé le cycle $C$, et $e$ n'aurait pas
été ajoutée à cette étape. Noter également que $e'$ est forcément de
poids plus grand que $e$: sinon, $e'$ aurait été choisie par
l'algorithme à une étape précédente, et $e$ n'aurait pu être ajoutée
sans créer de cycle. Alors $G'(i+1)=(G'(i)\setminus \{e'\})\cup
\{e\}$ est un arbre couvrant qui prolonge $G(i+1)$, et son poids est
$w(G'(i))+w(e)-w(e')<w(G'(i))$, ce qui est absurde par minimalité.

Cette preuve montre de plus que\enlargethispage{\baselineskip}%
$$G'(0)=G'(1)=\ldots=G'(\card(V)-1),$$
c'est-à-dire qu'il n'y a qu'un seul arbre couvrant minimal.
\end{proof}

Nous en déduisons le critère suivant déterminant si une arête est dans
l'arbre couvrant minimal, qui nous sera très utile par la suite.

\begin{propositio}
\label{sec:lalg-de-krusk-1}
Une arête $e=\{x,y\}\in E$ est dans $E(\ba_m)$ si et seulement si pour
tout chemin $x=x_1,x_2,\ldots,x_k=y$, il existe une arête
$e'=\{x_i,x_{i+1}\}$ telle que $w(e)\geq w(e')$.
\end{propositio}

\begin{proof}
Supposons que $e=e_j$ soit la $j$-ème arête dans l'ordre croissant
de poids. Cette arête est ajoutée à la $j$-ème étape de l'algorithme
de Kruskal si et seulement si les extrémités $x$ et $y$ ne sont pas
connectées à l'étape $j-1$. Si tout chemin de $x$ à $y$ passe par
une arête de poids $>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 $s<r$ ou $s>r$: 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(X<r)=\frac{1}{k!}\int_0^rx^{k-1}e^{-x}\d x\leq r^k/k!.$$
Par conséquent, l'espérance du nombre de sommets à $d_\xi$-distance
inférieure à $r$ de l'origine (à l'exception de celle-ci) est
\begin{align*}
\E\biggl[\sum_{u\in
\mathcal{U}^*}\ind_{\{d_\xi(u,\varnothing)\leq
r\}} \biggr]&\leq \sum_{u\in \mathcal{U}^*}
\frac{r^{|u|_1}}{|u|_1!}=\sum_{k\geq 1}\sum_{l\geq 0}\frac{r^{k+l}}{(k+l)!}\\
&\leq\sum_{k,l\geq 0}\frac{r^{k+l}}{k!\,l!}\leq e^{2r},
\end{align*}
puisque $(k+l)!\geq
k!\,l!$. D'où le résultat.

\subsubsection*{La première génération du PWIT}
Nous avons donné
précédemment la loi du réarrangement croissant
$(\be^n_{(1)},\ldots,\be^n_{(n-1)})$ de $n-1$ variables exponentielles
indépendantes: on peut les représenter sous la forme
$$\be^n_{(i)}=\sum_{j=1}^i\frac{\be'_j}{n-j},\qquad 1\leq i\leq n-1,$$
où $\be'_i$, $i\geq 1$ sont également des variables exponentielles
indépendantes. Par conséquent, on voit immédiatement que dans cette
représentation,
$$n(\be^n_{(i)},i\geq
1)\underset{n\to\infty}{\longrightarrow}\biggl(\sum_{j=1}^i\be'_i,i\geq
1 \biggr),$$
(presque sûrement!) et on reconnaît à droite un processus de Poisson. Si l'on interprète
les variables $(\be^n_{(i)},1\leq i\leq n)$ comme les distances aux
voisins de la racine dans le graphe complet, on voit donc qu'elles
correspondent à la limite aux distances de la racine à ses voisins
dans le PWIT. On notera que cette limite décrit en réalité les voisins
de la racine qui en sont très proches: la plupart des voisins se
trouvent à une distance renormalisée de l'ordre de $n$, et \og
disparaissent\fg à la limite.

La preuve du théorème \ref{sec:le-graphe-complet-1} consiste
essentiellement à réitérer l'argument ci-dessus génération par
génération, en justifiant le fait que les distances des $B$ plus
proches voisins de la racine de $K_n$ à leurs~$B$ plus proches voisins
distincts de la racine peuvent être décrits à la limite par les $B$
premiers atomes d'un processus de Poisson indépendants, et aussi que
tous les sommets ainsi visités sont tous distincts. Ici, $B$ est un
grand entier fixé lorsque $n\to\infty$. Nous omettons les détails
techniques de la preuve.

\subsection{L'arbre minimal vu comme une forêt couvrante du
PWIT}\label{sec:larbre-minimal-vu}

Rappelons que nous voulons décrire non seulement une limite loca\-le du
graphe complet, mais aussi de l'arbre couvrant minimal $M_n$. On~peut
se demander à quel objet cela peut correspondre sur le PWIT, puisque
ce dernier est \emph{déjà un arbre}! Mais un moment de réflexion montre
que l'on ne saurait voir toutes les arêtes du PWIT comme correspondant
à la limite de l'arbre couvrant minimal, pour la raison
suivante. Rappelons-nous la proposition \ref{sec:lalg-de-krusk-1}
disant qu'une arête $e=\{x,y\}$ est dans l'arbre couvrant minimal si et seulement
si tout chemin de $x$ à $y$ emprunte au moins une arête $e'$ de poids
$w(e')>w(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<x_1+\ldots+x_n+x_{n+1}} \d x_1\ldots\d x_n\d
x_{n+1}\, e^{-(x_1+\ldots+x_n+x_{n+1})}\\
&=\int_{y>\lambda}\d y\, e^{-y}\int_{y_1<\ldots<y_n\leq \lambda}\d y_1\ldots\d y_n\\
&=\frac{\lambda^n\, e^{-\lambda}}{n!},
\end{align*}
comme voulu.
Par construction du PWIT, on voit donc que le sous graphe de $\bT$ formé
des arêtes de poids $<\lambda$ est constitué des $N_\lambda^u$
premiers voisins de chaque sommet $u\in V(\bT)$, où $N_\lambda^u,u\in
V(\bT)$ est une famille i.i.d.\ de loi de Poisson de paramètre
$\lambda$. Il est immédiat de vérifier la composante connexe de
$\varnothing$ a la loi voulue.
\end{proof}

Les résultats standards sur le processus de branchement (rappelons que
$\E[N_\lambda]=\lambda$) montrent que $\bT_\lambda$ est fini presque
sûrement si $\lambda\in [0,1]$, et que $\P(|\bT_\lambda|=\infty)$
est l'unique racine $q=q(\lambda)$ dans $]0,1[$ de l'équation\vspace*{-.5\baselineskip}\enlargethispage{\baselineskip}%
$$e^{-\lambda q}=1-q$$
(voir par exemple le texte d'Igor Kortchemski, ce volume). En fait, il est
également connu que sur l'événement où $\bT_\lambda$ est infini, la
géné\-ra\-tion $n$ contient de l'ordre de $W\lambda^n$ individus, où $W>0$
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}

