Graphe aléatoire

Dans ce modèle, souvent noté ${\displaystyle \mathbb {G} (n,p),}$ chacune des n(n–1)/2 arêtes potentielles est présente avec probabilité p, et absente avec probabilité 1-p, cela indépendamment du statut des autres arêtes. Le cas p = 0,5 a été étudié par Erdős dès 1947[2]. Le nombre N_p d'arêtes de ${\displaystyle \mathbb {G} (n,p)}$ suit la loi binomiale de paramètres n(n–1)/2 et p.

Dans ce modèle, souvent noté ${\displaystyle \mathbb {G} (n,M),}$ on choisit uniformément un sous-ensemble de M arêtes parmi les n(n–1)/2 arêtes possibles. Si on considère un graphe G à n sommets possède M arêtes, la probabilité d'obtenir G est donnée par

${\displaystyle \mathbb {P} (G)\ =\ {\frac {1}{{n \choose 2} \choose M}}.}$

C'est le modèle ${\displaystyle \mathbb {G} (n,M)}$ qui est principalement étudié dans la série d'articles fondateurs publiés par Erdős et Rényi entre 1959 et 1968[3].

• On peut partir d'un graphe sans arêtes, donc totalement déconnecté, et ajouter une arête tirée au hasard uniformément, puis une autre, etc., sans remise. On obtient ainsi une suite ${\displaystyle \{\mathbb {G} (n,M)\}_{0\leq M\leq n(n-1)/2},}$ croissante (au sens de l'inclusion de l'ensemble des arêtes), de 1 + n(n–1)/2 graphes aléatoires, qui forme un processus à temps discret à valeurs dans l'ensemble des graphes. Chaque terme de la suite est un graphe aléatoire uniforme défini à la section précédente. Un avantage de cette construction est de voir coexister différents graphes aléatoires de paramètres M différents, sur le même espace probabilisé, et de pouvoir ainsi comparer leurs caractéristiques, non pas en moyenne ou en loi, mais pour chaque élément ω de l'espace probabilisé considéré. Cela permet de raisonner par couplage.
• On peut aussi associer à chaque arête e de J une variable aléatoire T_e, le poids de l'arête, de sorte que la famille (T_e)_{e ∈ J} soit une famille de variables aléatoires i.i.d., par exemple de loi uniforme sur l'intervalle [0, 1]. On note alors ${\displaystyle \mathbb {G} (n,p)}$ le graphe formé des arêtes dont le poids est inférieur à p. Pour chaque arête, cela se produit avec probabilité

${\displaystyle \mathbb {P} (T_{e}\leq p)\ =\ p.}$

On obtient ainsi une famille ${\displaystyle \{\mathbb {G} (n,p)\}_{0\leq p\leq 1},}$ croissante, de graphes aléatoires, qui forme un processus à temps continu, à valeurs dans l'ensemble des graphes. Cette famille est croissante au sens de l'inclusion de l'ensemble des arêtes : une arête e présente dans ${\displaystyle \mathbb {G} (n,p)}$ est aussi présente dans ${\displaystyle \mathbb {G} (n,p+\varepsilon ),\ \varepsilon >0,}$ puisque ${\displaystyle \{T_{e}\leq p\}\ \Rightarrow \ \{T_{e}\leq p+\varepsilon \}.}$ Chaque terme de la famille de graphes est un graphe aléatoire binomial défini précédemment.

Métaphore. On peut imaginer les sommets du graphe comme n îles sur un lac, communicant à l'aide de passerelles (les arêtes e), submergées à des profondeurs respectives T_e sous la surface de l'eau. Si le lac se vide de son eau graduellement, on va voir émerger progressivement les passerelles, et des composantes connexes regroupant de plus en plus d'îles vont se former.

En vertu du théorème central limite, ou de l'inégalité de Hoeffding, la loi binomiale est très concentrée autour de son espérance. Plus précisément, le nombre d'arêtes N_p d'un graphe aléatoire de loi ${\displaystyle \mathbb {G} (n,p)}$ est donc très proche de ${\displaystyle {\hat {M}}=\left\lfloor p\ {n \choose 2}\right\rfloor }$ surtout si cette dernière quantité ${\displaystyle {\hat {M}}}$ est grande devant n : en effet[4],

${\displaystyle \forall t>0,\qquad \mathbb {P} \left(\left|N_{p}-{\hat {M}}\right|\geq tn\right)\ \leq \ 2\,\mathrm {e} ^{-2t^{2}}.}$

De plus, la loi conditionnelle de ${\displaystyle \ \mathbb {G} (n,p)}$ sachant que N_p = M est précisément ${\displaystyle \mathbb {G} (n,M).}$ Pour cette raison, si M est proche de ${\displaystyle {\hat {M}}}$, ou, de manière équivalente, si

${\displaystyle p\simeq {\frac {2M}{n(n-1)}},}$

il est généralement admis (et souvent démontré[5]) que les deux modèles ${\displaystyle \mathbb {G} (n,p)}$ et ${\displaystyle \mathbb {G} (n,M)}$ ont des propriétés très proches.

En poussant plus loin, notons T_(k) la k-ième valeur de la suite ${\displaystyle (T_{e})_{e\in J}}$ une fois que cette dernière suite est rangée dans l'ordre croissant : la suite ${\displaystyle (T_{(k)})_{1\leq e\leq n(n-1)/2}}$ est appelée la suite des statistiques d'ordre de la suite ${\displaystyle (T_{e})_{e\in J}.}$ Lorsque p prend la valeur aléatoire T_(M), alors ${\displaystyle \mathbb {G} (n,T_{(M)})}$ est exactement ${\displaystyle \mathbb {G} (n,M).}$ Pour corroborer les observations précédentes, notons que T_(M) est très proche de ${\displaystyle 2M/n(n-1),}$ au sens où, en conséquence de résultats célèbres de Donsker et de Kolmogorov[6], la probabilité

${\displaystyle \varphi _{n}(x)=\mathbb {P} \left(\sup _{1\leq M\leq n(n-1)/2}\left\{|T_{(M)}-{\tfrac {2M}{n(n-1)}}|\right\}\geq {\tfrac {x{\sqrt {2}}}{n}}\right)}$

satisfait

${\displaystyle \exp(-2x^{2})\ \leq \ \liminf _{n}\varphi _{n}(x)\ \leq \ \limsup _{n}\varphi _{n}(x)\ \leq \ 2\sum _{r=1}^{+\infty }(-1)^{r-1}\exp(-2r^{2}x^{2}),}$

les 1^er et 4^e termes étant les queues de distribution des lois de Rayleigh et de Kolmogorov, respectivement : en résumé, le supremum (lorsque M varie) des erreurs ${\displaystyle |T_{(M)}-2M/n(n-1)|}$ est de l'ordre de 1/n.

Théorème (Erdős, Rényi, 1960) — Posons a_n = np(n) — ln n, ou encore :

${\displaystyle p(n)\ =\ {\frac {\ln n}{n}}\,+\,{\frac {a_{n}}{n}}.}$

• Si ${\displaystyle \lim _{n}a_{n}=+\infty ,}$ alors ${\displaystyle \lim _{n}\mathbb {P} \left(\mathbb {G} \left(p(n),n\right)\mathrm {~est~connexe} \right)=1.}$
• Si ${\displaystyle \lim _{n}a_{n}=-\infty ,}$ alors ${\displaystyle \lim _{n}\mathbb {P} \left(\mathbb {G} \left(p(n),n\right)\mathrm {~est~connexe} \right)=0.}$

On dit que ln(n)/n est un seuil étroit pour la propriété de connexité, l'étroitesse faisant référence au fait que la propriété est vérifiée même si ${\displaystyle a_{n}}$ tend vers l'infini strictement moins vite que ${\displaystyle \ln n.}$

Démonstration

On se donne un graphe aléatoire G_n de loi ${\displaystyle \mathbb {G} \left(p(n),n\right)}$ et un graphe aléatoire ${\displaystyle {\tilde {G}}_{n}}$ de loi ${\displaystyle \mathbb {G} \left({\tilde {p}}(n),n\right).}$ Le théorème découle du théorème double-exponentiel, qui découle lui-même de l'énumération des points isolés effectuée à la section suivante. La connexité est une propriété croissante, donc, dès que n est assez grand pour que

${\displaystyle p(n)\ =\ {\frac {\ln n}{n}}\,+\,{\frac {a_{n}}{n}}\quad \geq \quad {\frac {\ln n}{n}}+{\frac {c}{n}}+{\frac {\varepsilon (n)}{n}}\ =\ {\tilde {p}}(n),}$

on a aussi

${\displaystyle \mathbb {P} \left(G_{n}\mathrm {~est~connexe} \right)\geq \mathbb {P} \left({\tilde {G}}_{n}\mathrm {~est~connexe} \right).}$

En effet, quitte à construire ${\displaystyle G_{n}}$ et ${\displaystyle {\tilde {G}}_{n}}$ à l'aide des mêmes variables uniformes i.i.d. ${\displaystyle (U_{e})_{e\in J}}$, sur le même espace probabilisé Ω, comme indiqué à la section « Les deux processus aléatoires à valeurs graphe », on a, pour tout ω de Ω,

${\displaystyle G_{n}(\omega )\supset {\tilde {G}}_{n}(\omega ),}$

donc

${\displaystyle \left\{{\tilde {G}}_{n}(\omega ){\text{ est connexe}}\right\}\Rightarrow \left\{G_{n}(\omega )\mathrm {~est~connexe} \right\},}$

et

${\displaystyle \mathbb {P} \left({\tilde {G}}_{n}\mathrm {~est~connexe} \right)\leq \mathbb {P} \left(G_{n}\mathrm {~est~connexe} \right).}$

Si ${\displaystyle \lim _{n}a_{n}=+\infty ,}$ il suit que, pour tout nombre réel c,

${\displaystyle \liminf _{n}\mathbb {P} \left(\mathbb {G} \left(p(n),n\right)\mathrm {~est~connexe} \right)\geq \mathrm {e} ^{-\mathrm {e} ^{-c}},}$

ou bien encore

${\displaystyle \liminf _{n}\mathbb {P} \left(\mathbb {G} \left(p(n),n\right)\mathrm {~est~connexe} \right)\geq \sup \left\{\mathrm {e} ^{-\mathrm {e} ^{-c}}\,|\,c\in \mathbb {R} \right\}\ =\ 1.}$

En revanche, si ${\displaystyle \lim _{n}a_{n}=-\infty ,}$ alors, pour n suffisamment grand, on aura, pour tout ω, ${\displaystyle G_{n}(\omega )\subset {\tilde {G}}_{n}(\omega ),}$ et

${\displaystyle \mathbb {P} \left({\tilde {G}}_{n}\mathrm {~est~connexe} \right)\geq \mathbb {P} \left(G_{n}\mathrm {~est~connexe} \right).}$

Ainsi, pour tout nombre réel c,

${\displaystyle \limsup _{n}\mathbb {P} \left(\mathbb {G} \left(p(n),n\right)\mathrm {~est~connexe} \right)\leq \inf \left\{\mathrm {e} ^{-\mathrm {e} ^{-c}}\,|\,c\in \mathbb {R} \right\}\ =\ 0.}$

Il est plus facile (plus probable) de réussir à couper les n – 1 connexions entre un point et son complémentaire, que les k(n – k) connexions entre un groupe de k points et son complémentaire, car la fonction f(k) = k(n – k) augmente très rapidement au voisinage de 1, d'où, lorsque k augmente, beaucoup plus d'arêtes à couper, et une probabilité bien plus faible de réussir à les couper toutes. En corollaire, avec le choix du paramètre p fait plus haut, le graphe G(n, p) sera non connexe « presque uniquement » s'il a des points isolés, au sens où la probabilité d'être connexe est très proche de la probabilité de ne pas avoir de points isolés, ${\displaystyle \mathbb {P} \left(X_{n}=0\right),}$ qui vaut approximativement e^–e–c En effet, on a le résultat suivant :

Points isolés (Erdős, Rényi, 1960). — Supposons que

${\displaystyle {\tilde {p}}(n)\ =\ {\frac {\ln n}{n}}+{\frac {c}{n}}+{\frac {\varepsilon (n)}{n}}.}$

Alors le nombre X_n de points isolés du graphe ${\displaystyle G\left({\tilde {p}}(n),n\right)}$ converge en loi vers une loi de Poisson de paramètre e^–c.

Démonstration

Dans ce qui suit, on abrège ${\displaystyle G\left({\tilde {p}}(n),n\right)}$ en ${\displaystyle {\tilde {G}}_{n},}$ et on pose

${\displaystyle \mu =\mathrm {e} ^{-c}.}$

Soit X_n le nombre de points isolés de ${\displaystyle {\tilde {G}}_{n}.}$ On sait que

${\displaystyle X_{n}=Y_{1}+Y_{2}+\dots +Y_{n},}$

où

${\displaystyle Y_{i}=1_{\mathrm {le~sommet~} i\mathrm {~est~isol{\acute {e}}} }.}$

Utilisons la méthode des moments factoriels[7]. Soit I_{n , A} l'ensemble des injections de ${\displaystyle [\![1,n]\!]}$ dans ${\displaystyle A.}$ Pour tout ${\displaystyle r\geq 1,}$

${\displaystyle (X_{n})_{r}=(Y_{1}+Y_{2}+\dots +Y_{n})_{r}=\sum _{\varphi \in I_{r,[\![1,n]\!]}}\ \prod _{i=1}^{r}Y_{\varphi (i)}.}$

Les termes ${\displaystyle \prod _{i=1}^{r}Y_{\varphi (i)}}$ de la somme précédente apparaissent effectivement dans le développement de ${\displaystyle (Y_{1}+Y_{2}+\dots +Y_{n})_{r},}$ mais, en dehors de ces termes, ce développement fait apparaître beaucoup d'autres termes qui, apparemment, se télescopent. En effet, soit

${\displaystyle E=\left\{a\in [\![1,n]\!]\,|\,Y_{a}=1\right\}.}$

Alors

${\displaystyle \forall \,\varphi \in I_{r,[\![1,n]\!]},\qquad \prod _{i=1}^{r}Y_{\varphi (i)}=1_{\varphi \in I_{r,E}},}$

donc

${\displaystyle \sum _{\varphi \in I_{r,[\![1,n]\!]}}\ \prod _{i=1}^{r}Y_{\varphi (i)}\ =\ |I_{r,E}|\ =\ (|E|)_{r}\ =\ (X_{n})_{r}.}$

Par ailleurs, par symétrie,

${\displaystyle \mathbb {E} \left[\prod _{i=1}^{r}Y_{\varphi (i)}\right]\ =\ \mathbb {E} \left[\prod _{i=1}^{r}Y_{i}\right]=(1-{\tilde {p}}(n))^{r(n-1)-r(r-1)/2},}$

où r(n -1) est le nombre d'arêtes potentiellement issues d'un sommet de E, et où r(r -1)/2 est le nombre d'arêtes entre deux sommets de E, c.-à-d. celles qui sont comptées double dans le total r(n -1). Ainsi

${\displaystyle {\begin{aligned}\mathbb {E} \left[(X_{n})_{r}\right]&=(n)_{r}(1-{\tilde {p}}(n))^{r(n-1)-r(r-1)/2}\\&\simeq n^{r}(1-{\tilde {p}}(n))^{r(n-1)}\\&=\left(n(1-{\tilde {p}}(n))^{n-1}\right)^{r}\\&\simeq \mu ^{r}.\end{aligned}}}$

Donc, par la méthode des moments[7], X_n converge en loi vers une loi de Poisson de paramètre μ, et

${\displaystyle \lim \mathbb {P} \left(X_{n}=0\right)\ =\ \mathrm {e} ^{-\mu }\ =\ \mathrm {e} ^{-\mathrm {e} ^{-c}}.}$

Ce théorème est une illustration frappante du paradigme de Poisson, selon lequel, lorsque se présente un grand nombre d'opportunités d'observer un événement rare (c.-à-d. peu probable), alors le nombre total d'événements rares effectivement observés suit une loi de Poisson.

Erdős et Rényi en déduisent un résultat plus précis que la propriété de seuil étroit :

Théorème double-exponentiel (Erdős, Rényi, 1960) — Supposons que

${\displaystyle {\tilde {p}}(n)\ =\ {\frac {\ln n}{n}}+{\frac {c}{n}}+{\frac {\varepsilon (n)}{n}}.}$ Alors ${\displaystyle \lim _{n}\mathbb {P} \left(\mathbb {G} \left({\tilde {p}}(n),n\right)\mathrm {~est~connexe} \right)=e^{-e^{-c}}.}$

Démonstration

Si ${\displaystyle X_{n}=0,}$ ${\displaystyle {\tilde {G}}_{n}}$ est sans point isolé, et il y a alors peu de chances que ${\displaystyle {\tilde {G}}_{n}}$ soit autre chose que connexe (cf. Spencer, 10 lectures on random graphs). En effet, soit B une partie de ${\displaystyle [\![1,n]\!]}$ et soit k son cardinal. Notons ${\displaystyle {\mathcal {C}}_{B}}$ l'événement « B est une composante connexe de ${\displaystyle {\tilde {G}}_{n}}$ ». L'événement ${\displaystyle {\mathcal {C}}_{B}}$ peut être vu comme la réunion (non disjointe) de k^{k -2} sous-ensembles de probabilités ${\displaystyle {\tilde {p}}(n)^{k-1}(1-{\tilde {p}}(n))^{k(n-k)},}$

ce qui conduit à la majoration suivante :

${\displaystyle \mathbb {P} ({\mathcal {C}}_{B})\ \leq \ k^{k-2}{\tilde {p}}(n)^{k-1}(1-{\tilde {p}}(n))^{k(n-k)}.}$

Ici ${\displaystyle k^{k-2}}$ désigne le nombre d'arbres couvrants possibles[8] pour un graphe connexe dont les sommets seraient les éléments de B, ou bien encore, de manière équivalente, le nombre de choix possibles d'une famille de k-1 arêtes qui rend l'ensemble B connexe. Par ailleurs, ${\displaystyle {\tilde {p}}(n)^{k-1}}$ est la probabilité que les k-1 arêtes de l'arbre couvrant considéré soient effectivement présentes, et ${\displaystyle (1-{\tilde {p}}(n))^{k(n-k)}}$ est la probabilité qu'aucune arête reliant un sommet de B à un sommet de B^c ne soit présente, de telle sorte que B soit non seulement connexe, mais aussi maximale parmi les parties connexes du graphe.

L'événement

${\displaystyle D_{n}=\{X_{n}=0\mathrm {~mais~} {\tilde {G}}_{n}\mathrm {~n} ^{\prime }\mathrm {est~pas~connexe} \}}$

vérifie

${\displaystyle D_{n}\subset \bigcup _{2\leq |B|\leq n/2}{\mathcal {C}}_{B}.}$

En effet, sous l'hypothèse D_n, ${\displaystyle {\tilde {G}}_{n}}$ a plusieurs composantes connexes, donc la plus petite d'entre elles (au sens du nombre de sommets) a au plus n/2 sommets, mais cette plus petite composante connexe a au moins deux sommets, puisque X_n = 0. Ainsi

${\displaystyle {\begin{aligned}\mathbb {P} (D_{n})&\leq \sum _{2\leq |B|\leq n/2}\mathbb {P} ({\mathcal {C}}_{B})\\&\leq \sum _{2\leq k\leq n/2}{n \choose k}k^{k-2}{\tilde {p}}(n)^{k-1}(1-{\tilde {p}}(n))^{k(n-k)}\\&\leq \sum _{2\leq k\leq n/2}u_{k}.\end{aligned}}}$

Or, pour α > 0,

${\displaystyle {\begin{aligned}u_{2}&\leq n^{-1+\alpha }\,\ln n\end{aligned}}}$

dès que

${\displaystyle \ln n\geq \max \left[c+\varepsilon (n)\,,(-2c-2\varepsilon (n)+4{\tilde {p}}(n))/\alpha \right].}$

De même qu'une composante connexe de taille supérieure à 2 est bien moins probable qu'une composante connexe de taille 1, une composante connexe de taille supérieure à 3 est bien moins probable qu'une composante connexe de taille 2, ce qui se traduit par

Propriété — Quand n tend vers l'infini

${\displaystyle u_{2}(n)\ \gg \ \sum _{3\leq k\leq n/2}u_{k}(n).}$

Quelques calculs un peu pénibles, sans être toutefois franchement difficiles, conduisent à ce résultat.

Démonstration

La borne donnée plus haut pour u₂(n) n'est pas seulement une majoration, mais donne en fait l'ordre de grandeur de u₂(n). Pour ce qui est du reste de la somme, on est contraint de le couper en deux avant de majorer chacun des deux morceaux :

${\displaystyle {\begin{aligned}{\frac {u_{k+1}}{u_{k}}}&=(n-k)\,(1+{\tfrac {1}{k}})^{k-2}\,{\tilde {p}}(n)\times (1-{\tilde {p}}(n))^{n-2k-1}\\&=(n-k)\,(e+{\hat {\varepsilon }}(k))\,{\tilde {p}}(n)\times (1-{\tilde {p}}(n))^{n-2k-1}\\&\leq {\hat {c}}\,\ln n\ (1-{\tilde {p}}(n))^{n-2k-1}\end{aligned}}}$

où

${\displaystyle \forall n,k,\quad {\hat {c}}\geq (e+{\hat {\varepsilon }}(k))\,{\frac {n{\tilde {p}}(n)}{\ln n}}.}$

Pour ${\displaystyle 0<\beta <(1-\gamma )/2<0.5,}$ et ${\displaystyle k\leq \beta n,}$

${\displaystyle {\begin{aligned}{\frac {u_{k+1}}{u_{k}}}&\leq {\hat {c}}\,\ln n\ \exp \left[-{\tilde {p}}(n)(n-2k-1)\right]\\&\leq {\hat {c}}n^{-\gamma }\ln n,\end{aligned}}}$

dès que

${\displaystyle \ln n\geq {\frac {{\tilde {p}}(n)+(c+\varepsilon (n))(2\beta -1)}{1-2\beta -\gamma }}.}$

Donc, pour n assez grand, ${\displaystyle u_{k}}$ décroit plus vite qu'une suite exponentielle de raison ${\displaystyle {\hat {c}}n^{-\gamma }\ln n,}$ lorsque ${\displaystyle 2\leq k\leq 1+\beta n,}$ et

${\displaystyle \sum _{k=2}^{1+\beta n}u_{k}\ \leq \ {\frac {u_{2}}{1-{\hat {c}}n^{-\gamma }\ln n}}\ \leq \ 2n^{-1+\alpha }\,\ln n.}$

Par ailleurs, pour ${\displaystyle 0<\alpha <1/4,}$ on peut trouver c et ρ positifs, tels que, pour tout ${\displaystyle n\geq 1,}$

${\displaystyle {\begin{aligned}u_{n/2}&\leq c\,\rho ^{n}\,n^{-\alpha n}.\end{aligned}}}$

Pour ${\displaystyle 0<\beta <(1-\gamma )/2<0.5,}$ et ${\displaystyle k\geq \beta n,}$

${\displaystyle {\begin{aligned}{\frac {u_{k-1}}{u_{k}}}&\leq {\frac {d}{\ln n}}\ \exp \left[{\tilde {p}}(n)(n-2k+1)\right]\\&\leq {\frac {d\,n^{(1-2\beta )^{2}/\gamma }}{\ln n}}\\&\leq d\,n^{(1-2\beta )^{2}/\gamma },\end{aligned}}}$

dès que n est assez grand. Par conséquent, pour ${\displaystyle n/2\geq k\geq \beta n,}$ et ${\displaystyle \beta }$ assez proche de 0,5, ${\displaystyle (1-2\beta )/\gamma }$ assez proche de 1,

${\displaystyle {\begin{aligned}-\alpha +((1-2\beta )^{3}/2\gamma )&<0,\\{\frac {u_{k}}{u_{n/2}}}&\leq d^{(1-2\beta )n/2}n^{n(1-2\beta )^{3}/2\gamma },\\u_{k}&\leq c\,{\tilde {\rho }}^{n}\,n^{(-\alpha +((1-2\beta )^{3}/2\gamma ))n},\end{aligned}}}$

et

${\displaystyle \sum _{k=\beta n}^{n/2}u_{k}\ \leq \ c\,{\hat {\rho }}^{n}\,n^{(-\alpha +((1-2\beta )^{3}/2\gamma ))n}\ \ll \ u_{2}.}$

Par conséquent

${\displaystyle \lim _{n}\mathbb {P} \left({\tilde {G}}_{n}\mathrm {~est~connexe} \right)=\lim _{n}\mathbb {P} \left(X_{n}=0\right).}$

Notons T_n le premier instant t où le graphe ${\displaystyle \mathbb {G} \left(t,n\right)}$ est connexe :

${\displaystyle T_{n}\ =\ \inf \left\{t\geq 0\ |\ \mathbb {G} (t,n)\mathrm {~est~connexe} \right\},}$

de sorte que

${\displaystyle \left\{\mathbb {G} \left(t,n\right)\mathrm {~est~connexe} \right\}\quad \Rightarrow \quad \left\{T_{n}\leq t\right\}\quad \Rightarrow \quad \left\{\forall \varepsilon >0,\quad \mathbb {G} \left(t+\varepsilon ,n\right)\mathrm {~est~connexe} \right\}.}$

On peut alors voir le théorème double-exponentiel comme un résultat sur le développement asymptotique de T_n : si Z_n est défini par la relation suivante :

${\displaystyle T_{n}\ =\ {\frac {\ln n}{n}}\ +\ {\frac {Z_{n}}{n}},}$

alors le théorème double-exponentiel stipule que Z_n converge en loi vers la distribution de Gumbel, ce qui pourrait se traduire, dans une version probabiliste de la notation de Landau, par :

${\displaystyle T_{n}\ =\ {\frac {\ln n}{n}}\ +\ \Theta \left({\frac {1}{n}}\right).}$

• (en) Béla Bollobás, Random Graphs, Cambridge University Press, janvier 2001, 2^e éd. (1^re éd. 1985), 516 p. (ISBN 978-0-521-79722-1, lire en ligne).
• (en) Svante Janson (en), Tomasz Łuczak et Andrzej Ruciński, Random Graphs, Wiley-Interscience, mai 2000, 1^re éd., 333 p., hardcover (ISBN 978-0-471-17541-4).
• (en) Joel Spencer, « Nine lectures on random graphs », dans École d'été de Probabilités de Saint-Flour XXI-1991, Part 3, Springer, coll. « Lecture Notes in Math. » (n^o 1541), 1993, p. 293-347.

Introduction de probabilités en théorie des graphes

Laurent Massoulié, Réseaux: contrôle distribué et phénomènes émergents, 2015