0% ont trouvé ce document utile (0 vote)

203 vues76 pages

Cours Web

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

203 vues76 pages

Cours Web

Transféré par

Abdelkrim RACHEDI

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Graphes aléatoires

Raphaël Rossignol

18 décembre 2012
2
Introduction

Ces notes correspondent à un cours donné au premier semestre 2011-2012

dans le cadre du M2 recherche de l’institut Fourier, à Grenoble.

0.1 Présentation du personnage principal : G(n, p)

Un graphe (simple, étiqueté, non orienté) est la donnée d’une paire G =
(V, E), où V est un ensemble, et E est un sous-ensemble de l’ensemble V2 des
paires d’éléments de V . Les éléments de V sont appelés les sommets de G et les
éléments de E sont appelés les arêtes de G.
Soient n ≥ 1 un entier et p ∈ [0, 1]. On note [n] l’ensemble des entiers de 1 à
n et Ωn l’ensemble de tous les graphes d’ensemble de sommets exactement [n].
Un de ces graphes est Kn , la clique(i.e graphe complet) d’ordre n : son ensemble
d’arêtes est [n]

2 . G(n, p) est un graphe aléatoire à n sommets inventé par Erdös
et Rényi dans les années 50 (en fait, le modèle original d’Erdös et Rényi était
légèrement différent, cf. section 1.4 dans [JLR00]). C’est à dire que c’est une
variable aléatoire à valeurs dans Ωn , obtenue comme suit. On considère une col-
lection de variables aléatoires i.i.d (Xe )e∈([n]) de loi de Bernoulli de paramètre p.
2
G(n, p) est alors le graphe ayant pour ensemble de sommets [n] et pour ensemble
d’arêtes celles telles que Xe = 1. Autrement dit, on part de Kn , et on supprime
chaque arête avec probabilité (1 − p), indépendamment des autres. On voit aussi
que la donnée de G(n, p) est équivalente à la donnée de la collection (Xe )e∈([n]) .
2
L’entier n est le nombre de sommets de G(n, p). Que représente le réel p ?
C’est la densité moyenne d’arêtes (par rapport à Kn ). En effet, le nombre
d’arêtes de G(n, p) suit une loi binomiale de paramètres n2 et p. Donc en
moyenne, le nombre d’arêtes de G(n, p) est n2 p. Lorsque p augmente de 0 à
1, on voit donc qu’en moyenne, le nombre d’arêtes augmente. Il est en fait pos-
sible de réaliser les lois de G(n, p) pour tout p de [0, 1] sur un même espace de
probabilité en faisant en sorte que G(n, p) ⊂ G(n, p0 ) pour tout p0 ≥ p, au sens où
l’ensemble des arêtes de G(n, p) est inclus dans l’ensemble des arêtes de G(n, p0 ).
On dit qu’on couple ces différentes lois et on appellera ce couplage le couplage
standard. Considérons une collection de variables aléatoires i.i.d (Ue )e∈([n]) de
2
loi uniforme sur [0, 1], et notons, pour toute arête e, Xe (p) = 1Ue ≤p . En as-
sociant G(n, p) à (Xe (p))e∈([n]) on voit qu’on a la même loi que ci-dessus, et
2

i
ii INTRODUCTION

qu’on a bien la propriété de croissance désirée. En faisant croı̂tre p de 0 à 1, on

voit ainsi un graphe sur n sommets, initialement vide (i.e sans arête), puis se
comblant d’arête petit à petit jusqu’à devenir plein, i.e égal au graphe complet
Kn .
Ce cours sera avant tout consacré à l’étude du graphe aléatoire G(n, p) d’un
point de vue asymptotique : la question principale est “quelle est l’allure, quelles
propriétés possède G(n, p) lorsque le nombre de sommets n est grand ?”. Gnp
étant une variable aléatoire, on examinera cette question sous l’angle des pro-
babilités asymptotiques, en donnat des résultats de convergence en loi ou en
probabilité lorsque le nombre de sommets n tend vers l’infini. Remarquons déjà
que l’existence du deuxième paramètre p donne la liberté de le faire évoluer
avec n, et on verra qu’une des parties les plus intéressantes de l’étude de G(n, p)
nécessite de le faire. On dira qu’une propriété est vérifiée a.p.s (“asymptotique-
ment presque sûrement”) par G(n, p) si la probabilité que G(n, p) vérifie cette
propriété tend vers 1 lorsque n tend vers l’infini (p pouvant être une fonction
de n).
A quoi sert donc d’étudier G(n, p) ? Voici quelques éléments de réponse :
1. c’est un modèle amusant, et même joli !
2. l’étude des grands graphes peut être très compliquée et les propriétés
des grands graphes peuvent être très difficiles à déterminer de manières
déterministes. Par exemple, savoir si un graphe est hamiltonien, savoir si
son nombre clique est supérieure à un entier k fixé, ou s’il est colorable
avec k couleurs sont des exemples de problèmes NP-complets. Il est alors
intéressant d’avoir une étude en moyenne, en probabilité, pour pouvoir
répondre à ces questions de manière approchée et avec grande probabilité
(on dit souvent “pour un graphe typique”).
3. c’est un modèle très simple mais déjà riche :
— notons déjà qu’il contient la probabilité uniforme sur les graphes de
Ωn , obtenue pour p = 1/2.
— il possède une dynamique lorsque p évolue de 0 à 1. Ainsi on montrera
que le schéma suivant est vrai a.p.s.****** Schéma d’évolution
******
4. l’étudier permet d’utiliser des outils amusants de probabilités, comme la
méthode du premier et du second moment, les arbres de Galton-Watson,
les marches aléatoires ou les martingales.
5. enfin, c’est un modèle intéressant car il permet de montrer l’existence
de certains graphes ayant des propriétés contre-intuitives, ou bien dont
l’existence est difficile à montrer sans faire appel aux probabilités. Ceci
est relié à ce qu’on appelle la méthode probabiliste en théorie des graphes.
L’idée de base est simple : pour montrer qu’un graphe existe ayant une
propriété A donnée on construit un graphe aléatoire et on montre que
ce graphe aléatoire possède la propriété A avec probabilité strictement
positive. Cela donne des résultats d’existence, non constructifs en général.
Un exemple d’application de cette méthode est l’obtention de graphes
0.2. PLAN iii

avec simultanément une maille et un nombre chromatique grands. La

maille d’un graphe est la taille du plus petit cycle. Le nombre chromatique
d’un graphe est le nombre minimal de couleurs nécessaires pour colorier
les sommets du graphe de sorte que deux sommets adjacents ne soient
jamais de la même couleur. La méthode probabiliste permet de montrer
que pour tous entiers k et l il existe un graphe de nombre chromatique
supérieur à k et de maille supérieure à l.
Remarquons tout de suite que G(n, p) est trop peu réaliste pour pouvoir
modéliser correctement des réseaux réels, comme ceux du web par exemple.
Notamment, la loi des degrés, l’indépendance des arêtes et la dynamique crois-
sante sont irréalistes. Plusieurs généralisations ont été étudiées, notamment les
modèles d’attachement préférentiel ou les modèles de configuration (cf. [Dur10]).
Néanmoins, le modèle d’Erdös-Rényi reste un exemple fondateur à partir duquel
il est utile de penser ces modèles plus réalistes.

0.2 Plan
1. Petits sous-graphes
2. Connexité
3. Un peu de concentration
4. Transition de phase d’Erdös-Rényi : apparition de la composante géante
5. Nombre d’indépendance, k-colorabilité

0.3 Phénomènes de seuil

Revenons un instant sur le schéma d’évolution pour noter que de nombreuses
propriétés apparaissent soudainement : lorsque p est petit devant une certaine
valeur p∗n , la propriété est fausse a.p.s et lorsque p est grand devant cette valeur,
la propriété devient vraie a.p.s. On dit dans ce cas que p∗n est une fonction
seuil pour la propriété considérée et que la propriété vérifie un phénomène de
seuil. Cela a du sens notamment pour les propriétés croissantes. On dit qu’une
propriété est croissante si pour tout G de Ωn , si G satisfait la propriété, alors tout
G0 de Ωn contenant G la satisfait aussi. Autrement dit, en rajoutant uniquement
des arêtes, on ne peut faire disparaı̂tre la propriété. Par exemple, contenir un
triangle, être connexe, être hamiltonien . . . sont des propriétés croissantes. Si
A est une propriété croissante, le couplage standard montre que la fonction
p 7→ P(G(n, p) ∈ A) est croissante sur [0, 1]. Si Ωn ∩ A est différent de Ωn et de
l’ensemble vide, on peut voir que cette fonction passe continûment de 0 à 1 et
est strictement croissante. On peut donc toujours définir une valeur p∗n comme
la valeur de p pour laquelle P(G(n, p) ∈ A) vaut 1/2. On peut alors montrer que
toute fonction monotone vérifie un phénomène de seuil, dans un cadre d’ailleurs
plus général que celui des graphes aléatoires (cf. le Théorème 1.24 p.20 dans
[JLR00]).
iv INTRODUCTION

Pour les propriétés monotones, on constatera également que pour certaines

propriétés, la largeur de seuil (c’est à dire la largeur de l’intervalle des valeurs
de p pour lesquelles la probabilité P(G(n, p) ∈ A) appartient à [ε, 1 − ε]) est
petite devant la fonction seuil, alors que pour d’autres, elles sont du même
ordre de grandeur. Dans le premier cas, on parle de seuil étroit (sharp threshold
en anglais), et dans le second, on parle de seuil grossier (coarse threshold). Un
sujet intéressant, qu’on évoquera peut-être à la fin du cours, est de comprendre
ce qui provoque le caractère étroit ou grossier d’un phénomène de seuil (cf.
paragraphe 1.6 dans [JLR00]).

0.4 Notions élémentaires de théorie des graphes

Si G est un graphe, on note V (G) l’ensemble de ses sommets et E(G) l’en-

semble de ses arêtes. L’ordre de G est le cardinal de V (G), noté vG . La taille
de G est le cardinal de E(G), noté eG .
Si u et v sont deux sommets de G, on dit que u et v sont adjacents si {u, v}
est une arête de G, et on note u ∼ v.
Un morphisme (de graphe) φ d’un graphe G vers un graphe G0 est une appli-
cation de V (G) vers V (G0 ) telle que pour tous x et y de V (G), x ∼ y ⇒ φ(x) ∼
φ(y). On dit que φ est un isomorphisme entre G et G0 si φ est un morphisme
bijectif et que son inverse est un morphisme. S’il existe un isomorphisme entre
G et G0 on dit qu’ils sont isomorphes, ou encore que G0 est une copie de G. Un
automorphisme de G est un isomorphisme entre G et lui-même, on note Aut(G)
le groupe des automorphismes de G.
Un sous-graphe de G est un graphe H tel que V (H) ⊂ V (G) et E(H) ⊂
E(G). On notera souvent H ⊂ G pour signifier que H est un sous-graphe de G.
Soit W un ensemble de sommets inclus dans V (G). On note G(W ) le graphe de
sommets W et d’arêtes E(G) ∩ W

2 . On dit que G(W ) est le sous-graphe induit
par W . De même, si F est un ensemble d’arêtes inclus dans E(G), on note G(F )
le graphe d’arêtes F et de sommets l’ensemble des sommets appartenant à l’une
des arêtes de F . G(F ) est le sous-graphe induit par F .
Un graphe connexe G vérifie toujours eG ≥ vG −1, avec égalité si et seulement
si G est un arbre, c’est à dire un graphe sans cycle. eG = vG correspond à un
graphe unicyclique, c’est à dire contenant exactement un seul cycle. Lorsque
eG ≤ vG , on dit que G est simple (à ne pas confondre avec la définition de
“simple” signifiant qu’il ne peut y avoir plusieurs arêtes entre deux sommets.
Pour nous, tous les graphes seront simples pour ce sens-ci). On dit que G est
complexe si eG ≥ vG + 1.
Quelques mots-clefs qui reviendront dans le cours : coloration ou coloriage, k-
colorabilité, nombre chromatique, cycle, maille, distance, connexité, composante
connexe . . .
0.5. LES MÉTHODES DU PREMIER ET DU SECOND MOMENT v

0.5 Les méthodes du premier et du second mo-

ment
Voyons le premier outil probabiliste de ce cours. Pour montrer que des
évènements ont lieu a.p.s, on utilisera beaucoup ce qu’on appelle les méthodes
du premier et du second moment.
La méthode du premier moment consiste à appliquer l’inégalité de Markov.
Par exemple, soit (Xn )n≥1 une suite de v.a. à valeurs dans N. Si E(Xn ) tend
vers 0 lorsque n tend vers l’infini, alors a.p.s Xn = 0. En effet,

P(Xn > 0) = P(Xn ≥ 1) ≤ E(Xn ) −−→ 0 .

n∞

Notamment, si Xn est le cardinal d’un ensemble d’objets présents dans G(n, p),
on en déduira que a.p.s. G(n, p) ne contient aucun exemplaire de ces objets.
La méthode du second moment consiste à appliquer l’inégalité de Tchebycheff
(ou de Paley-Wiener) pour obtenir une conclusion dans l’autre sens.
Par exemple, soit (Xn )n≥1 une suite de v.a. à valeurs positives. Si Xn n’est
pas constant égal à 0, et si l’écart-type de Xn est petit devant son espérance,
alors a.p.s Xn > 0. En effet, en appliquant Cauchy-Schwarz,

E(Xn )2 Var(Xn ) Var(Xn )

P(Xn > 0) ≥ =1− ≥1− .
E(Xn2 ) E(Xn2 ) E(Xn )2

Application : Exercices 0.1 et 0.2.

Les autres outils probabilistes seront introduits au fur et à mesure des be-
soins.

0.6 Remarques sur les notations

(n)k = n(n − 1) . . . (n − k + 1)
Tous les logarithmes sont en base e si la base n’est pas précisée.
Notations de Landau et Hardy.

0.7 Références principales

[AS08], [Bol01], [JLR00]
vi INTRODUCTION

0.8 Exercices
Exercice 0.1 Méthode du premier moment. Compter le nombre moyen de
copies de K4 dans G(n, p). Montrer que si p = o(n−2/3 ), alors a.p.s G(n, p) ne
contient pas de copie de K4 . Mêmes questions pour le graphe G obtenu à partir
de K4 en rajoutant un sommet relié par une seule arête à l’un des sommets de
K4 . Mêmes questions pour les copies induites de G.
Exercice 0.2 Méthode du second moment. Montrer que si p = o(n−2 ),
G(n, p) est a.p.s le graphe vide. Montrer que si p = ω(n−2 ), a.p.s G(n, p) est non
vide.
Exercice 0.3 On suppose que p = c/n avec c ∈ R∗+ fixé. Montrer que le degré
d’un sommet v fixé dans G(n, p) converge en loi, lorsque n tend vers l’infini, vers
une loi de Poisson de paramètre c.
Exercice 0.4 On appelle bicycle un graphe constitué soit de deux cycles dis-
joints reliés par un chemin (éventuellement réduit à un point), soit d’un cycle
auquel on a ajouté un chemin entre deux sommets non consécutifs. Montrer
que si p = (1 − ε)/n avec ε n−1/3 , a.p.s G(n, p) ne contient pas de bicycle.
En déduire que pour les mêmes valeurs de p, a.p.s les composantes connexes de
G(n, p) sont simples.
Exercice 0.5 Modèle original d’Erdös et Rényi Soit M un entier inférieur
ou égal à n. On considère un graphe aléatoire G̃(n, M ) obtenu en tirant un
graphe au hasard, uniformément, parmi tous les sous-graphes étiquetés de Kn
ayant M arêtes. Appliquer la méthode du premier moment pour le nombre de
copies de K4 .
Chapitre 1

Petits sous-graphes

Soit G un graphe fixé. La propriété “contenir une copie de G” est une pro-
priété croissante. Dans ce chapitre, on déterminera la fonction seuil de cette
propriété, et pour les graphes dits “strictement équilibrés”, on montrera un
comportement poissonien pour le nombre de copies à l’intérieur du seuil.
Dans la suite, G est un graphe fixé, non vide. On note O(G) l’orbite de G
dans Kn , c’est à dire l’ensemble des copies de G dans Kn . Remarquons que :

(n)vG
|O(G)| = .
|Aut(G)|

On note XG la variable aléatoire qui compte le nombre de copies de G dans

G(n, p) :
1G0 ⊂G(n,p) .
X
XG =
G0 ∈O(G)

Remarquons que :

E(XG ) = |O(G)|peG = Θ(nvG peG ) .

1.1 Seuil d’apparition d’une copie d’un petit sous-

graphe
L’exercice 0.1 a mis en évidence les choses suivantes. Pour tout graphe H, si
p = o(n−vG /eG ), a.p.s G(n, p) ne contient pas G. Mais pour que G apparaisse, il
faut que tous les sous-graphes non vides de G apparaissent, ce qui ne peut arriver
si p = o(n−vH /eH ) pour un sous-graphe H de G. Remarquons que n−vH /eH est
une fonction croissante de 2eH /vH qui est le degré moyen de H. Les graphes
les plus “denses” (au sens de degré moyen le plus élevé) sont les plus difficiles à
obtenir : il faut plus d’arête à G(n, p) pour les voir apparaı̂tre. On note :
eH
m(G) = max .
H⊂G vH

1
2 CHAPITRE 1. PETITS SOUS-GRAPHES

Nous allons voir que n−1/m(G) est la fonction seuil pour l’apparition d’une copie
de G. Pour cela, on cherche à appliquer la méthode du second P moment. D’une
manière générale, soit X une somme d’indicatrices, X = α∈Γ Iα . Pour tout
couple d’indicatrices (Iα , Iβ ), on note α ∼ β si α 6= β et Cov(Iα , Iβ ) 6= 0. On a
alors :
X X
Var(X) = Var(Iα ) + Cov(Iα , Iβ ) ,
α∈Γ α∼β
Var(X) ≤ E(X) + ∆ , (1.1)
(1.2)
où on a noté : X
∆= E(Iα Iβ ) .
α∼β

On voit alors que si E(X) tend vers l’infini, on aura Var(X) = o(E(X)2 ) dès
que ∆ = o(E(X)2 ). Examinons la situation lorsque X = XG . Notons H un
ensemble contenant un représentant de chaque classe d’isomorphisme des sous-
graphes non vides de G, en excluant les copies de G.
X
∆ = p2eG −eG1 ∩G2 ,
G1 6=G2 ∈O(G)
E(G1 ∩G2 )6=∅
X X
= p2eG −eH ,
H∈H G1 6=G2 ∈O(G)
G1 ∩G2 ∈O(H)
X
≤ p2eG −eH |O(G)|.|{G2 ∈ O(G) t.q. G1 ∩ G2 ∈ O(H)}| .
H∈H

où G1 est une copie fixée de G. Or, en notant c(H, G) le nombre de copies de
H dans G,
|O(G)|
|{G2 ∈ O(G) t.q. G1 ∩ G2 ∈ O(H)}| ≤ c(H, G)2 . (1.3)
|O(H)|
En effet, en notant H1 une copie fixe de H incluse dans G1 ,
|{G2 ∈ O(G) t.q. G1 ∩ G2 ∈ O(H)}| ≤ c(H, G)|{G2 ∈ O(G) t.q. H1 ⊂ G2 }| .
De plus,
|O(G)|c(H, G) = |{(H̃, G2 ) ∈ O(H) × O(G) t.q. H̃ ⊂ G2 }| ,
= |O(H)|.|{G2 ∈ O(G) t.q. H1 ⊂ G2 }| ,
ce qui montre (1.3). Par conséquent,
X |O(G)|2
∆ ≤ p2eG −eH c(H, G)2 ,
|O(H)|
H∈H
X c(H, G)E(XG )2
≤ ,
E(XH )
H(G
eH 6=0
1.2. A L’INTÉRIEUR DU SEUIL 3

On a donc prouvé le lemme suivant.

Lemme 1.1.1. Pour tout graphe G non vide,

X c(H, G)E(XG )2
Var(XG ) ≤ E(XG ) + .
E(XH )
H(G
eH 6=0

On en déduit facilement la fonction seuil pour le fait de contenir une copie

de G. En effet, si p = o(n−1/mG ), alors notamment E(XG ) tend vers 0, donc
a.p.s G(n, p) ne contient pas G. Si p = ω(n−1/mG ), alors E(XH ) tend vers l’infini
pour tout H ⊂ G non vide. Donc le lemme précédent et la méthode du second
moment permettent de conclure que G(n, p) contient une copie de G a.p.s.

Théorème 1.1.2. Pour tout graphe G non vide fixé, la fonction seuil pour le
fait de contenir une copie de G est n−1/mG .

1.2 A l’intérieur du seuil pour les sous-graphes

strictement équilibrés
Définition 1.2.1. On dit qu’un graphe G est équilibré si eG /vG = mG , c’est
à dire si son degré moyen est supérieur ou égal à n’importe lequel de celui de
ses sous-graphes. On dit qu’il est strictement équilibré si son degré moyen est
strictement supérieur à ceux de ses sous-graphes propres.

Lorsqu’un graphe G est strictement équilibré et que E(XG ) = Θ(1), on voit

que ∆ = o(1) car E(XH ) 1 pour tout sous-graphe propre H de G non vide.
On en déduit que la différence entre la variance de XG et son espérance est
petite, et que les indicatrices qui composent XG sont peu corrélées. On peut
alors s’attendre à avoir une convergence de XG en loi vers une loi de Poisson
si E(XG ) converge vers une constante λ ∈ R∗+ . On en déduira alors que la
probabilité de voir une copie de G dans G(n, p) vaut :

P(XG ≥ 1) ∼ 1 − e−λ . (1.4)

Le but de cette section est de montrer la proximité entre la loi de XG et une

loi de Poisson. On verra dans le chapitre 3 une façon de montrer directement
(1.4) à l’aide d’inégalités de corrélation, qui peuvent d’ailleurs être utiles dans
un contexte plus large.

1.2.1 Convergence en loi et distance en variation totale

Rappelons la définition de la convergence en loi.

Définition 1.2.2. Soit (Xn )n≥1 une suite de variables aléatoires à valeurs dans
un espace topologique mesurable X . Soit µ une mesure de probabilité sur X et
4 CHAPITRE 1. PETITS SOUS-GRAPHES

µn la loi de Xn . On dit que (Xn )n≥1 converge en loi vers µ si et seulement si

pour toute fonction continue bornée f de X dans R,
Z Z
f dµn −−−−→ f dµ .
n→∞

Lorsque X = R, on a les équivalences suivantes de la convergence en loi.

Proposition 1.2.3. Soit (Xn )n≥1 une suite de variables aléatoires à valeurs
réelles, µ une mesure de probabilité sur les boréliens de R et µn la loi de Xn .
Les propositions suivantes sont équivalentes.
(i) (Xn )n≥1 converge en loi vers µ.
(ii) Convergence des fonctions de répartition. Pour tout x réel tel que
µ({x}) = 0,
µn (] − ∞, x]) −−−−→ µ(] − ∞, x]) .
n→∞

(iii) Convergence des fonctions caractéristiques. Pour tout réel t,

Z Z
e dµn (x) −−−−→ eitx dµ(x) .
itx
n→∞

Soit maintenant un espace E au plus dénombrable, muni de la tribu discrète

E et de la topologie discrète. Pour mesurer la proximité entre deux lois, on peut
utiliser la distance en variation totale définie, pour deux mesures de probabilités
µ et ν sur E, par
dT V (µ, ν) = sup |µ(A) − ν(A)| .
A∈E

Cette distance définit en général une topologie plus fine que la topologie de la
convergence en loi, mais sur un espace dénombrable comme E, nous allons voir
que les deux topologies sont équivalentes.
Lemme 1.2.4.
Z Z
1 1X
dT V (µ, ν) = sup | f dµ − f dν| = |µ(x) − ν(x)| .
2 f :E→[−1,1] 2
x∈E

Démonstration: Soit f : E → [−1, 1].

Z Z X X
| f dµ − f dν| ≤ |f (x)||µ(x) − ν(x)| ≤ sup |f | |µ(x) − ν(x)| ,
E
x∈E x∈E

et l’inégalité est saturée pour f = 1B − 1 c

B avec :
B = {x ∈ E t.q. µ(x) ≥ ν(x)} .
Ceci montre la deuxième égalité. Pour la première,
X
2|µ(A) − ν(A)| = |µ(A) − ν(A)| + |µ(Ac ) − ν(Ac )| ≤ |µ(x) − ν(x)| ,
x∈E

et l’inégalité est saturée pour A = B.

1.2. A L’INTÉRIEUR DU SEUIL 5

Proposition 1.2.5. Soit (Xn )n≥1 une suite de variables aléatoires à valeurs
dans E, µ une mesure de probabilité sur E et µn la loi de Xn . Les propositions
suivantes sont équivalentes.
(i) (Xn )n≥1 converge en loi vers µ.
(ii) Pour toute fonction f bornée de E dans R,
Z Z
f dµn −−−−→ f dµ .
n→∞

(iii) Pour tout x de E,

µn (x) −−−−→ µ(x) .
n→∞

(iv) dT V (µn , µ) −−−−→ 0.

n→∞

Démonstration: Exercice !
Il est facile de voir que si (X, Y ) est une variable aléatoire telle que X a pour
loi µ et Y pour loi ν (on appelle (X, Y ) un couplage de µ et ν), alors :

dT V (µ, ν) ≤ P(X 6= Y ) .

Il se trouve que l’égalité est atteinte pour un certain couplage.

Proposition 1.2.6.

dT V (µ, ν) = min P(X 6= Y ) .

(X,Y ) couplage de µ et ν

P
Démonstration: Soit p = x µ(x) ∧ ν(x). On a :

dT V (µ, ν) = 1 − p .

Si p ∈ {0, 1}, faire une preuve séparée. Sinon, prendre U , V , W et B des variables
aléatoires telles que (U, V, W ) soit indépendante de B, B soit de Bernoulli de
paramètre p, U de loi p−1 (µ ∧ ν), V de loi (1 − p)−1 (µ − µ ∧ ν) et W de loi
(1 − p)−1 (ν − µ ∧ ν). On pose alors :

X = Y = U si B = 1 ,

X = V et Y = W si B = 0 .
On vérifie que c’est un couplage, et que :

P(X 6= Y ) ≤ P(B = 0) = 1 − p = dT V (µ, ν) .

6 CHAPITRE 1. PETITS SOUS-GRAPHES

1.2.2 Approximation poissonienne par couplage

Le premier résultat est un résultat général sur l’approximation poissonienne
des sommes d’indicatrices. Pour mesurer la proximité entre deux lois, on utilisera
la distance en variation totale.
Prenons par exemple n variables aléatoires indépendantes de Bernoulli, X1 , . . . , Xn ,
avec Xi de paramètre pi . On a alors le résultat facile suivant.
Pn
LemmePn 1.2.7. Soit µ la loi de X = i=1 Xi et ν la loi de Poisson de paramètre
λ = i=1 pi . Alors,
X n
dT V (µ, ν) ≤ p2i .
i=1

Démonstration: On réalise un couplage de µ et ν de la façon suivante. Soient

U1 , . . . , Un des v.a.i.i.d uniformes su [0, 1]. On note :

k−1
X (pi )j
y0i = 0 et ∀k ≥ 1, yki = P(P(pi ) ≤ k − 1) = e−pi .
j=0
j!

Xi = 1Ui ≥1−pi et Yi = k lorsque Ui ∈ [yki , yk+1

i
[.
Les Xi sont indépendantes,
P de loi B(pi ) et les Yi sont indépendantes, de loi
P(pi ). Ainsi, Y = i Yi est de loi P(λ), et donc (X, Y ) est un couplage de µ et
de ν.

P(Xi 6= Yi ) = P(Ui ∈ [1−pi , e−pi [)+P(Ui ∈ [e−pi (1+pi ), 1]) = pi (1−e−pi ) ≤ p2i .

Donc :
n
X n
X
dT V (µ, ν) ≤ P(X 6= Y ) ≤ P(Xi 6= Yi ) ≤ p2i .
i=1 i=1

On considère maintenant, comme dans la section précédente, une collection

P
finie d’indicatrices (Iα )α∈Γ , éventuellement dépendantes. On note X = α∈Γ Iα
leur somme, pα = E(Iα ) et on s’intéresse à l’approximation de X par la loi de
Poisson de paramètre :
X
λ= pα = E(X) .
α

Théorème 1.2.8. On note µ la loi de X, µα la loi de (Iβ )β6=α conditionnelle-

ment à {Iα = 1} et να la loi de (Iβ )β6=α .
X X
dT V (µ, P(λ)) ≤ p2α + 2 pα dT V (µα , να ) .
α α
1.2. A L’INTÉRIEUR DU SEUIL 7

Démonstration: On va coupler µ avec la loi d’une somme de Bernoulli indépendantes

de paramètres pα . Le Lemme 1.2.7 permettra ensuite de mesurer l’écart entre
la loi de la somme de Bernoulli indépendante et la loi P(λ).
Soit m le cardinal de Γ. On ordonne les éléments de Γ de manière arbitraire,
et on les renomme 1, . . . , m. Notamment pi = E(Ii ). Soient U1 , . . . , Um des
v.a.i.i.d uniformes sur [0, 1]. On pose, pour (x1 , . . . , xi−1 ) ∈ {0, 1}i−1 :

p0i (x1 , . . . , xi−1 ) = P(Ii = 1|I1 = x1 , . . . , Ii−1 = xi−1 ) .

et on définit :
Ii∗ = 1Ui ≤pi et Ii0 = 1Ui ≤p0i (I10 ,...,Ii−1
0 ) .

Alors les (Ii0 )1≤i≤n ont même loi que les (Ii )1≤i≤n et les (Ii∗ )1≤i≤n ont pour loi
⊗ni=1 B(pi ). De plus,

P(Ii0 6= Ii∗ ) = E[P(Ii0 6= Ii∗ |I10 , . . . , Ii−1

0
)] ,
= E[|pi − p0i (I10 , . . . , Ii−1
0
)|] ,
= E[|pi − E(Ii |I1 , . . . , Ii−1 )|] ,
≤ E[|pi − E(Ii |I1 , . . . , Ii−1 , Ii+1 , . . . , In )|] ,
X
= P[(Ij )j6=i = x]|pi − E(Ii |(Ij )j6=i = x)| ,
x∈{0,1}n−1
X
P[(Ij )j6=i = x] P(Ii = 1) − P(Ii = 1|(Ij0 )j6=i = x) ,

=
x∈{0,1}n−1
X
= P(Ii = 1) |P[(Ij )j6=i = x] − P[(Ij )j6=i = x|Ii = 1]| ,
x∈{0,1}n−1

= 2P(Ii = 1)dV T (µi , νi ) ,

νi la loi de (Ij )j6=i conditionnellement à {Ii = 1}.

avec µi la loi de (Ij )j6=i et P
n
Enfin, en notant ν la loi de i=1 Ii∗ ,
n
X n
X
dV T (µ, P(λ)) ≤ dV T (µ, ν) + dV T (ν, P(λ)) ≤ 2 pi dV T (µi , νi ) + p2i .
i=1 i=1

On peut facilement appliquer le Théorème 1.2.8 pour obtenir une approxima-
tion poissonienne pour une v.a qui compte un certain nombre de configurations
contenues dans le graphe aléatoire.
Théorème 1.2.9. Soit Γ un ensemble de parties de E(Kn ). Pour α ∈ Γ, on
note :
Iα = 1α⊂G(n,p) .
On note α ∼ β si α 6= β et α ∩ β 6= ∅. On définit :
X
∆= P(Iα = 1 et Iβ = 1) .
α∼β
8 CHAPITRE 1. PETITS SOUS-GRAPHES

Alors,
X
dT V (L(X), P(λ)) ≤ p2α + 2∆ .
α

Démonstration: Soit X = (Xe )e∈Kn une collection de variables aléatoires de

Bernoulli de paramètre p. On note X 0 la collection obtenue à partir de X en
remplaçant par 1 les Xe pour e ∈ α. On définit, pour β ∈ Γ :
Y Y
Iβ = Xe et Iβ0 = Xe0 .
e∈β e∈β

Ainsi, en conservant les notations du Théorème1.2.8, (Iβ0 )β6=α a pour loi µα et

(Iβ )β6=α a pour loi να . On a alors :

dT V (µα , να ) ≤ P((Iβ0 )β6=α 6= (Iβ )β6=α ) ,

X
≤ P( Iβ0 ≥ 1) ,
β∼α
X
= P( Iβ ≥ 1|Iα = 1) ,
β∼α

et donc :
X X X
pα dT V (µα , να ) ≤ P( Iβ ≥ 1 et Iα = 1) ,
α α β∼α
X
≤ P(Iβ = 1 et Iα = 1) .
β∼α

Remarquons que le Théorème 1.2.8 n’est pas optimal lorsque λ est grand. En
fait, la stratégie de preuve du Lemme 1.2.7 est trop grossière : le couplage choisit
n’optimise pas le fait que les différences entre les Xi et les variables de Poisson
correspondantes peuvent se compenser dans la somme. Il existe une méthode,
dite méthode de Stein, qui améliore le Théorème 1.2.8 lorsque λ est grand (cf.
[BHJ92], notamment l’introduction et le chapitre 5).
Dernière remarque, le Théorème 1.2.8 implique une convergence vers la loi
normale pour λ−1/2 (XG − λ) si λ tend vers l’infini.

1.2.3 Méthode des moments

Une autre façon de montrer la convergence vers une loi de Poisson (ou une
autre loi) est la méthode des moments.

Théorème 1.2.10. Soit µ une mesure de probabilité sur R caractérisée par

ses moments. Soit (Xn )n≥1 une sutie de variables aléatoires réelles dont les
moments convergent vers ceux de µ. Alors (Xn )n≥1 converge en loi vers µ.
1.2. A L’INTÉRIEUR DU SEUIL 9

Si k ∈ N, le k-ème moment factoriel d’une v.a X est défini par :

E[(X)k ] = E[X(X − 1) . . . (X − k + 1)] .

Pour une variable de Poisson de paramètre λ, le k-ème moment factoriel vaut

λk . Par conséquent, la méthode des moments pour la loi de Poisson se réduit à
la proposition suivante.
Proposition 1.2.11. Soit Xn une suite de variables aléatoires à valeurs entières
et λ un réel strictement positif. Si pour tout entier k ≥ 1, le k-ème moment fac-
toriel de Xn converge vers λk , alors Xn converge en loi vers la loi de Poisson
de paramètre λ.
10 CHAPITRE 1. PETITS SOUS-GRAPHES

1.3 Exercices
P
Exercice 1.1 Soit X = α Iα une somme d’indicatrices telle que supα E(Iα ) =
o(1). Avec les notations du cours, montrer que :

Var(X) ∼ E(X) + ∆ .

Exercice 1.2 Calculer la fonction génératrice d’une loi de Poisson de paramètre

λ, puis calculer son k-ème moment factoriel.
Exercice 1.3 Soit G un graphe équilibré de degré moyen d et G0 un graphe
de degré moyen d0 ≥ d. Montrer que toute union de G et G0 a un degré moyen
supérieur ou égal à d. En déduire qu’une union de copies de G a un degré moyen
supérieur ou égal à d. Donner un contre-exemple lorsque G n’est pas équilibré.
Exercice 1.4 Déterminer une fonction seuil pour le graphe C4 , cycle de longueur
4 ainsi que pour le graphe G obtenu à partir de C4 en ajoutant un sommet et
une unique arête reliant ce sommet à C4 . A-t-on un comportement poissonien
pour XC4 à l’intérieur du seuil ? Et pour XG (on pourra donner une idée de la
loi limite) ?
Exercice 1.5 Soit G un graphe strictement équilibré et YG le nombre maxi-
mal de copies induites et disjointes de G dans G(n, p). On suppose que p =
cn−1/m(G) . Montrer que YG converge vers une loi de Poisson.
Exercice 1.6 Soient n ≤ N deux entiers naturels. Soit une urne à N boules
numérotées. On considère deux façons de prélever un échantillon aléatoire de
n boules dans l’urne. Soit on tire les boules avec remise, et on note X =
(X1 , . . . , Xn ) l’échantillon obtenu. Soit on tire les boules sans remise, et on
note X 0 = (X10 , . . . , Xn0 ) l’échantillon obtenu.
1. Calculer la distance en variation totale entre les lois de X et X 0 en
utilisant un couplage.
2. On suppose que les boules sont de deux couleurs : il y a M ≤ N boules
blanches et N −M boules noires. On note S (resp. S 0 ) le nombre de boules
blanches obtenues en tirant n boules avec remise (resp. sans remise).
Préciser les lois de S et S 0 et majorer la distance en variation totale
entre ces deux lois.
Chapitre 2

Connexité

Dans ce chapitre, on étudie le seuil d’apparition de la propriété monotone

“être connexe”. On montrera que ce seuil est situé en logn n , avec une largeur de
seuil d’ordre 1/n. C’est donc un exemple de seuil étroit.
Pour être connexe, il faut bien sûr ne pas avoir de sommet isolé. Il se trouve
qu’au moment où le graphe devient connexe, la seule obstruction à sa connexité
est la présence de sommets isolés. Ainsi les seuils de la propriété “ne pas contenir
de sommet isolé” et “être connexe” coı̈ncident. La raison de ce comportement
est la suivante : lorsque p 1/n, le graphe aléatoire possède une grande com-
posante connexe, appelée “composante géante”, contenant n − o(n) sommets, et
les autres composantes ont peu de sommets (cf. chapitre 4). Lorsque p grandit,
une composante de taille k + 1 a plus de chances d’être “avalée” par la grande
composante qu’une composante de taille k, car le nombre d’arêtes joignant la
composante de taille k + 1 à la composante géante est équivalent à (k + 1)n
alors que le nombre d’arêtes joignant la composante de taille k à la composante
géante est équivalent à kn. Ainsi, les dernières composantes connexes à être
avalées par la composante géante sont les plus petites.

2.1 Disparition des sommets isolés

Soit X le nombre de sommets isolés dans G(n, p).
n
1i est isolé .
X
X=
i=1

E(X) = n(1 − p)n−1 .

Lorsque p = o(1), ce qu’on supposera dans la suite,

2
/2+o(np2 )
E(X) = elog n−np−np .

11
12 CHAPITRE 2. CONNEXITÉ

Si np − log n tend vers +∞, G(n, p) ne contient pas de sommet isolé, a.p.s. Si
np − log n tend vers −∞, E(X) tend vers +∞. Examinons le second moment :
X
E(X 2 ) = E(X) + P(i, j sont isolés) ,
i6=j

= E(X) + (n)2 (1 − p)2n−3 ,

= E(X) + E(X)2 (1 + o(1)) ,

Donc si E(X) tend vers l’infini, E(X 2 ) ∼ E(X)2 et on peut appliquer la méthode
du second moment. On a montré :
Proposition 2.1.1. Si np − log n tend vers −∞, G(n, p) contient au moins
un sommet isolé, a.p.s. Si np − log n tend vers +∞, G(n, p) ne contient pas de
sommet isolé, a.p.s.
On peut imaginer que dans l’intervalle de seuil, X a un comportement pois-
sonien, vue la faible corrélation entre les indicatrices la composant. Calculons le
k-ème moment factoriel de X pour k fixé :
X
E[(X)k ] = P(i1 , . . . , ik sont isolés) ,
(i1 ,...,ik )
2 à 2 distincts
k
= (n)k (1 − p)(2)+k(n−k) ,
∼ E[X]k .

Donc si E(X) converge vers une constante λ, X converge en loi vers la loi de
Poisson de paramètre λ. Or, si np − log n converge vers c ∈ R, E(X) converge
vers e−c . On en déduit le résultat suivant.
Théorème 2.1.2.
log n c 1
Soit X le nombre de sommets isolés dans G(n, p). Si p =
n + n + o n avec c ∈ R, X converge vers une loi de Poisson de paramètre
e−c . En particulier, la probabilité que G(n, p) possède au moins un sommet isolé
−c
converge vers e−e .
Remarquons qu’on aurait pu également utiliser la méthode par couplage
(Exercice !).

2.2 Connexité
Nous allons d’abord montrer le lemme suivant.
Lemme 2.2.1. Si np ≥ α log n avec α > 2/3, alors a.p.s. G(n, p) ne possède
pas de composante connexe d’ordre appartenant à [2, n/2].
Par conséquent, les composantes connexes de G(n, p) ne peuvent être que de
deux types : des sommets isolés et une composante “géante”, de taille strictement
supérieure à n/2 (il ne peut contenir plus d’une composante connexe de taille
2.2. CONNEXITÉ 13

strictement supérieure à n/2). On en déduira donc que a.p.s. G(n, p) est connexe
si et seulement si il ne contient pas de sommet isolé, ce qui donne, avec le
théorème 2.1.2 :
Théorème 2.2.2. Si p = logn n + nc + o n1 avec c ∈ R, la probabilité que G(n, p)

−c
soit connexe converge vers e−e .

Démonstration: (du Lemme 2.2.1). Supposons que p = o(1) et np ≥ α log n avec

α > 1/2. Examinons séparément le cas des composantes connexes d’ordre 2 (les
arêtes isolées). La probabilité que G(n, p) contienne une composante connexe
d’ordre 2 est inférieure à :

n
p(1 − p)n−2 = Θ(pn2 e−2pn ) = O(n log ne−2α log n ) = o(1) .
2
Toute composante connexe d’ordre r contient un arbre couvrant dont tous les
sommets sont isolés des sommets en dehors de la composante connexe. Le
nombre d’arbres étiquetés sur r sommets est égal à rr−2 d’après la formule
de Cayley (cf. le cours de Michel Mollard). Donc, la probabilité que G(n, p)
contienne une composante connexe d’ordre appartenant à [3, n/2] est inférieure
à :
bn/2c
X n
rr−2 pr−1 (1 − p)r(n−r) .
r=3
r
Pour borner cette quantité, on peut utiliser la formule de Stirling. Il existe une
constante universelle C telle que :

n
r
n n r n n−r
≤C .
r r(n − r) r n−r
Lorsque r ≤ n/2, on obtient :
C0

n r−2
r ≤ 5/2 nr er .
r r
D’autre part, lorsque r ≤ n/2,
(1 − p)r(n−r) ≤ e−npr/2 .
Ainsi,
n r−2 r−1 1
r p (1 − p)r(n−r) . [enpe−np/2 ]r .
r p
Comme np tend vers l’infini, enpe−np/2 tend vers 0 et donc, pour n assez grand,
la probabilité que G(n, p) contienne une composante connexe d’ordre apparte-
nant à [3, n/2] est dominée par :
bn/2c
X 1 1
[enpe−np/2 ]r . (enpe−np/2 )3 = ne−3np/2 (np)2 .
r=3
p p
Pour np ≥ α log n avec α > 2/3 ceci tend vers 0.
14 CHAPITRE 2. CONNEXITÉ

2.3 Exercices
Exercice 2.1 Montrer que si np tend vers l’infini, a.p.s. les composantes connexes
de G(n, p) de taille inférieure à n/2 sont toutes des arbres, de taille o(log n).
Exercice 2.2 Montrer que lorsque np tend vers l’infini, a.p.s le nombre de points
en dehors de la composante géante est o(n).
Exercice 2.3 Montrer que si np ∼ α log n avec α < 1, pour tout ε > 0, le nombre
X de sommets isolés de G(n, p) appartient a.p.s à [n1−α (1 − ε), n1−α (1 + ε)].
En déduire que si α ∈]1/2, 1[, G(n, p) est a.p.s. constitué de O(n1−α ) sommets
isolés et d’une composante géante contenant n − O(n1−α ) sommets.
Chapitre 3

Inégalités de concentration
pour des sommes de
variables aléatoires
indépendantes

Ce chapitre est un interlude technique pour appréhender facilement l’ordre

de grandeur des sommes de variables aléatoires indépendantes.

Les sommes de v.a. indépendantes interviennent régulièrement dans l’étude

de G(n, p). Notamment, la loi binomiale joue un rôle important : par exemple,
le degré d’un sommet fixé ainsi que le nombre total d’arêtes de G(n, p) suivent
une loi binomiale. Plus généralement, d’autres types de sommes de variables
aléatoires indépendantes apparaı̂tront dans la suite du cours, et il sera crucial
de quantifier leur dispersion. En général, une telle somme Z est proche de son
espérance (penser à la loi des grands nombres), et un moyen de quantifier cela
est de produire une inégalité de concentration, qui est une borne supérieure
sur P(|Z − E(Z)| > t) pour t > 0. Le comportement à gauche et à droite de
la moyenne n’étant pas toujours symétrique, il est souvent préférable d’obtenir
séparément, pour t > 0, des bornes sur P(Z−E(Z) > t), on parle alors d’inégalité
de déviation supérieure, et sur P(Z − E(Z) < −t), on parle alors d’inégalité de
déviation inférieure.

Dans ce chapitre, nous obtiendrons via la méthode de Cramér-Chernoff des

inégalités de déviations nommées inégalités de Hoeffding, Bennett et Bernstein.

Remarque : on supposera toujours les variables aléatoires intégrables lorsque

c’est nécessaire.

15
16 CHAPITRE 3. INÉGALITÉS DE CONCENTRATION

3.1 Méthode de Cramér-Chernoff

Concentrons nous sur le cas des déviations supérieures. L’outil de base est
l’inégalité de Markov : si Z est une v.a positive ou nulle, et t > 0, alors :
E(Z)
P(Z > t) ≤ .
t
On peut faire fructifier un peu la méthode en prenant Z et t de signes quel-
conques et φ une fonction croissante et strictement positive sur R, pour obtenir :
E(φ(Z))
P(Z > t) ≤ P(φ(Z) > φ(t)) ≤ .
φ(t)
Il y a toutes sortes de fonctions φ intéressantes. Le choix de t ≥ 0, φ(x) = x2
et Z = |X − E(X)| donne l’inégalité de Tchebycheff. Lorsqu’on a affaire à des
sommes de variables aléatoires indépendantes qui ont des moments exponentiels,
il y a toute une famille de fonctions φ pour lesquels on peut faire des calculs
assez aisés : ce sont les fonctions de la forme x 7→ eλx avec λ ≥ 0 (le choix λ ≤ 0
donne des inégalités de déviations inférieures). En effet, notons Z = supni=1 Xi
une somme de variables aléatoires indépendantes. On obtient, pour λ ≥ 0 :
Pn n
Y
P(Z > t) ≤ e−λt E(eλ i=1 Xi
) ≤ e−λt E(eλXi ) .
i=1

Il reste alors à contrôler λ 7→ E(eλXi ) et à optimiser en λ. En fait, cette

méthode, dite méthode de Cramér-Chernoff, est utile même avec une seule va-
riable aléatoire, car elle permet souvent d’obtenir des bornes simples sur sa
queue de distribution. On peut écrire, pour tout t ∈ R :
P(Z > t) ≤ inf {e−λt E(eλt )} .
λ≥0

De même,
P(Z < t) ≤ inf {e−λt E(eλt )} .
λ≤0

Notons ΛZ la log-Laplace de Z :
ΛZ (λ) = log E(eλZ ) ,
et pour une fonction f de R dans R ∪ {+∞}, on définit sa transformée de
Legendre :
f ∗ (t) = sup{λt − f (λ)} .
λ∈R
Λ∗Z est appelée transformée de Cramér de Z.
Proposition 3.1.1. Pour tout t ≥ E(Z),
∗
P(Z > t) ≤ e−ΛZ (t) ,
et pour tout t ≤ E(Z), ∗
P(Z < t) ≤ e−ΛZ (t) .
3.2. INÉGALITÉS DE HOEFFDING, BENNETT ET BERNSTEIN 17

Démonstration: Il suffit de vérifier que pour t ≥ E(Z),

Λ∗Z (t) = sup{λt − ΛZ (λ)} .

λ≥0

et pour t ≤ E(Z),
Λ∗Z (t) = sup{λt − ΛZ (λ)} .
λ≤0

Remarquons d’abord que Λ∗Z (t) ≥ 0 (prendre λ = 0 dans la définition de Λ∗Z ).

L’inégalité de Jensen assure que ΛZ (λ) ≥ λE(Z). Donc lorsque t = E(Z),
Λ∗Z (t) = 0 et dans la définition de Λ∗Z , l’égalité est atteinte pour λ = 0. De
plus, lorsque t > E(Z), et λ < 0, λt − ΛZ (λ) < 0 ≤ Λ∗Z (t), ce qui montre que :

Λ∗Z (t) = sup{λt − ΛZ (λ)} .

λ≥0

Idem pour t < E(Z) et λ > 0.

Quelques exemples : cf. Exercice 3.2.

3.2 Inégalités de Hoeffding, Bennett et Bern-

stein
Il est souvent intéressant d’utiliser la méthode de Cramér-Chernoff lorsque
Z est une somme de variables aléatoires indépendantes X1 , . . . , Xn et qu’on
ne dispose pas exactement de la loi des Xi mais seulement d’hypothèses plus
générales comme une borne sur leurs supports ou sur leurs variances. Le premier
exemple est l’inégalité de Hoeffding, qui repose sur le lemme suivant.

Lemme 3.2.1. Soit Y une variable aléatoire d’espérance nulle prenant ses va-
leurs dans un intervalle [a, b]. Alors,

λ2 (b − a)2
ΛY (λ) ≤ ,
8
2
t
−2 (b−a)
P(Y ≥ t) ≤ e 2
,
et 2
t
−2 (b−a)
P(Y ≤ −t) ≤ e 2
.

Démonstration: Tout d’abord,

1 1
|Y − (a + b)| ≤ (b − a) ,
2 2
donc :
1 1
Var(Y ) = Var(Y − (a + b)) ≤ (b − a)2 .
2 4
18 CHAPITRE 3. INÉGALITÉS DE CONCENTRATION

Ensuite, soit Q la loi de Y . On note Z une variable aléatoire ayant pour loi Qλ ,
avec :
dQλ
(x) = exλ−ΛY (λ) .
dQ
Z est à valeurs dans [a, b], donc sa variance est majorée par 14 (b − a)2 . Mais,
00
ΛY (λ) = e−ΛY (λ) E(Y 2 eλY ) − e−2ΛY (λ) (E(Y eλY ))2 ,
= Var(Y ) .

D’après la formule de Taylor, il existe θ ∈ [0, λ] tel que

λ2 00 λ2 (b − a)2
ΛY (λ) = ΛY (θ) ≤ .
2 8
Enfin, la transformée de Legendre de λ 7→ 12 λ2 est t 7→ 12 t2 .

Théorème 3.2.2 (Inégalité de Hoeffding). Soient X1 , . . . , Xn desPnvariables

aléatoires indépendantes avec Xi à valeurs dans [ai , bi ]. Soit S = i=1 (Xi −
E(Xi )). Alors,
n
λ2 X
ΛS (λ) ≤ (bi − ai )2 ,
8 i=1
t2
−2 Pn (bi −ai )2
P(S ≥ t) ≤ e i=1 ,
et
t2
−2 Pn (bi −ai )2
P(S ≤ −t) ≤ e i=1 .

Démonstration: Par indépendance des Xi ,

n
X
ΛS (λ) = ΛXi −E(Xi ) (λ) .
i=1

D’après le Lemme 3.2.1,

λ2 (bi − ai )2
ΛXi −E(Xi ) (λ) ≤ ,
8
et on conclut en prenant la transformée de Legendre.
Prenons des variables aléatoires Xi i.i.d sur [−b, b]. Lorsque b est nettement plus
grand que l’écart-type des Xi , l’inégalité de Hoeffding peut être très mauvaise
pour des valeurs de t qui ne sont pas trop grandes (penser au théorème central
limite de Lindeberg). Une meilleure inégalité est alors la suivante.
Théorème 3.2.3 (Inégalité de Bennett). Soient X1 , . . . , XP
n des variables aléatoires
n
indépendantes
Pn majorées par un nombre b > 0. Soit S = i=1 (Xi − E(Xi )) et
2
v = i=1 E(Xi ). Alors, pour tout t > 0,
v
P(S ≥ t) ≤ e− b2 h(bt/v) ,
3.2. INÉGALITÉS DE HOEFFDING, BENNETT ET BERNSTEIN 19

où
h(u) = (1 + u) log(1 + u) − u .

Démonstration: On peut supposer b = 1. On note :

φ(x) = ex − x − 1 .

La première remarque est que :

ΛXi −E(Xi ) (λ) ≤ E(φ(λXi )) ,

en utilisant log u ≤ u − 1. Ensuite, la fonction u 7→ u−2 φ(u) est croissante sur R

(par exemple, utiliser la formule de Taylor avec reste intégral). Ainsi, pour tout
λ ≥ 0,
φ(λXi ) ≤ Xi2 φ(λ) ,
donc :
ΛS (λ) ≤ vφ(λ) .
Il suffit alors de calculer la transformée de Legendre du membre de droite, qui
est la log-Laplace d’une loi de Poisson de paramètre v recentrée.
En remarquant que, pour 0 ≤ λ < 3,

λ2
φ(λ) ≤ ,
2(1 − λ/3)

on peut montrer que (prendre λ = u/(1 + u/3)) :

u2
h(u) ≥ .
2(1 + u/3)

On obtient alors le corollaire suivant qui peut être plus facile à interpréter.
Corollaire 3.2.4 (Inégalité de Bernstein). Soient X1 , . . . , Xn desPvariables
n
aléatoires indépendantes
Pn majorées p.s. par un nombre b > 0. Soit S = i=1 (Xi −
2
E(Xi )) et v = i=1 E(Xi ). Alors, pour tout t > 0,
t2
P(S ≥ t) ≤ e− 2(v+bt/3) .

Remarquons que l’inégalité de Bernstein peut être démontrée sous des hy-
pothèses plus faibles portant sur les moments des Xi plutôt que sur leurs sup
essentiels, mais nous n’en auront pas l’utilité.
20 CHAPITRE 3. INÉGALITÉS DE CONCENTRATION

3.3 Exercices
Exercice 3.1 Montrer que les transformées de Laplace et de Cramér sont des
fonctions convexes.
Exercice 3.2 Calculer les transformées de Laplace et de Cramér des lois de
Bernoulli et binomiales, des lois de Poisson et des lois gaussiennes.
Exercice 3.3 Comparer l’inégalité de Hoeffding et celle de Bernstein pour une
somme de Bernoulli i.i.d de paramètre p ≤ 1/2.
Exercice 3.4 On suppose que p = 1/2 et r log n. Montrer qu’a.p.s, dans
G(n, p), tout couple (U, V ) d’ensembles de sommets disjoints de taille supérieure
à r vérifie : r
e(U, V ) C log n
|U |.|V | − p ≤ ,

r
pour une constante C bien choisie. On a noté e(U, V ) le cardinal de l’ensemble
des arêtes menant de U à V .
Chapitre 4

Transition de phase
d’Erdös-Rényi : apparition
de la composante géante

On a vu dans le chapitre 2 que lorsque p = logn n − |ω(1/n)|, G(n, p) n’est pas

connexe et lorsque p = logn n + |ω(1/n)|, G(n, p) est connexe. On a vu également
qu’un peu avant ce seuil, il existait une composante géante contenant de l’ordre
de n sommets. Ceci suggère les questions suivantes : quelle est l’allure des compo-
santes connexes lorsque p ∈]0, logn n [ ? A partir de quel instant G(n, p) contient-il
une composante connexe de taille macroscopique (i.e contenant une proportion
strictement positive de l’ensemble de tous les sommets) ? Peut-il y avoir plu-
sieurs composantes connexes de taille macroscopique ?
Pour k ≥ 1, on notera Ck la k-ème plus grande composante connexe et
Lk = |V (Ck )| son ordre. Si v est un sommet, on note C(v) sa composante
connexe.
Le but de tout ce chapitre sera de montrer le théorème suivant qui montre no-
tamment qu’une unique composante géante (i.e macroscopique) apparait lorsque
p franchit le seuil 1/n. Pour comprendre le comportement fin de cette transition
lorsque p est proche de 1/n, on utilise une paramétrisation p = (1 + ε)/n =
(1 + λn−1/3 )/n avec ε et λ dépendant de n.

Théorème 4.0.1. Soit p = c/n avec c ∈ R∗+ . Les évènements suivants ont lieu
a.p.s.
Cas sous-critique : c < 1 fixé :
— Toutes les composantes connexes sont simples.
— L1 = Θ(log n).
— De plus, pour tout k ≥ 1 fixé, Lk ∼ L1 .
Cas à peine sous-critique : p = 1−ε λ
n avec ε = n1/3 , 1 λ n
1/3
.
— Toutes les composantes sont simples.
— L1 = Θ(ε−2 log λ) = Θ(n2/3 λ−2 ln λ).

21
22 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

— Pour tout k ≥ 1 fixé, Lk ∼ L1 .

−1/3
Fenêtre critique : p = 1+λnn avec λ = Θ(1).
2/3
Pour tout k ≥ 1 fixé, Lk = Θ(n ).
Cas à peine sur-critique : p = 1+ε λ
n avec ε = n1/3 , 1 λ n
1/3
.
2/3
— L1 ∼ 2εn = 2λn
— La complexité de C1 tend vers l’infini.
— Toutes les autres composantes sont simples.
— L2 = Θ(ε−2 log λ) = Θ(n2/3 λ−2 ln λ).
Cas sur-critique : c > 1 fixé :
— L1 ∼ yn avec y = y(c) solution strictement positive de :

1 − y = e−cy . (4.1)

— La complexité de C1 tend vers l’infini.

— Toutes les autres composantes sont simples.
— L2 = Θ(log n).

Faisons deux commentaires. Lorsqu’on regarde uniquement la paramétrisation

p = c/n avec c fixé, on assiste à un “double saut” dans la taille de la plus grande
composante connexe : si c < 1, cette taille est d’ordre log n, lorsque c = 1 elle
est d’ordre n2/3 et lorsque c > 1 elle devient d’ordre n. Ensuite, il n’y a jamais
plus d’une c.c. d’ordre macroscopique.
Comment arriver à un tel résultat ? Une idée simple pour analyser l’ordre
d’une composante connexe est la suivante : on part d’un sommet fixé et on
examine C(v) de proche en proche, en examinant à chaque fois les voisins des
sommets rencontrés. On organise les sommets rencontrés en arbre. En première
approximation, un sommet possède à chaque fois en moyenne np enfants. Au
niveau k, on trouve donc deP l’ordre de (np)k sommets et ainsi la taille totale
de C(v) serait de l’ordre de k (np)k . Ceci explique déjà pourquoi la position
de np par rapport à 1 est importante. Pour rendre cette heuristique rigoureuse,
il faut rendre rigoureux l’analyse “en moyenne” du nombre de descendant. On
va faire ceci avec la notion de processus de branchement et plus précisément
d’arbre de Galton-Watson. Mais il faut également prendre en compte le fait
qu’à chaque étape le nombre de nouveaux voisins possibles diminue. Ceci sera
fait en effectuant une comparaison avec un vrai processus de Galton-Watson.

4.1 Processus de Galton-Watson

4.1.1 Construction par génération
Les processus de Galton-Watson sont des modèles d’arbres aléatoires généalogiques.
L’arbre en question est un arbre enraciné (et étiqueté) et sa loi dépend d’un
paramètre µ qui est une mesure de probabilité sur N et qui représente la loi
de reproduction. La racine correspond à l’ancêtre de la population. L’ancêtre
se reproduit : il a k enfants avec probabilité µ(k), puis meurt. Par la suite,
4.1. PROCESSUS DE GALTON-WATSON 23

chaque enfant se reproduit indépendamment des autres enfants et de ses pa-

rents, puis meurt. Ce processus se poursuit indéfiniment ou jusqu’à ce que la
population s’éteigne. Le terme “processus de Galton-Watson” fait référence en
général à la suite de variables aléatoires (Zn )n≥0 où Zn est la taille de la n-ème
génération. Il peut également faire référence à la suite d’arbres (Tn ) où Tn est
l’arbre généalogique jusqu’à la n-ème génération. Formellement,
(n)
(Li )i≥1,n≥0 i.i.d de loi µ

Z0 = 1
PZn−1 (n)
Zn = i=1 Li , ∀n ≥ 1

On supposera toujours que µ({1}) 6= 1 pour exclure le cas trivial où l’arbre
de Galton-Watson est isomorphe à N de manière déterministe. Remarquons que
(Zn )n≥0 est une chaı̂ne de Markov à valeurs dans N, avec 0 comme unique état
absorbant. L’arbre de Galton-Watson, T = ∪n Tn peut être soit fini, on dit que
la population s’est éteinte, et ceci arrive lorsque Zn atteint l’état absorbant 0,
soit infini. Notons enfin que la donnée de l’arbre de Galton-Watson permet de
retrouver le processus de Galton-Watson.
Peut-on déterminer facilement la probabilité que la population s’éteigne ?
Remarquons tout de suite que le fait que cette probabilité vaille 1 ou non dépend
certainement de la position de c par rapport à 1. En effet, il est facile de voir
que la taille moyenne de la n-ème génération Zn vaut :

E(Zn ) = cn .

Donc, si c < 1, la taille totale de l’arbre de Galton-Watson a une moyenne finie :

X X 1
E(|T |) = E(Zn ) = cn = .
n n
1−c

T est donc fini presque sûrement, et la population s’éteint. Lorsque c ≥ 1, la

taille moyenne de l’arbre devient infini. Cela ne signifie pas que la population
ait nécessairement une probabilité strictement positive de survivre. Nous allons
voir que c’est le cas si et seulement si c > 1. Il est commode d’introduire f , la
fonction génératrice de la loi µ :
(1)
f (z) = E[z Z1 ] = E[z L1 ] .

On note f (n) la n-ème composée de f .

Proposition 4.1.1. La fonction génératrice de Zn est donnée par :

E[z Zn ] = f (n) (z) .

La probabilité d’extinction est donnée par :

q = lim f (n) (0) .

n∞
24 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

q est la plus petite racine de l’équation f (z) = z dans [0, 1], et

q=1⇔c≤1.

Démonstration: Pour n ≥ 1,
E[z Zn ] = E[E[z Zn |Zn−1 ]] ,
Zn−1
Y (n)
= E[ E[z Li ]] ,
i=1
= E[f (z)Zn−1 ] ,
donc par récurrence,
E[z Zn ] = f (n) (z) .
L’évènement “extinction” est la réunion des évènements {Zn = 0}, qui forment
une suite croissante. Ainsi,
q = lim P(Zn = 0) = lim f (n) (0) .
n∞ n∞

Donc q est la limite de la suite définie par u0 = f (0) ≤ 1 et un+1 = f (un ).

Comme f est une fonction continue sur [0, 1], q est solution de f (z) = z. De
plus, f est croissante et f (0) ≥ 0 donc f est stable sur [0, q ∗ ] où q ∗ est l’inf de
{x t.q. f (x) = x} (ensemble non vide car 1 est dedans). Ainsi, q = q ∗ et c’est
la plus petite racine de l’équation f (z) = z dans [0, 1]. De plus, q = 1 implique
que f (x) ≤ x pour tout 0 ≤ x ≤ 1, donc f (1) − f (x) ≤ 1 − x donc f 0 (1) ≤ 1,
or c = E(Z1 ) = f 0 (1) donc c ≤ 1. Enfin, si L1 prend seulement les valeurs 0 et
1, et que f 0 (1) ≤ 1, alors par hypothèse, comme P(L1 = 1) < 1 on a f (z) < z
pour tout z < 1, et donc q = 1. Sinon, f est strictement convexe et donc c ≤ 1
implique que f (1) − f (x) < 1 − x pour tout x < 1, et donc q = 1.
Donnons deux exemples de calcul de probabilités de survie. Si µ est une loi de
Poisson de paramètre c, alors :
f (z) = ec(z−1) .
Si c ≤ 1, le processus de Galton-Watson s’éteint avec probabilité 1. Si c > 1, il
survit avec probabilité y définie par :
y > 0 et 1 − y = e−cy . (4.2)
Comme le nombre de voisins d’un sommet dans G(n, c/n) est à peu près une loi
de Poisson de paramètre c, ceci explique l’apparition de l’équation 4.2 dans le
théorème 4.0.1. ************ Dessin *********
Prenons un autre exemple, où µ est une loi binomiale de paramètres m et p.
Alors,
f (z) = (1 − p + pz)m .
Si mp ≤ 1, le processus de Galton-Watson s’éteint avec probabilité 1. Si c > 1,
il survit avec probabilité y définie par :
y > 0 et 1 − y = (1 − yp)m . (4.3)
4.1. PROCESSUS DE GALTON-WATSON 25

4.1.2 Codage par une marche aléatoire

Nous utiliserons surtout un codage de l’arbre de Galton-Watson sous forme
d’une marche aléatoire (St )t∈N associée. Dans ce cas, l’indice des temps n’est
pas celui des générations, mais correspond à un parcours en largeur de l’arbre.
L’ancêtre se reproduit et meurt, ses enfants sont ordonnés, puis les enfants se
reproduisent dans cet ordre (et meurent). Chaque progéniture est ordonnée, ce
qui fournit un ordre des petits-enfants etc. On associe ainsi à chaque noeud de
l’arbre un numéro, l’ancêtre ayant le numéro 1. ***** dessin **** Soit Lt le
nombre d’enfants de l’individu t : (Lt )t≥1 est une suite i.i.d de loi µ. Notons St
le nombre d’individus vivants au temps t. Entre les temps t − 1 et t, l’individu
t a Lt enfants puis meurt. Ainsi,
(Lt )t≥1 i.i.d de loi µ

S0 = 1
(4.4)
St = St−1 + Lt − 1, ∀t ≥ 1

On voit donc que (St )t≥0 est une marche aléatoire à valeurs dans Z, partant
de 1. Une caractéristique importante de cette loi est que la seule valeur stricte-
ment négative qu’elle peut prendre est -1. Ainsi, elle ne peut pas sauter d’entier
lorsqu’elle descend (en anglais, on dit qu’elle est skip free).
Rigoureusement, ceci ne peut être défini que tant que le processus de Galton-
Watson ne s’éteint pas, c’est à dire tant que t ≤ T , où T est l’instant d’extinction
défini par :
T = inf{t ≥ 0 t.q. St = 0} .
Néanmoins, il est plus pratique de définir la marche aléatoire ci-dessus avec une
suite infinie de Lt . Cela ne change pas, bien sûr, la loi de T . Notons que T est
le nombre total de noeuds de l’arbre de Galton-Watson.
Supposons que c = E(Lt ) < ∞. Lorsque c < 1, la marche aléatoire possède
ce qu’on appelle une dérive négative, puisque E(St ) = (c − 1)t + 1. Notamment,
la loi des grands nombres nous dit que St tend p.s. vers −∞, donc la population
va s’éteindre presque sûrement. Si c > 1, St tend p.s. vers +∞, et ceci suggère
que la population a une chance d’exploser. Lorsque c = 1 la marche aléatoire a
une dérive nulle, c’est le cas le plus délicat à traiter.
Le second résultat que nous utiliserons est une formule exacte pour la loi de
T en fonction de la probabilité que Sn vaille 0.

Théorème 4.1.2. Si on part de S0 = k ≥ 1 ancêtres,

k
∀n ≥ 0, P(T = n) = P(Sn = 0) .
n
En particulier, lorsque S0 = 1,

1
∀n ≥ 0, P(T = n) = P(Sn = 0) .
n
26 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

Démonstration: Cela revient à montrer que :

k
P(T = n|Sn = 0) = .
n
On pense à l’intervalle de temps {1, . . . , n} modulo n, arrangé sur un cercle. Re-
marquons que la loi de (L1 , . . . , Ln ) conditionnellement à Sn = 0 est invariante
par permutation circulaire de {1, . . . , n}. Le théorème est alors une conséquence
du Lemme 4.1.3.

Lemme 4.1.3. Pour toute suite d’entiers (l1 , . . . , ln ) tels que li ≥ −1 et k +

P n
i=1 li = 0, il y a exactement k indices i tels que :

n = min{j ≥ 1 t.q. k + li+1 + . . . + li+j = 0} .

Pi
Démonstration: On note si = j=1 li . On note R = {i1 < . . . < ir } l’ensemble
des instants auxquels (l1 , . . . , ln ) atteint un record inférieur :

R = {i t.q. ∀j < i, sj < si } .

Notons m le minimum de la suite s1 , . . . , sn . Comme li ≥ −1, on a :

si1 = k, si2 = k − 1, . . . , sir = m . (4.5)

Notons I l’ensemble des indices i tels que :

n = min{j ≥ 1 t.q. k + li+1 + . . . + li+j = 0} .

un indice i appartient à I si et seulement si c’est un élément de R tel que :

∀j ≥ i, sj − si ≥ −k + 1 ,

ce qui revient à demander :

m − si ≥ −k + 1 .

Au vu de (4.5), il y a exactement k indices de R vérifiant ceci, ce sont les k

instants de plus petits records.
Notamment, si µ est une loi de Poisson de paramètre c, la loi de t + St − S0 est
une loi de Poisson de paramètre ct, donc :

e−ct
P(Tcpo = t) = t! . (4.6)
(ct)t−1

Si µ est une loi binomiale B(n, p), avec p = c/n, la loi de t + St − S0 est une
binomiale B(nt, c/n), donc :

bin 1 nt c t−1 c nt−t+1
P(Tn,p = t) = 1− . (4.7)
t t−1 n n
4.1. PROCESSUS DE GALTON-WATSON 27

4.1.3 Processus de branchement du graphe

Le processus de branchement du graphe aléatoire G(n, p) est le processus de

branchement obtenu en parcourant en largeur la composante connexe C(v) d’un
sommet v dans le graphe aléatoire G(n, p). Ce n’est pas tout à fait un proces-
sus de Galton-Watson, mais on l’analysera en le comparant à des processus de
Galton-Watson. Décrivons plus précisément ce processus. On part de la racine
v. Tous les sommets du graphe seront soit vivants, soit morts, soit neutres. Au
temps 0, seul v est vivant, et tous les autres sommets sont neutres. A chaque
instant t ≥ 1, on examine le sommet w qui est en tête de la liste des sommets
vivants et on examine l’ensemble des arêtes {w, w0 } avec w0 neutre. Si l’arête
{w, w0 } est dans G(n, p), on ajoute w0 au bout de la liste des sommets vivants
et on l’enlève de la liste des sommets neutres. Dans tous les cas, on déplace w
de la liste des sommets vivants à la liste des sommets morts. On peut arrêter la
procédure quand la liste des sommets vivants est vide. On note T cet instant. Au
temps T l’ensemble des sommets morts est exactement la composante connexe
de v, et ainsi T = |C(v)|. Reprenons maintenant la procédure d’exploration à
l’instant T et poursuivons-la comme suit : comme il n’y a plus de sommet vivant,
on choisit un nouveau sommet parmi les sommets neutres, et à l’étape d’après
(au temps T + 1) on recommence l’exploration de sa composante connexe : on le
déclare mort (on l’enlève de la liste des sommets neutres), et on déclare vivants
tous ses voisins qui étaient neutres. On note At le nombre de sommets vivants
à l’instant t, Ñt le nombre de sommets neutres et L̃t le nombre de sommets
auparavant neutres ajoutés à la liste des sommets vivants à l’instant t. Si on
note T0 = 0 puis, pour i ≥ 0, Ti+1 = inf{t > Ti t.q. At = 0} alors Ti+1 − Ti est
la taille de la i-ème composante connexe explorée et T1 = T . Remarquons que
At+1 = At + L̃t+1 −1, sauf lorsque t est l’un des Ti , auquel cas At+1 = At + L̃t+1 .
De plus, conditionnellement au passé jusqu’à l’instant t − 1 compris, L̃t est de
loi B(Ñt−1 − 1At−1 =0 , p). On a donc :

Ñ0 = n − 1, A0 = 1

 L̃t ∼ B(Ñt−1 − 1At−1 =0 , p) conditionnellement à Ñt−1



∀t ≥ 1 A = At−1 + L̃t − 1 + 1At−1 =0 (4.8)

 t
Ñt = Ñt−1 − L̃t − 1At−1 =0

A obéit à une équation similaire à (4.4). Remarquons que (At )t≥0 n’est pas
une marche aléatoire au sens usuel, notamment car les variables aléatoires L̃t
ne sont pas i.i.d. L’irruption du terme 1At−1 =0 dans la définition de L̃t est la
plus gênante. On définit un processus plus simple de la façon suivante :
28 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

N0 = n − 1, S0 = 1

 Lt ∼ B(Nt−1 , p) conditionnellement à Nt−1
∀t ≥ 1 St = St−1 + Lt − 1 (4.9)
Nt = Nt−1 − Lt


On peut voir ce processus de la façon suivante, sur le graphe d’Erdös-Rényi :

on explore les composantes connexes de la façon classique, sauf qu’à chaque fois
qu’on a fini d’explorer une composante, on introduit un nouveau sommet, qu’on
relie aux sommets neutres par des arêtes selon la loi de Bernoulli usuelle, puis ce
sommet meurt tout de suite. St désigne alors le nombre de sommets vivants dans
la composante connexe en cours d’exploration moins le nombre de composantes
déjà totalement explorées. L’avantage principal de St est qu’on peut calculer
simplement sa loi à l’instant t, et le comparer qu processus original At .
Proposition 4.1.4. A chaque instant t ≥ 0,

St + Nt + t = n et At + Ñt + t = n .

De plus, St est de loi B(n − 1, 1 − (1 − p)t ) − t + 1 et on peut coupler A et S de

sorte que pour tout t ≥ 0 :
t−1
1As =0 .
X
At ≥ St ≥ At −
s=0

Notamment, At = St tant que t ≤ T .

Enfin, si 0 ≤ t1 ≤ t2 , conditionnellement à St1 , St2 − St1 suit une loi B(n −
St1 − t1 , 1 − (1 − p)t2 −t1 ) − t2 + t1 .

Démonstration: Il est clair que St +Nt +t = n, puisque St −St−1 = Nt−1 −Nt −1

et que S0 +N0 = n. De même, At −At−1 = Ñt−1 −Ñt −1 montre que At +Ñt +t =
n.
Soit (Xt,i )t≥1,i≥1 une collection de variables aléatoires i.i.d de loi de Bernoulli
de paramètre p. Xt,i va désigner l’état de la i-ème arête inspectée au temps t,
lorsqu’on examine les voisins possibles d’un sommet. On peut coupler A et S
comme suit :
PÑt−1 −1At−1 =0

 L̃t = i=1

 Xt,i
∀t ≥ 1 At = At−1 + L̃t − 1 + 1At−1 =0
 Ñ = PÑt−1 −1At−1 =0 (1 − X )


t i=1 t,i

et :  PNt−1
 Lt = i=1 Xt,i
∀t ≥ 1 St = St−1 + Lt − 1
PNt−1
(1 − Xt,i )

Nt = i=1
On voit donc (par une récurrence immédiate) que pour tout t, Ñt ≤ Nt . Comme
St + Nt + t = n et At + Ñt + t = n, on en déduit que St ≤ At . Et d’après les
4.2. CAS SOUS- ET SUR-CRITIQUE 29

formules pour Lt et L̃t , on en déduit aussi que Lt ≥ L̃t . Et donc que St ≥

At − s=0 1As =0 .
Pt−1
Par ailleurs, on peut aussi réaliser les Nt de la façon suivante :
n−1
X t
Y
Nt = (1 − Xs,i ) ,
i=1 s=1

en voyant la situation depuis le stock des n − 1 sommets neutres du début : à

chaque instant t, le sommet i est retiré du stock des neutres si Xt,i = 1. Donc
Nt suit une loi B(n − 1, (1 − p)t ), et par conséquent St est de loi B(n − 1, 1 −
(1 − p)t ) − t + 1. On voit aussi que pour t1 ≤ t2 ,

n−1 t1 t2
! Nt1 t2
!
XY Y X Y
Nt1 −Nt2 = (1−Xs,i ) 1 − (1 − Xs,i ) = 1− (1 − Xs,i ) .
i=1 s=1 s=t1 +1 i=1 s=t1 +1

Donc conditionnellement à Nt1 , Nt1 − Nt2 suit une loi B(Nt1 , 1 − (1 − p)t2 −t1 ),
et donc conditionnellement à St1 , St2 − St1 suit une loi B(n − St1 − t1 , 1 − (1 −
p)t2 −t1 ) − t2 + t1 .

4.2 Cas sous-critique et sur-critique : premiers

résultats
Nous allons d’abord démontrer quelques résultats du Théorème 4.0.1 qui
ont lieu loin de la transition, c’est à dire quand p = c/n avec c fixé différent de
1. Dans cette section, on utilise les notations du processus de branchement de
graphe.

4.2.1 Cas sous-critique

Nous allons montrer que lorsque p = c/n avec c < 1 fixé, pour tout δ > 0,
a.p.s,
(1 + δ)
L1 ≤ log n ,
J(c)
où
J(c) = c − 1 − log c .
On peut aussi montrer une inégalité dans l’autre sens, mais ceci sera fait de
manière plus générale plus tard. Soit t ≥ 0. Remarquons que

P(|C(v)| > t) = P(T > t) ≤ P(St ≥ 1) .

En utilisant la proposition 4.1.4,

P(St ≥ 1) = P(B(n − 1, 1 − (1 − p)t ) ≥ t) .

30 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

On veut montrer que ceci est petit lorsque t = (1+δ)

J(c) log n. Dans ce cas, 1−(1−p)
t

est d’ordre tp, donc on ne perd pas grand chose à majorer 1 − (1 − p)t par tp et
n − 1 par n. On obtient :

P(St ≥ 1) ≤ P(B(n, tp) ≥ t) .

On utilise alors la borne de Cramér-Chernoff (cf. chapitre 3) :

∗
P(B(n, q) ≥ t) ≤ e−nΛB(q) (t/n) ,

Or,
u 1−u
Λ∗B(q) (u) = u log + (1 − u) log ,
q 1−q
On va l’utiliser avec u = t/n et q = tp = tc/n, donc u et q tendent vers 0 et u/q
tend vers 1/c. On a alors :
1
Λ∗B(q) (u) = u log + cu − u + o(u) = uJ(c) + o(u) .
c
Donc :
nΛ∗B(tp) (t/n) = J(c)t + o(t) .
D’où :
P(|C(v)| > t) ≤ e−(1+δ)(1+o(1)) log n ,
Donc,
P(L1 > t) ≤ nP(|C(v)| > t) = o(1) .

4.2.2 Cas sur-critique

Nous allons montrer les résultats suivants lorsque p = c/n avec c > 1 fixé.
1. L1 ∼ ny(c) ,
2. L2 = O(log n) ,
3. la complexité de C1 est au moins d’ordre n, les autres composantes
connexes sont simples.

Existence d’une grande composante

L’idée générale est simple : soit α ∈ R+ ∗ et t ≤ n de la forme t = ny(c)α.
On remarque que :

E(St ) = n(1 − (1 − p)t ) − t + 1 ,

t − tc
= n 1 − − e n + O(1) ,
n
E(St ) = nφ(y(c)α) + O(1) . (4.10)

où φ(x) = 1 − x − e−cx . De plus, une inégalité de concentration comme celle

d’Hoeffding (cf. chapitre3) montre que les fluctuations de St autour de sa moyenne
4.2. CAS SOUS- ET SUR-CRITIQUE 31

√
sont au plus d’ordre n. Or φ est strictement concave, s’annule exactement en 0
et en y(c). Donc elle est strictement positive sur ]0, y(c)[ et strictement négative
sur ]y(c), +∞. Fixons δ ∈]0, 1/3[. Ainsi, avec très grande probabilité, on va voir
que St est strictement négative pour t ≥ (1+δ)ny(c) et strictement positive pour
t dans [δny(c), (1 − δ)ny(c)]. Le premier point permettra de montrer qu’a.p.s,

L1 ≤ ny(c)(1 + δ) . (4.11)

Le second point implique que At > 0 sur cet intervalle de temps, et donc que :

L1 > ny(c)(1 − 2δ) (4.12)

On peut alors trouver δ = δn une suite tendant vers 0 telle que les convergences
aient encore lieu, ce qui montre que L1 ∼ ny(c), a.p.s.
Prouvons (4.11). Pour t = ny(c)(1 + δ), E(St ) est éngative d’après (4.10).
En utilisant l’inégalité de Hoeffding,

P(|C(v)| > t) ≤ P(St ≥ 0) ,

= P(St − E(St ) ≥ −E(St )) ,
E(St )2
≤ e−2 n ,
−2nφ2 (y(c)(1+δ))+O(1)
= e .

Par conséquent,
2
P(L1 ≥ ny(c)(1 + δ)) ≤ ne−2nφ (y(c)(1+δ))+O(1)
= o(1) .

Passons à la preuve de (4.12). Pour t ∈ [δny(c), (1 − δ)ny(c)], E(St ) est positive,

donc :

P(St ≤ 0) ≤ P(St − E(St ) ≤ −E(St )) ,

E(St )2
≤ e−2 n ,
−2nφ2 (y(c)(1+δ))+O(1)
= e .

Ainsi,

P(L1 ≤ (1 − 2δ)ny(c)) ≤ P(∃t ∈ [δny(c), (1 − δ)ny(c)] St ≤ 0) ,

(1−δ)ny(c)
X
≤ P(St ≤ 0) ,
t=δny(c)
2
≤ ne−2nφ (y(c)(1+δ))+O(1)
,
= o(1)

Unicité de la grande composante

On a montré que si p = c/n avec c > 1 fixé, la plus grande composante
connexe a une taille équivalente à ny(c). On veut maintenant montrer qu’il ne
32 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

peut y avoir deux composantes de cette taille. On choisit p2 = n−3/2 et on pose

p0 = 1−(1−p)(1−p2 ) ∼ c/n = p. Prenons maintenant un graphe G de loi G(n, p)
et un graphe G2 indépendant de G et de loi G(n, p2 ). Alors G0 := G ∪ G2 est de
loi G(n, p0 ). Si G contenait au moins deux composantes de taille équivalente à
ny(c), avec probabilité tendant vers 1, ces deux composantes seraient reliées dans
G∪G2 . En effet, ces deux composantes étant fixées, il y a un nombre équivalent à
y(c)2 n2 arêtes qui les relient. La probabilité qu’aucune de ces arêtes ne soit dans
2 2
G2 est inférieure (1 − p2 )y(c) n (1−o(1)) = o(1). On aurait donc une composante
de taille équivalente à 2ny(c) dans G0 . Mais d’après le paragraphe précédent,
a.p.s G0 ne contient pas de composante de taille supérieure à (1 + δ)ny(c). Donc,
G ne contient pas plus d’une composante géante.

Dualité

Soit G ∼ G(n, p). Maintenant, on considère la loi du graphe G \ C1 , où on a

enlevé la plus grande composante connexe (qui est unique avec proba tendant
vers 1). A isomorphisme près, et conditionnellement à |C1 | = n − k, la loi de
ce graphe est la loi G(k, p) conditionnée à ne pas contenir de composante de
taille supérieure ou égale à n − k (cf. Lemme 4.2.1 et le fait qu’avec proba
tendant vers 1 il n’y a qu’une composante connexe de taille maximale). Or, avec
proba tendant vers 1, |C1 | est équivalente à ny(c). Pour un entier k équivalent
à n(1 − y(c)),
c 1 k 1
p = = c ∼ c(1 − y(c)) .
n k n k
Or c(1 − y(c)) < 1, car :

1 1 1 1 y
y = log < −1 = .
c 1−y c 1−y c(1 − y)

On est donc dans la phase sous-critique : G(k, p) = G(k, (c∗ + o(1))/k) avec
c∗ = c(1 − y(c)). Ainsi, si δ > 0, a.p.s. G(k, p) ne possède pas de composante
1+δ
de taille supérieure à J(c ∗ ) log k, et donc pas de composante de taille supérieure

à n − k. Ainsi, pour tout ce qui est propriété de graphe, la loi de G \ C1 est,

sachant |C1 | = n − k (à un évènement de proba tendant vers 0 près) la loi de
G(k, (c∗ +o(1))/k). Notamment, G\|C1 | ne contient pas de composante connexe
1+δ 1
de taille plus grande que J(c ∗ ) log k, donc L2 . J(c∗ ) log n.

Lemme 4.2.1. Soit l et k deux entiers tels que l + k ≤ n. Soit G distribué

comme G(n, p). On note C la réunion de toutes les composantes connexes de G
de taille supérieure ou égale à l et G 0 = G \ C. Alors, pour tout graphe G à k
sommets,

P(G 0 ∈ On (G)|card(V (G 0 )) = k) = P(G(k, p) ∈ Ok (G)|card(C1 (G(k, p))) < l) .

où On (G) l’orbite de G dans Kn .

4.2. CAS SOUS- ET SUR-CRITIQUE 33

Démonstration: Soit G = (V, E) un sous-graphe de la clique Kn tel que |V | = k

et tel que C1 (G) soit d’ordre strictement inférieur à l. On note B(V c ) l’évènement
“V c est la réunion de composantes connexes (pas nécessairement toutes) de G
de tailles supérieures ou égales à l”. C’est un évènement indépendant de G[V ].
De plus, sa probabilité ne dépend que de k : notons-la αk .

P(G 0 = G) = αk P(G[V ] = G) .

Si C1 (G) ≥ l, P(G 0 = G) = 0. Donc,

X
P(G 0 ∈ On (G)) = αk P(G[V (H)] = H) ,
H∈On (G)
X
n
= αk P(G[Kk ] = H) ,
k
H∈Ok (G)

n
= αk P(G(k, p) ∈ Ok (G)) .
k

De même,
X
P(|V (calG0 )| = k) = P(calG0 = G) ,
G⊂Kn
|C1 (G)|<l
|V (G)|=k

n X
= αk P(G[Kk ] = H) ,
k
H⊂Kk
|C1 (H)|<l

n
= αk P(|C1 (G(k, p))| < l) .
k

Donc, pour tout sous-graphe G de la clique Kn tel que |V | = k,

P(G 0 ∈ On (G)) = P(|V (G 0 )| = k)P(G(k, p) ∈ Ok (G)|card(C1 (G(k, p))) < l) .

Et plus généralement, pour tout sous-graphe G de la clique Kn ,

n
X
P(G 0 ∈ On (G)) = P(|V (G 0 )| = k)P(G(k, p) ∈ Ok (G)|card(C1 (G(k, p))) < l) .
k=0

Dit autrement,

P(G 0 ∈ On (G)|card(V (G 0 )) = k) = P(G(k, p) ∈ Ok (G)|card(C1 (G(k, p))) < l) .

34 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

Complexité de la composante géante

On note p1 = (1 + (c − 1)/2)/n et p2 tel que p = 1 − (1 − p1 )(1 − p2 ). Soit
G1 ∼ G(n, p1 ) et G2 ∼ G(n, p2 ) indépendants et G = G1 ∪ G2 ∼ G(n, p). On
remarque que p2 ∼ (c − 1)/(2n) et que c0 = 1 + (c − 1)/2 > 1. Donc il existe
a.p.s. une unique composante connexe de taille équivalente à ny(c0 ) dans G1 .
Dans G1 ∪ G2 , il existe une unique composante connexeC1 de taille équivalente
1
à ny(c), et cette composante connexe est la seule de taille supérieure à J(c) log n
donc la composante géante de G1 est en fait incluse dans celle de G. Mais l’ajout
de G2 apporte un grand nombre d’arêtes internes en excès à cette composante
connexe : un nombre qui suit au moins une loi B( ny(c)(1−δ)
2 − ny(c) + 1, c0 /n),
0
donc un nombre d’arêtes qui est équivalent à ny (c)c (1 − δ)2 /4 = Ω(n). Par
2

dualité, on montre également que les autres composantes connexes sont simples.

4.3 Explication de la paramétrisation dans le cas

à peine sur-critique
On peut maintenant comprendre la paramétrisation justifiant que la com-
posante géante apparaisse après (1 + λn−1/3 )/n. En se souvenant du cas sur-
critique, on voit que l’apparition d’une composante géante est dûe à la forme
de la fonction t 7→ E(St ) donnée par (4.10). Cette moyenne dépasse 0 sur
une longueur d’ordre ny(c) qui est équivalent à 2nε lorsque ε tend vers 0 (cf.
Lemme 4.3.1). Après ny(c)(1+δ), la moyenne plonge trop vite pour qu’on puisse
encore explorer une grande composante. Mais quand t est d’ordre nε (pour t/n
2
√ y(c)[),√St a une moyenne d’ordre (c − 1)t ∼ nε et des fluc-
dans l’intervalle ]0,
tuations d’ordre ct ∼ nε. Ainsi, St ne va suivre sa moyenne d’assez près
et rester positive sur presque tout √[0, ny(c)] que si les fluctuations sont petites
devant sa moyenne, c’est à dire si nε nε2 , ce qui donne ε n−1/3 .
Lemme 4.3.1 (Probabilité de survie du processus de Poisson quand ε tend vers
0). On suppose que ε > 0 et on note y(c) la probabilité de survie d’un processus
de Galton-Watson ayant une loi de reproduction de Poisson de paramètre c.
Alors, quand ε tend vers 0+ ,
y(1 + ε) = 2ε + o(ε) .

Démonstration: On note y la probabilité de survie. D’après l’équation (4.2), on

sait qu’elle est définie comme la plus petite solution de :
y > 0 et 1 − y = e−cy .
Donc, en utilisant y 6= 0 pour diviser par y :
y2
1−y = 1 − yc + + o(y 2 ) ,
2
y2
+ o(y 2 ) = yε ,
2
y + o(y) = 2ε .
4.4. CAS CRITIQUE 35

D’où le résultat.

4.4 Cas critique

Nous voulons montrer que L1 est d’ordre n2/3 dans le cas critique, c’est à dire
lorsque p = (1 + ε)/n et ε = λn−1/3 avec λ d’ordre 1. Lorsqu’on veut analyser
plus en finesse l’exploration d’une composante connexe dans le graphe d’Erdös-
Rényi, on se retrouve naturellement avec trois processus de branchement. En
effet, on peut penser que si p = c/n, et tant que t n’est pas trop grand, le
processus de branchement du graphe va se comporter comme un processus de
Galton-Watson de loi de reproduction B(n − 1, c/n), qui lui-même va se com-
porter comme un processus de Galton-Watson de loi de reproduction P(c). On
a donc 3 processus différents : le processus de graphe, le processus binomial et
le processus de Poisson. On utilisera les annotations gr pour graphe, bin pour
binomial et po pour Poisson pour distinguer ces trois processus lorsque ce sera
nécessaire. On indiquera leurs paramètres en indice.

4.4.1 Borne supérieure sur L1

Nous allons majorer la taille d’une composante connexe par la taille d’un
arbre de Galton-Watson poissonien.
Lemme 4.4.1. Pour tout t ≥ 1,
bin
P(|C(v)| ≥ t) ≤ P(Tn−1,p ) ≥ t) .
et si c > 3/2, pour n assez grand, et pour tout t ≥ 1,
bin
P(Tn−1,p ) ≥ t) ≤ P(Tcpo ) ≥ t) .

Démonstration: La première inégalité est claire, puisque les incréments de St

dans le processus de graphe sont majorés par des incréments de loi B(n−1, p)−1.
Soit X une v.a de loi B(c/(n + 1)) et Y une v.a de loi P(c/n).
c
P(X = 0) = 1− ,
n+1
c c
= 1 − + 2 + O(n−3 ) ,
n n
2
c − c2
= P(Y = 0) + + O(n−3 ) ,
n2
≥ P(Y = 0) ,

pour n assez grand, si c ∈]0, 3/2]. On en déduit que X est inférieure stochasti-
bin
quement à Y , donc que B(n − 1, p) est inférieure à P(c), et donc que Tn−1,p est
inférieure à Tcpo .
36 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

L’analyse du processus de branchement de Poisson dans le cas presque critique

est menée dans le Lemme 4.5.1. Soit A > 0 un nombre réel. On obtient :
Z +∞
|λ|
po 2/3
P(+∞ > Tc ≥ An ) . 1/3 x−3/2 e−x dx .
n Aλ2

De plus, P(Tcpo = +∞) ∼ max(2ε, 0). Donc :

n
P(L1 ≥ An2/3 ) ≤ P(|C(v)| ≥ An2/3 ) ,
An2/3
n1/3
. P(Tcpo ≥ An2/3 ) ,
A
Z +∞
n1/3

|λ|
. max(2ε, 0) + 1/3 x−3/2 e−x dx ,
A n Aλ2
Z +∞
|λ|
. 2+ x−3/2 e−x dx ,
A Aλ2

2|λ| 1
. 1+ √ ,
A |λ| A

Ce qui montre que L1 = OP (n2/3 ).

4.4.2 Le cas des arbres

Nous allons montrer qu’a.p.s, il existe au moins un arbre d’ordre n2/3 dans la
fenêtre de transition. Pour simplifier les calculs, on prendre p = 1/n exactement.
On note Tk le nombre de composantes connexes qui sont des arbres d’ordre k,
et pour b > a > 0 fixés, on note
2/3
bn
X
X= Tk .
k=an2/3

On calcule d’abord le premier moment de X.

n k−2 k−1 k
E(Tk ) = k p (1 − p)k(n−k)+(2)−(k−1) .
k

En utilisant la formule de Stirling pour k de l’ordre de n2/3 ,

n−k
nk

n n
∼ √ ,
k n−k kk 2πk
k2 k3 nk

k
(n−k) n−k − 2(n−k)2 + 3(n−k)3 +o(1)
= e √ ,
k k 2πk
k2 k3 nk
= ek− 2n − 6n2 +o(1) √ ,
k k 2πk
4.4. CAS CRITIQUE 37

et :
k k2
(1 − p)k(n−k)+(2)−(k−1) = (1 − p)kn− 2 (1 + o(1)) ,
k2
)(−p+O(p2 ))
= e(kn− 2 (1 + o(1)) ,
2
−knp+ k 2 p
= e (1 + o(1)) .

D’où, pour p = n−1 :

n k3
E(Tk ) = √ e− 6n2 (1 + o(1)) .
k 5/2 2π
k 1
Ainsi, en posant xk = n2/3
, xk+1 − xk = n2/3
,
2/3
bn
X n k3
E(X) = √ e− 6n2 (1 + o(1)) ,
k=an2/3
k 5/2 2π
2/3
bn
X 1 x3
k
= 5/2 √
e− 6 (xk+1 − xk )(1 + o(1)) ,
k=an2/3
xk 2π
b x3
e− 6
Z
∼ √ dx .
a x5/2 2π
On remarque que cette limite tend vers +∞ lorsque a tend vers 0. Par ailleurs,
X
E[X(X − 1)] = P[T etT 0 sont des c.c.] ,
T 6=T 0
de taille∈[an2/3 ,bn2/3 ]
2/3 2/3
bn bn
X X n n − k k−2 0 k0 −2 k−1+k0 −1
= k (k ) p
k k0
k=an2/3 k0 =an 2/3

0 0 0 k k0 0
×(1 − p)(k+k )(n−k−k )+kk +(2)+( 2 )−k+1−k +1 ,
2/3 2/3
bn bn n−k

X X 0 0
= E(Tk )E(Tk0 ) n−k (1 − p)kk .
k

k=an2/3 k0 =an2/3 k0

Or,
k2 k3 k
n−k ek− 2n − 6n2 +o(1) kk √
n

k0 2πk
n−k
= k2 k3
,
ek− 2n − 6n2 +o(1) kk √
n k
k0
2πk
kk0 02 2 0
− kk − k2nk2 +o(1)
= e− n 2n2 ,

et
0 kk0
(1 − p)−kk = e n +o(1)
,
38 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI

Donc :
E[X(X − 1)] . E(X)2 .
Soit A l’évènement “il existe une c.c. qui soit un arbre de taille supérieure à
an2/3 ”.
E(X)
P(A) ≥ ,
E(X 2 )
1
& 1 .
1 + E(X)

Et ce nombre tend vers 1 quand a tend vers 0.

4.5 Analyse du processus de branchement de

Poisson
Dans cette section, on analyse la formule (4.6) avec c ∈ R∗+ . Lorsque c = 1,
on obtient :
e−k k k−1 1
P(T1 = t) = ∼√ .
k! 2πt3/2
q
2
Ainsi, P(T1 ≥ t) ∼ tπ qui décroit lentement vers 0. Remarquons que T1 est
p.s. fini, mais de moyenne infinie. En général, quand t tend vers l’infini,
1
P(Tc = t) = √ t−3/2 c−1 (ce1−c )t (1 + ot (1)) . (4.13)
2π
Remarquons déjà que ceci décroit vers 0 à vitesse exponentielle si c 6= 1 est fixe.
Dans ce cas,
P(+∞ > Tc ≥ u) < e−u(J(c)+o(1)) , (4.14)
où J(c) = c − 1 − ln c > 0. Pour analyser les cas critique et à peine sous- ou
sur-critique, il faut aussi comprendre la distribution de T1+ε avec ε qui tend vers
0 par valeurs positives ou négatives. Le lemme suivant résume le comportement
de P(+∞ > Tc ≥ u) lorsque u tend vers l’infini. On note Γ−1/2 (x) la fonction
gamma incomplète de paramètre −1/2 :
Z +∞
Γ−1/2 (x) = t−3/2 e−t dt ∼x→+∞ x−3/2 e−x .
x

Lemme 4.5.1. On suppose que u tend vers l’infini. Alors,

J 1/2 (c) J 1/2 (c)
√ Γ−1/2 (uJ(c)) . P(+∞ > Tc ≥ u) . √ Γ−1/2 ((u − 1)J(c)) .
c 2π c 2π
Notamment, si c = 1 + ε avec ε tendant vers 0, positif ou négatif, et uJ(c) tend
vers l’infini,
2u−3/2 2
P(+∞ > Tc ≥ u) ∼ √ e−uε /2 .
2
ε 2π
4.6. COMPLÉMENTS 39

Démonstration:
 
1 X −3/2 −tJ(c) 
P(+∞ > Tc ≥ u) = √ t e (1 + ou (1)) .
c 2π t≥u

Or,
Z +∞ X Z +∞
t−3/2 e−tJ(c) dt ≤ t−3/2 e−tJ(c) ≤ t−3/2 e−tJ(c) dt ,
u t≥u u−1

et : Z +∞
t−3/2 e−tJ(c) dt = J 1/2 (c)Γ−1/2 (uJ(c)) .
u
On en déduit le résultat.
Rappelons que nous avons vu dans le Lemme ref que P(T1+ε = +∞) ∼ 2ε
lorsque ε tend vers 0+ .

4.6 Compléments
Les cas à peine sous-critique et à peine sur-critique n’ont pas été vus en
cours, faute de temps. Vous pourrez trouver des preuves dans le Chapitre A.
40 CHAPITRE 4. TRANSITION DE PHASE D’ERDÖS-RÉNYI
Chapitre 5

Coloriages, nombre clique

et nombre d’indépendance

Un coloriage (par sommets) d’un graphe est une fonction de l’ensemble des
sommets du graphe dans un ensemble fini, l’ensemble des couleurs, de sorte
que deux sommets voisins ne se voient pas associés la même couleur. Le but de
ce chapitre est principalement de montrer que minimal de couleurs nécessaire
n
pour colorier G(n, 1/2) est équivalent à 2 log . Ce nombre est appelé le nombre
2n
chromatique.

5.1 Introduction
Historiquement, il semble qu’un rôle important dans le développement de
cette notion ait été joué par le coloriage des cartes planaires. A une carte
géographique, on peut associer un graphe où chaque pays est représenté par
un sommet et une frontière entre deux pays est représentée par une arête. On
obtient alors un graphe planaire. Francis Guthrie conjectura en 1852 que toutes
les cartes géographiques pouvaient être coloriées avec au plus 4 couleurs. Le
théorème des 4 couleurs fut démontré en 1976 par Appel et Haken : tout graphe
planaire peut être colorié avec au plus 4 couleurs.
A part le cas des graphes planaires, la coloration de graphes joue un rôle
important en algorithmique. Tout d’abord, c’est un problème utile. Imaginons
par exemple que l’on doive planifier un certain nombre de réunions, chacune
réquérant la présence d’un ensemble de participants déterminé, et que chaque
réunion dure, disons une demi-journée. Combien de demi-journées seront nécessaires ?
Cela peut se formaliser en termes de coloriage d’un graphe. Par ailleurs, c’est un
problème difficile : pour k ≥ 3, le problème de décider si un graphe est coloriable
avec k couleurs ou moins est un des 21 problèmes NP-complets de Karp. La dif-
ficulté du coloriage est illustrée par le problème du Sudoku, qui peut se voir
comme un coloriage de graphe où certains sommets du graphe ont une couleur
imposée et où il un unique coloriage optimal (à 9 couleurs).

41
42 CHAPITRE 5. NOMBRE CHROMATIQUE

Notamment, on ne connait pas d’algorithme efficace, général, pour colo-

rier un graphe avec le nombre minimal de couleurs possibles. Donnons tout de
même quelques idées naı̈ves. Tout d’abord, ce qu’on appelle l’algorithme glou-
ton consiste, étant donnée une liste ordonnée des sommets (cette donnée est loin
d’être innoncente) à parcourir la liste dans l’ordre, et à colorier chaque sommet
avec la première couleur disponible (les couleurs peuvent être identifiées à N)
cetteà dire la première couleur qui ne soit pas déjà empruntée par les voisins du
sommet courant. En général, on utilisera toujours au plus ∆(G) + 1 couleurs,
où ∆(G) est le degré maximal. On s’aperçoit vite qu’on a intérêt à colorier
d’abord les sommets de plus grands degrés, et à garder les sommets de petit
degré pour la fin : ils seront moins contraints. Notamment, si G a n sommets,
on peut procéder de la sorte : on pose vn un sommet de degré minimal δ(G),
puis on l’enlève de G, et on recommence en posant vn−1 un sommet de degré
minimal dans G \ {vn }. On obtient alors une liste v1 , . . . , vn avec la propriété
que pour tout i, vi est de degré minimal dans G|{v1 ,...,vi } . Pour colorier vi avec
l’algorithme glouton, il faudra au plus cette valeur plus un. Ainsi,

χ(G) ≤ 1 + max δ(H) .

H⊂G

Remarquons qu’il existe un unique sous-graphe de G de degré minimal supérieur

ou égal à k qui soit maximal pour l’inclusion. Ce sous-graphe (éventuellement
vide) est appelé le k-coeur du graphe. On peut également l’obtenir en enlevant
récursivement les sommets de degré strictement inférieur à k.
Donnons quelques définitions qui nous seront utiles par la suite. La maille
(ou circonférence) d’un graphe G, notée γ(G) est la longueur de son plus petit
cycle. Le nombre d’indépendance d’un graphe G, noté α(G) est la taille du
plus grand ensemble indépendant de sommets (on parle aussi de stable). Un
ensemble indépendant de sommets est un ensemble de sommets ne contenant
aucune arête intérieure. Le nombre clique de G, égal à l’ordre de la plus grande
clique contenue dans G, est noté ω(G). Ainsi, α(G) = ω(G).
Colorier un graphe avec k couleurs revient à partitionner l’ensemble de ses
sommets en k ensembles indépendants (ce qui revient à dire que G est k-parti).
On obtient ainsi la borne suivante pour un graphe G = (V, E) :

α(G)χ(G) ≥ |V | .

Remarquons que cette borne est assez bonne s’il existe un coloriage optimal tel
que le nombre de sommets de chaque couleur est à peu près le même.
Bien sûr, une clique d’ordre k n’est pas coloriable avec moins de k couleurs,
donc :
χ(G) ≥ ω(G) .
Néanmoins, cette borne est en général très mauvaise. Une première façon de le
voir est la construction suivante, dûe à Mycielski.

Théorème 5.1.1. Pour tout entier k il existe un graphe G sans triangle tel que
χ(G) > k.
5.1. INTRODUCTION 43

Démonstration: Disposant d’un graphe G sans triangle tel que χ(G) = k, on

construit un graphe G0 sans triangle tel que χ(G) = k + 1. On part d’une copie
de G avec ensemble de sommets v1 , . . . , vn , et on se donne n + 1 autres sommets
v10 , . . . , vn0 , w. Pour tout i, on place alors une arête entre vi0 et chaque voisin de vi .
Puis on place une arête entre w et vi0 pour tout i. On appelle G0 le graphe ainsi
construit. Il est facile de voir que si G est sans triangle, G0 est également sans
triangle. On suppose que χ(G) = k, et on considère un coloriage à k couleurs de
la copie de G contenue dans G0 . Il existe un ensemble de sommets w1 , . . . , wk tel
que pour tout i wi soit colorié avec la couleur i et les voisins de wi utilisent les
(k−1) couleurs restantes. Ainsi, wi0 (le sommet vj0 si wi = vj ) ne peut être colorié
qu’avec la même couleur que wi . Et ainsi w nécessite une nouvelle couleur. Ceci
montre que χ(G0 ) = k + 1.

Le Théorème 5.1.1 a d’abord été généralisé par Erdös en utilisant la méthode

probabiliste.
Théorème 5.1.2 (Erdös (1959)). Pour tous entiers k et l il existe un graphe
G tel que γ(G) > l et χ(G) > k.

Démonstration: On pose p = nθ−1 avec θ ∈ [0, 1]. On note X le nombre de

cycles de longueur inférieure ou égale à l dans G(n, p).
l
X (n)i
E(X) = pi ,
i=3
2i
l
X nθi
≤ = o(n) .
i=3
2i

Donc,
P(X ≥ n/2) = o(1) .
Par ailleurs,

n x
P(α(G(n, p)) ≥ x) ≤ (1 − p)(2) ,
x
≤ (xe−p(x−1)/2 )x .

Donc, si x = 3 logp n , P(α(G) ≥ x) = o(1). Donc pour n assez grand, il existe

un graphe G à n sommets ayant au plus n/2 cycles de longueur inférieure ou
égale à l et vérifiant α(G) ≤ x. En supprimant au plus un sommet par cycle de
longueur inférieure ou égale à l, on obtient un graphe G0 ayant au moins n/2
sommets et de maille γ(G0 ) > l. Par ailleurs,

n n nθ
χ(G0 ) ≥ ≥ = .
2α(G0 ) 2α(G) 3 log n
Donc pour n assez grand, on obtient χ(G0 ) ≥ k.
44 CHAPITRE 5. NOMBRE CHROMATIQUE

Remarquons que les graphes obtenus par Erdös sont bien plus petits que ceux
obtenus par Mycielski dans le cas où l = 3 : pour obtenir χ(G0 ) ≥ k, il suffit
d’un nombre de sommet polynomial en k : n ≥ k l (1 + ε), alors que le graphe de
Mycielski a un nombre de sommets exponentiel en k.
Dans la suite, nous commencerons par étudier le nombre d’indépendance
de G(n, p), puis nous l’utiliserons pour approcher χ(G(n, p)). On se restreindra
au cas où p est loin de 0 et de 1, ce qu’on appelle le cas dense. De plus, pour
simplifier les écritures, on prendra p = 1/2, mais tout ce qui suit peut se faire
de manière identique avec p fixé dans ]0, 1[.

5.2 Nombre d’indépendance et nombre clique

dans G(n, 1/2)
Notons Xk le nombre de cliques d’ordre k contenues dans G(n, 1/2). Exami-
nons le premier moment de Xk .

n −(k2)
f (k) := E(Xk ) = 2 .
k
√
Pour 1 k n, on a :
2
E(Xk ) ∼ 2k log2 n−k /2−log2 (k!)
.

De plus,
1 1
log2 (k!) = k log2 k − k + log2 (2πk) + o(1) .
log 2 2
On voit donc que E(Xk ) passe rapidement d’un ω(1) à un o(1) pour des valeurs
de k équivalentes à 2 log2 n. Par exemple, si k ≤ 2 log2 n−2 log2 log2 n− log2 2 −2,
f (k) tend vers l’infini. Mais si k ≥ 2 log2 n − 2 log2 log2 n, alors f (k) tend vers
0. Plus précisément, lorsque k ∼ 2 log2 n,
f (k + 1) n − k −k
= 2 = n−1+o(1) .
f (k) k+1
Notons k0 = k0 (n) tel que :

f (k0 − 1) > 1 ≥ f (k0 ) .

Alors, k0 ∼ 2 log2 n. f (k0 + 1) tend vers 0, donc a.p.s ω(G) ≤ k0 . On suppose

dans la suite que k ∼ 2 log2 n. Regardons la valeur du terme de covariance ∆
défini dans le chapitre 1.
k−1
n X k n − k 2(k2)−(2i )
∆ = p ,
k i=2 i k−i
k−1
X
2
= E(X) g(i) ,
i=2
5.3. NOMBRE CHROMATIQUE 45

où
k n−k

i
g(i) = i
n
k−i
2(2) .
k
On remarque que :
g(i + 1) 2i (k − i)2
= .
g(i) (i + 1)(n − 2k + i)
Lorsque i ≤ log2 n − K log log n pour K assez grand, g(i + 1)/g(i) tend vers 0, et
lorsque i ≥ log2 n + K log log n pour K assez grand, g(i + 1)/g(i) tend vers +∞.
Ainsi, dans ∆, les valeurs de g(i) pour i ≤ log2 n − K log log n sont majorées
par g(2), et les valeurs de g(i) pour i ≥ log2 n + K log log n sont majorées par
g(k − 1). Pour les valeurs intermédiaires, soit i ∈ [log2 n ± K log log n] et prenons
l petit devant log n mais grand devant log log n. Alors,

g(i0 + l) 2li+l(l−1)/2
≥ 1.
g(i0 ) (i + l)l nl

Ainsi, g(i0 ) est majoré par g(i0 ) + l qui lui-même est majoré par g(k − 1). De
plus,
k4
g(2) ∼ 2 ,
n
et
2kn
g(k − 1) ∼ k .
2 E(X)
Notamment, si on prend k = k0 − 2, on a E(X) = f (k0 − 2) 1 donc ∆ = o(1)
et P(X = 0) tend vers 0. Ainsi, ω(G) ≥ k0 − 2 donc ω(G) ∈ {k0 − 2, k0 − 1, k0 }
a.p.s. Remarquons qu’en faisant un peu plus attention, on peut montrer qu’il y
a concentration sur deux points seulement (cf. [AS08], section 10.2).

5.3 Nombre chromatique

Théorème 5.3.1. Asymptotiquement presque sûrement,
n
χ(G(n, 1/2)) ∼ .
2 log2 n

Démonstration: On note G un graphe de loi G(n, p) pour p = 1/2. La borne

inférieure est une conséquence simple de la section 5.2. En effet, α(G) est
équivalent (a.p.s) à 2 log2 n, puisque α(G) = ω(G). Ainsi,
n
χ(G) ≥ (1 + o(1)) .
2 log2 n

On aimerait maintenant “inverser” (approximativement) l’inégalité χ(G)α(G) ≥

n. On peut y arriver si on parvient à recouvrir presque tous les sommets (c’est
à dire tous sauf un o(n/ log n)) par des ensembles indépendants d’ordre 2 log2 n.
46 CHAPITRE 5. NOMBRE CHROMATIQUE

En effet, on pourra alors colorier chaque ensemble indépendant d’une couleur,

puis utiliser o(n/ log n) couleurs pour les sommets qui restent. L’idée est alors de
trouver une valeur m = o(n/ log n) telle que tout sous-ensemble de m sommets
contienne un ensemble indépendant de taille équivalente à 2 log2 n. Pour mener à
bien ceci, il faut qu’il y ait beaucoup d’ensembles indépendants d’ordre 2 log2 n.
La première chose est donc de choisir un k équivalent à 2 log2 n mais tel que le
nombre moyen d’ensembles indépendants soit grand. Prenons k = k0 (n) − 4. On
a alors :
f (k) > n3+o(1) ,
et le second moment donne :
f (k)2 k 4
∆∼ ,
n2
Par conséquent l’inégalité de Janson (cf. Chapitre B) donne :
n2
P(X = 0) ≤ e− 2k4 .

On choisit maintenant m = n/(log n)2 et k = k0 (m) − 4. Alors, pour tout

sous-ensemble de sommets S de cardinal m,
m2
P(α(G|S ) < k) ≤ e− 2k4 .

Donc,
n − m24
P(∃S t.q. |S| = m et α(G|S ) < k) ≤ e 2k = o(1) .
m
Donc, avec proba tendant vers 1, tout sous-ensemble de m sommets contient un
ensemble indépendant d’ordre k ∼ 2 log2 n. On peut alors successivement tirer
un ensemble indépendant d’ordre k, le colorier, le retirer du graphe, retirer un
ensemble indépendant d’ordre k, le colorier etc. jusqu’à ce qu’il ne reste qu’un
ensemble de sommets d’ordre inférieur à m, auquel on donne au plus m couleurs.
On a alors :
n n
χ(G) ≤ + m ≤ (1 + o(1)) .
k 2 log2 n

5.4. EXERCICES 47

5.4 Exercices
Exercice 5.1 Soit G un graphe à m arêtes. Montrer que :
r
1 1
χ(G) ≤ + 2m + .
2 4

Exercice 5.2 Soit G un graphe connexe, et v un sommet tel que G \ {v} ne

soit plus connexe, mais soit la réunion de r composantes connexes C1 , . . . , Cr .
On note Bi le graphe induit par Ci ∪ v. Calculer le nombre chromatique de G
en fonction de ceux des Bi .
Exercice 5.3 Trouver un graphe et un ordre sur ses sommets tels que l’algo-
rithme glouton ne soit pas optimal.
Exercice 5.4 Montrer que pour tout k, il existe ε > 0 tel que pour tout n
assez grand, il existe des graphes G à n sommets tels que χ(G) > k et pourtant
χ(G|S ) ≤ 3 pour tout ensemble de sommets S de taille au plus εn.
Exercice 5.5 Montrer que tout graphe planaire peut être colorié avec au plus
5 couleurs.
48 CHAPITRE 5. NOMBRE CHROMATIQUE
Annexe A

Compléments sur la
transition de phase
d’Erdös-Rényi

Les cas à peine sous-critique et à peine sur-critique n’ont pas été vus en
cours, faute de temps. Voici des preuves.

A.1 Cas à peine sous-critique

Nous allons d’abord comparer les 3 processus (cf. Proposition A.1.1), et enfin
appliquer ces approximations pour obtenir une preuve du Théorème 4.0.1 dans
les cas sous-critique.

A.1.1 Comparaison des trois processus

Le but de cette section est de compléter la comparaison des trois processus
initiée au Lemme 4.4.1. Tout d’abord, on peut approcher également par en-
dessous le processus de branchement de graphe par le processus de branchement
binomial.

Proposition A.1.1. Pour tout t ≥ 1,

bin gr bin
P(Tn−t,p ≥ t) ≤ P(Tn,p ≥ t) = P(|C(v)| ≥ t) ≤ P(Tn−1,p ≥ t) .

Démonstration: La majoration a été vue au Lemme 4.4.1. On conserve les nota-

tions du processus de graphe (4.9) en ajoutant des exposants gr. La proposition
est une conséquence du fait que :
gr
Tn,p = inf{t ≥ 0, t.q. Ntgr = n − t} .

49
50 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION

On peut alors coupler les processus de la manière suivante. On définit un pro-

(2) (2)
cessus 2 par N0 = n − t, S0 = 1

(2)
 Ls ∼ B(N, p) conditionnellement à Ns−1 = N

(2) (2) (2)
∀s ≥ 1 Ss = Ss−1 + Ls − 1
 (2)
 (2)
Ns = Ns−1
gr
De plus, pour tout s ≥ 1, tant que Ns−1 ≥ n − t, on peut coupler à l’étape s les
(2)
trois variables aléatoires Ls et Ls de sorte que :

Ls ≤ L(2)
s .

gr (2)
Ainsi, tant que s ≤ Tn,p , on a toujours Ss ≤ Ss , ce qui implique que T (1) ≤
gr (1)
Tn,p , où T (1) = inf{s ≥ 0 t.q. Ss = 0}.
Le processus de branchement de Poisson est plus agréable à manipuler que le
processus de branchement binomial. On a déjà vu au Lemme 4.4.1 une compa-
raison lorsque c < 3/2.
Pour la minoration, ou pour c > 3/2, on doit utiliser des résultats plus
précis. On suppose que p = c/n, avec c = Θ(1) et c = 1 + ε, avec ε de signe
quelconque.

Lemme A.1.2 (Comparaison). Soient t et k tels que k ≥ 1 et 0 ≤ t n. On

pose
bin
P(Tn−t,p = k)
Qk = po .
P(Tc = k)
Alors, si t = 0,
sup Qk ≤ 1 + o(1) .
k
3 3
Sinon, si k n et kt = o(n ), alors :

kt
log Qk = (2nε − t) + o(1) .
2n2

Démonstration: On omet l’indice k dans Qk . D’après le Théorème 4.1.2,

P(Skbin,n−t,p = 0)
Q= .
P(Skpo,c = 0)

Ainsi,
(n−t)k

k−1 pk−1 (1 − p)(n−t)k−k+1
Q = k−1 ,
e−kc (kc)
(k−1)!

(nk − tk)!ekc (1 − nc )nk−tk−k+1

= .
(nk − tk − k + 1)!(nk)k−1
A.1. CAS À PEINE SOUS-CRITIQUE 51

Grâce à la formule de Stirling, en utilisant que t = o(n),

log Q = (k(c − 1) + 1) + k(n − t) log[k(n − t)]

h c i
+(k(n − t − 1) + 1) log(1 − ) − log(k(n − t − 1) + 1)
n
−(k − 1) log(nk) + o(1) ,
t
= kε + 1 + (nk − tk) log(1 − )
n
c t 1 1
+(k(n − t − 1) + 1) log(1 − ) − log(1 − − + ) + o(1) ,
n n n nk
t
= kε + 1 + k log(1 − )
n
1 − nc

t
+k(n − t − 1) log(1 − ) + log + o(1) .
n 1 − nt − n1 + nk
1

Or,
(1 − nt )(1 − nc ) (−ε − k1 + tc
n)
t 1 1 =1+ n−t−1
.
1 − n − n + nk
Notamment, si t = 0, en utilisant log(1 − x) ≤ x,
1
log Q ≤ kε + 1 + k(−ε − ) + o(1) = o(1) .
k
Sinon, en général on remarque que :
(1 − nt )(1 − nc ) −1
1 = O(n ).
1 − nt − n1 + nk
Donc, si k est petit devant n,
2
(−ε − k1 + tc

n) 1
= o( ) .
n−t−1 nk
Donc :

t 1 tc
log Q = 1 + k ε + log(1 − ) − ε − + + o(1) ,
n k n

tε t t
= k + log(1 − ) + + o(1) ,
n n n
kt
= (2nε − t) + o(1) ,
2n2
en utilisant à la dernière ligne que kt3 = o(n3 ).
On commence par compléter la majoration pour c grand :
Lemme A.1.3 (Majoration (bis)). Pour tout u ≥ 1,
bin
P(+∞ > Tn,p ≥ u) ≤ P(+∞ > Tcpo ≥ u)(1 + o(1)) .
52 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION

Démonstration: On prend t = 0 dans le Lemme A.1.2 :

X1
bin
P(+∞ > Tn,p ≥ u) = P[Skbin,n−1,p = 0] ,
k
k≥u
X1
≤ (1 + o(1)) P[Skpo,c = 0] ,
k
k≥u
= P(+∞ > Tcpo ≥ u)(1 + o(1)) .

Puis, on obtient les minorations utiles.

Lemme A.1.4 (Minoration). Soient u, u2 et t petis devant n tels que u2 ≥ u

et u2 t3 n3 . Alors,
u2 t
bin
P(+∞ > Tn−t,p ≥ u) ≥ [P(+∞ > Tcpo ≥ u)−P(+∞ > Tcpo ≥ u2 )]e− 2n2 (t−2nε)+ (1+o(1)) .
ut
Notamment, si t n, u n, ut3 n3 , uJ(c) tend vers l’infini et 2n2 (t −
2nε)+ 1,
bin
P(+∞ > Tn−t,p ≥ u) ≥ P(+∞ > Tcpo ≥ u)(1 + o(1)) .

Démonstration: On écrit :
bin
P(+∞ > Tn−t,p ≥ u)
u
X1 2

≥ P[Skbin,n−1,p = 0] ,
k
k=u
u2 t X1
≥ (1 + o(1))e− 2n2 (t−2nε)+ P[Skpo,c = 0] ,
k
k≥u
u2 t
& [P(+∞ > Tcpo ≥ u) − P(+∞ > Tcpo ≥ u2 )] e− 2n2 (t−2nε)+ .

Pour le deuxième point, on choisit u2 tel que u u2 n, u2 t3 n3 et

u2 t
2n2 (t − 2nε)+ 1 puis on utilise le Lemme 4.5.1 qui assure que :

P(+∞ > Tcpo ≥ u2 ) P(+∞ > Tcpo ≥ u) .

Enfin, on obtient l’analogue du Lemme 4.3.1 pour le branchement binomial,
lorsque ε tend vers 0+ .

Lemme A.1.5 (Probabilité de survie). On suppose que ε > 0 et t = o(εn).

Alors, quand ε tend vers 0+ ,
bin
P(Tn−t,p = +∞) = 2ε + o(ε) .
A.1. CAS À PEINE SOUS-CRITIQUE 53

Démonstration: On note y la probabilité de survie. D’après l’équation (4.3), on

sait qu’elle est définie comme la plus petite solution de :
yc
y > 0 et 1 − y = (1 − )n−t .
n
On remarque que :
2
h yc i yc y
log (1 − )n−t = (n − t) − + o ,
n n n
= −yc + o(y 2 ) + o(yε) .
Donc, en utilisant y 6= 0 pour diviser par y :
y2
1−y = 1 − yc + o(y 2 ) + o(yε) + + o(y 2 ) ,
2
y2
+ o(y 2 ) = yε + o(yε) ,
2
y + o(y) = 2ε + o(ε) .
D’où le résultat.

A.1.2 Phase à peine sous-critique

Le fait que les composantes connexes de G(n, p) soient simples dans les phases
sous-critique et à peine sous-critique a été vu dans l’exercice 0.4.
Il nous faut maintenant contrôler la taille des plus grandes composantes
connexes, en utilisant le travail fait jusqu’ici, qui concerne la taille d’une com-
posante connexe particulière. Un argument assez général basé sur une méthode
du premier moment est contenu dans le lemme suivant.
Lemme A.1.6. On note :
m = E(|C(v)|) .
(i) Soit u = un tel que
n
P(|C(v)| ≥ u) = o(1) . (A.1)
u
Alors,
P(L(1) ≥ u) = o(1) .
(ii) Soient u0 = u0n , β = βn et T = Tn telles que
β = ω(1) ,
T βm < n ,
et
T Pn−T βm,p (|C(v)| ≥ u0 ) 1 ,
où Pl,p désigne la proba selon G(l, p). Alors,
P(L(1) ≤ u0 ) = o(1) .
54 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION

(iii) On suppose de plus que

Pn−T βm,p (|C(v)| ≥ u0n ) = Θ(P(|C(v)| ≥ u0n )) .
Alors, pour tout r fixé,
P(L(r) ≤ u0n ) = o(1) .

Démonstration: Notons X le nombre de sommets qui appartiennent à une

composante connexe d’ordre au moins u. On a :
E(X) ≤ nP(|C(v)| ≥ u) .
De plus, s’il existe une composante connexe d’ordre au moins u, alors X est
supérieure à u. Donc,
P(L(1) ≥ u) ≤ P(X ≥ u) ,
E(X)
≤ ,
u
nP(|C(v)| ≥ u)
≤ ,
u
ce qui montre le premier point.
Pour la minoration, on explore les composantes connexes du graphe de la
façon suivante. Tous les sommets du graphe sont ordonnés et on va explorer les
T premières composantes connexes selon cet ordre (l’ordre d’une composante
connexe étant déterminé par le plus petit sommet lui appartenant).
On examine C(v1 ), avec v1 = 1, qui est de taille supérieure à u0 avec pro-
babilité q = P(|C(v)| ≥ u0 ). puis on examine C(v2 ) où v2 est le premier som-
met n’appartenant pas à C(v1 ). Conditionnellement à |C(v1 )| = k, C(v2 ) vit
dans G(n − k, p). Conditionnellement à |C(v1 )| < u0 , la taille de cette seconde
composante connexe est donc minorée par la taille de C(v), avec v fixé, dans
G(n − u0 , p). On continue comme ça jusqu’à la T -ième composante connexe.
Remarquons que :
T
X
P( |C(vi )| ≥ βT m) ≤ β −1 = o(1) .
i=1

La probabilité qu’aucune de ces composantes connexes ne soit de taille supérieure

à u0 est donc inférieure à :
T
Y 0
Pn−βT m,p (|C(vi )| < u0 ) ≤ e−T Pn−βT m,p (|C(v)|≥u ) + o(1) .
i=1

Ceci montre le deuxième point.

Pour le troisième point, notons Y le nombre de composantes connexes, parmi
les T premières, qui sont de taille supérieure ou égale à u0 . On note :
q = Pn−T βm,p (|C(v)| ≥ u0 ) ,
A.1. CAS À PEINE SOUS-CRITIQUE 55

et
q̃ = Pn (|C(v)| ≥ u0 ) .

Quitte à augmenter u0 , on peut supposer que q tend vers 0. Ainsi,

T
X
P(Y ≤ r) = P(Y ≤ r et |C(vi )| < βT m) + o(1) ,
i=1
i
1|C(vi )|≥u0 = bi et
X X
≤ P(∀i ≤ T, |C(vi )| < βT m) + o(1) ,
b∈{0,1}T j=1
|b|≤r

X T
Y
≤ Pn−βT m,p (|C(vi )| < u0 )1−bi Pn,p (|C(vi )| ≥ u0 )bi + o(1) ,
b∈{0,1} T i=1
|b|≤r
X
≤ (1 − q)T −|b| (q̃)|b| + o(1) ,
b∈{0,1}T
|b|≤r

≤ (r + 1)(T q̃)r e−(T −r)q (1 + o(1)) + o(1) ,

= o(1) ,

puisque par hypothèse, q et q̃ sont du même ordre et T q tend vers l’infini.

La taille d’une composante connexe fixée est facilement majorée par la Propo-
sition A.1.1 et les Lemmes 4.4.1 et 4.5.1. On a, pour tout sommet v fixé :
n n
P(|C(v)| > u) ≤ P(Tcpo > u) ,
u u
ne−uJ(c)
≤ √ .
u5/2 cJ(c) 2π

On pose λ = n1/3 J 1/2 (c), qui permet d’englober les cas sous-critique et à peine
sous-critique. En effet, dans le cas sous-critique, lorsque c = 1 − ε avec ε tend
vers 0+ mais grand devant n−1/3 , on a λ tend vers l’infini et λ ∼ n1/3 ε. En
choisissant
log(nJ 3/2 (c)) 3 log(λ)
u= = ,
J(c) J(c)
on obtient :
n
P(|C(v)| > u) = Θ(log−5/2 λ) = o(1) .
u
Pour la minoration, on pose

log(nJ 3/2 (c))

u0 = (1 − δ) ,
J(c)
56 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION

avec δ ∈]0, 1[ fixé. On remarque que d’après le Lemme 4.5.1 :

0
n ne−u J(c)
P(Tcpo > u0 ) ≥ √ (1 + o(1)) ,
u0 (u0 )5/2 cJ(c) 2π

= Ω λ3δ /(log λ)5/2 .

Si on trouve T et β tels que :

Pn−βT m,p (|C(v)| > u0 ) ≥ P(Tcpo > u0 )(1 + o(1)) , (A.2)

et
T u0 λ3δ
1, (A.3)
n(log λ)5/2

on aura fini. Remarquons que |C(v)| est inférieure stochastiquement à T po ,

donc :
1
m = E(|C(v)|) ≤ E(T po ) = = ε−1 .
1−c
Pour appliquer le Lemme A.1.4, et obtenir (A.2) il suffit d’avoir (en prenant β
tendant vers l’infini assez lentement) :

u0 (T m)2 = o(n2 ), u0 (T m)ε = o(n) .

Donc, il suffit d’avoir :

T = o(nε/(u0 )1/2 ), T = o(n/u0 ) .

Or,
p
nε/(u0 )1/2 = Θ(λ2 n1/3 / log λ), n/(mεu0 ) = Θ(λ2 n1/3 / log λ) .

Et la condition (A.3) est équivalente à :

T n1/3 (log λ)3/2 λ2−3δ .

Il suffit donc de prendre par exemple T = n1/3 λ2 /(log λ)3/2 . On peut donc
appliquer le Lemme A.1.6, et on obtient que :

P(L(1) ≥ 3 log λ/J(c)) = o(1) ,

et pour tout r fixé (et tout δ 0 ∈]0, 1[),

P(L(r) ≤ 3(1 − δ) log λ/J(c)) = o(1) .

A.2. CAS À PEINE SUR-CRITIQUE 57

A.2 Cas à peine sur-critique

A.2.1 Existence de la composante géante
Nous allons montrer que lorsque p = c/n avec c = 1+ε, ε = λn−1/3 et λ 1,
il existe une plus grande composante géante de taille équivalente à ny(c), et il
n’existe pas de composante de taille supérieure à ny(c)(1 + δ). Fixons δ > 0 et
notons t1 = ny(c)δ et t2 = ny(c)(1 − δ). Le point crucial est d’arriver à montrer
que :
P(∃t ∈ [t1 , t2 ] s.t. St ≤ 0) = o(1) ,
mais ici, on ne peut plus utiliser une borne d’union comme dans le cas sur-
critique : on perdrait trop. Il faut comprendre que la borne d’union est en
général très mauvaise. En effet, si Sk = 0 pour un k dans [ny(c)δ, ny(c)(1 − δ)],
alors cela va influer, négativement, sur la valeur de Sny(c)(1−δ) .
Lemme A.2.1. Pour tout λ ≤ 0,
P(∃t ∈ [t1 , t2 ] s.t. St ≤ 0) ≤ e−λε(t2 −t1 ) E(eλSt2 ) .

Démonstration: Pour k ∈ [t1 , t2 ], notons Bk l’évènement {Xi > 0∀i ∈ [t1 , k −

1], et Xk = 0}. Notons également B l’évènement {∃t ∈ [t1 , t2 ] s.t. St ≤ 0}.
Alors, B est l’union disjointe des évènements Bk , pour k ∈ [t1 , t2 ]. Pour com-
prendre l’influence de Bk sur la valeur de St2 , écrivons :
E(eλSt2 1Bk |St1 , . . . , Sk ) = 1Bk eλ(Sk ) E(eλ(St2 −Sk ) |St1 , . . . , Sk ) ,
= 1Bk E(eλ(St2 −Sk ) |Sk ) ,
or d’après la Proposition 4.1.4, pour λ ≤ 0 :
E(eλ(St2 −Sk ) |St1 , . . . , Sk ) ≥ eλE(St2 −Sk |Sk ) ,
t2 −k
= eλ[(n−Sk −k)(1−(1−p) )−t2 +k]
,
λ[(n−Sk )p(t2 −k))−t2 +k]
≥ e ,
= eλ(t2 −k)(c(1−Sk /n)−1) ,

Donc :
E(eλSt2 1Bk |St1 , . . . , Sk ) ≥ 1Bk eλ(t2 −k)ε ,
D’où :
t2 t2
eλSt2 1Bk ) = e−λ(t2 −t1 )ε E(eλSt2 ) .
X X
P(B) = P(Bk ) ≤ e−λ(t2 −t1 )ε E(
k=t1 k=t1

Notons B l’évènement {∃t ∈ [t1 , t2 ] s.t. St ≤ 0}. En optimisant en λ ≤ 0 le
Lemme A.2.1, et en notant que ε(t2 −t1 ) ∼ ny(c)ε(1−2δ) ≤ E(St2 )ny(c)ε(1−δ),
−Λ∗
St (ε(t2 −t1 ))
P(A) ≤ e 2 .
58 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION

Or, d’après la Proposition 4.1.4, St2 suit une loi B(n − 1, 1 − (1 − p)t2 . Comme
t2 p ∼ 2ε(1 − δ), Var(St2 ) ∼ 2nε(1 − δ) et E(St2 ) ∼ (1 − δ)2nε2 . En utilisant
l’inégalité de Bernstein (on pourrait aussi utiliser la transformée de Cramér de
la binomiale), on obtient :

−Λ∗
St (ε(t2 −t1 ))
P(A) ≤ e 2 ,
(E(St −ε(t2 −t1 ))2
2
− 2(Var(S )+(E(S
t2 −ε(t2 −t1 ))/3))
≤ e t2
,
2
( )
2nδε2

= e− 4nε(1−δ) (1+o(1)) ,
3
= e−λ (1+o(1))/(1−δ)
,
= o(1) .

Ainsi, a.p.s. on est en train d’explorer une composante de taille supérieure à t2 −

t1 entre les instants t1 et t2 . Nous allons montrer maintenant que l’exploration de
cette composante s’arrête nécessairement avant l’instant ny(c)(1 + δ). D’après
(4.10), E(St ) est négative lorsque t = ny(c)(1 + δ), et plus précisément, par
concavité :
E(St ) ≤ nδy(c)φ0 (y(c)) + O(1) ∼ −2nδε2 .
De plus, Var(St ) ∼ ntp ∼ 2nε(1 + δ). Donc en utilisant Bernstein,

P(St ≥ 0) = P(St − E(St ) ≥ −E(St )) ,

(E(St )2
≤ e− 2(Var(St )+E(St /3)) ,
2
(2nδε2 )
− 4nε(1+δ) (1+o(1))
= e ,
3
= e−λ (1+o(1))
.

On obtient donc qu’il existe une composante connexe de taille supérieure à

ny(c)(1 − 2δ), explorée entièrement entre les instants 0 et ny(c)(1 + δ).
Pour prouver l’unicité de cette composante, on ne peut plus utiliser la borne
d’union, mais on peut la voir comme une conséquence de la dualité.

A.2.2 Dualité, unicité et complexité

Soit G ∼ G(n, p), et soit C la réunion de toutes les composantes connexes
de taille comprise entre ny(c)(1 − 2δ) et ny(c)(1 + δ). On considère la loi de
G \ C. Comme dans le cas sur-critique, la loi de ce graphe est celle d’un G(n, k)
avec k de l’ordre de ny(c)(1 − 2δ) au moins (et on sait que n − k est d’ordre n,
l’ordre du nombre de sommets isolés), conditionné à ne pas avoir de composante
connexe de taille entre ny(c)(1 − 2δ) et ny(c)(1 + δ). Pour un entier k supérieur
à ny(c)(1 − 2δ) ∼ 2nε(1 − 2δ),

c 1 k 1 1
p= = c(1− ) . (1+ε)(1−2ε(1−2δ)) = (1−ε(1−4δ)+o(ε)) ,
n n−k n n−k n−k
A.2. CAS À PEINE SUR-CRITIQUE 59

et si δ est assez petit, on se retrouve ainsi dans la phase à peine sous-critique.

On verra alors (cf. section A.1) qu’avec probabilité tendant vers 1 les r plus
grandes composantes, pour r fixé, sont d’ordre ε−2 ln λ. Notamment, il n’y a
pas de composante de taille comprise entre ny(c)(1 − 2δ) et ny(c)(1 + δ), donc
le conditionnement ci-dessus ne change pas les propriétés de graphes a.p.s. On
en déduit donc qu’il n’y a pas non plus, dans le graphe initial, de composante
de taille supérieure à ny(c)(1 + δ). On peut alors faire le même argument que
dans le cas sur-critique pour l’unicité de la composante géante et sa complexité.
60 ANNEXE A. COMPLÉMENTS SUR LA TRANSITION
Annexe B

Inégalités de corrélation

Ce chapitre est un deuxième interlude technique à propos des inégalités de

corrélation. Il nous servira pour l’étude du nombre chromatique (cf. chapitre 5).

B.1 Inégalité de Harris

Si les indicatrices qui composent XG , la variable aléatoire qui compte le
nombre de copies d’un graphe G dans G(n, p), sont corrélées, il semble qu’il y
ait un sens dans cette corrélation : elles sont positivement corrélées, car lorsque
l’une d’elles vaut 1, cela a tendance a aider les autres à valoir 1. Cet argument
semble indiquer que :
Y
P(XG ≥ 1) ≥ P(S ⊂ G(n, p)) .
S∈O(G)

Nous allons voir que c’est effectivement le cas grâce à l’inégalité de Harris. Celle-
ci est très simple à montrer dans le cadre d’un espace produit (elle se généralise
à des cadres plus généraux).

Théorème B.1.1. Soient f et g Q deux fonctions mesurables réelles définies sur

n
un espace de probabilité produit ( i=1 Xi , ⊗ni=1 µi ) où chaque Xi est totalement
ordonné. Si f etQg sont des fonctions croissantes (pour l’ordre coordonnée par
n
coordonnée sur i=1 Xi ), et X est un vecteur aléatoire de loi µ, alors :

E(f (X)g(X)) ≥ E(f (X))E(g(X)) .

Démonstration: On montre le résultat par récurrence sur n. Si n = 1, c’est

ce qu’on appelle l’inégalité d’association positive de Tchebychev (ou “l’autre
inégalité de Tchebychev”). On considère X et X 0 deux variables aléatoires
indépendantes de loi µ1 . Comme X1 est totalement ordonné et que f et g sont
croissantes,
(f (X) − f (X 0 ))(g(X) − g(X 0 )) ≥ 0 .

61
62 ANNEXE B. INÉGALITÉS DE CORRÉLATION

En prenant l’espérance, on obtient le résultat pour n = 1. Si n ≥ 2,

E(f (X)g(X)) = E(E(f (X)g(X)|X1 , . . . , Xn−1 )) .
L’inégalité pour n = 1 montre que :
E(f (X)g(X)|X1 , . . . , Xn−1 ) = E(f (X)|X1 , . . . , Xn−1 )E(g(X)|X1 , . . . , Xn−1 ) ,
Enfin, comme E(f (X)|X1 , . . . , Xn−1 ) et E(g(X)|X1 , . . . , Xn−1 ) sont des fonc-
tions croissantes de (X1 , . . . , Xn−1 ), l’hypothèse de récurrence au rang (n − 1)
montre que :
E(E(f (X)|X1 , . . . , Xn−1 )E(g(X)|X1 , . . . , Xn−1 ))
≥ E(E(f (X)|X1 , . . . , Xn−1 ))E(E(g(X)|X1 , . . . , Xn−1 )) ,
= E(f (X))E(g(X)) .
Cela donne le résultat au rang n.
Cette inégalité a une forme plus générale, satisfaite par des mesures qui ne sont
pas nécessairement de forme produit, connue sous le nom d’inégalité FKG.

B.2 Inégalité de Janson

On considère le cadre de l’hypercube {0, 1}n , muni d’une mesure produit
µ = ⊗ni=1 µi . On note G un vecteur aléatoire de loi µ qu’on identifie à un sous-
ensemble aléatoire de [n] par la correspondance G 7→ {i ∈ [n] t.q. Gi = 1}. Soit
Γ une collection de sous-ensembles de [n]. Pour α ∈ Γ, on note :
Iα = 1α⊂G pα = E(Iα ) .
On note α ∼ β si α 6= β et α ∩ β 6= ∅. On définit :
X
W = Iα ,
α∈Γ

λ = E(W ) ,
et X
∆= E(Iα Iβ ) .
α∼β

Le résultat suivant permet d’obtenir une majoration de P(W = 0) qui est no-
tamment bien meilleure que l’approximation poissonienne du Chapitre 1 lorsque
λ, l’espérance de W , est grande.
Théorème B.2.1 (Inégalité de Janson). Pour tout ε ∈ [0, 1],
λ
− (ε+(1−ε) log(1−ε))
1+ ∆
P(W ≤ (1 − ε)λ) ≤ e λ .
Notamment,
λ
−
1+ ∆
P(W = 0) ≤ e λ .
B.2. INÉGALITÉ DE JANSON 63

Démonstration: Pour t ≥ 0, on note ψ(t) = E[e−tW ]. Alors,

X
ψ 0 (t) = −E[W e−tW ] = − E(Iα e−tW ) .
α

On note, pour α ∈ Γ, Wα0 = Iα + et Wα00 = W − Wα0 . Ainsi, Wα00 est

P
β∼α Iβ
indépendante de Iα . Maintenant,
0 00
E(Iα e−tW ) = pα E(e−tWα e−tWα |Iα = 1) .

Le fait de conditionner par Iα = 1 revient à fixer à 1 les valeurs de Gi pour

i ∈ α. Ainsi, l’inégalité de Harris implique que :
0 00
E(Iα e−tW ) ≥ pα E(e−tWα |Iα = 1)E(e−tWα |Iα = 1) ,
0 00
= pα E(e−tWα |Iα = 1)E(e−tWα ) ,
0
≥ pα E(e−tWα |Iα = 1)E(e−tW ) .

Ainsi, en utilisant Jensen,

X 0
ψ 0 (t) ≤ −ψ(t) pα E(e−tWα |Iα = 1) ,
α
X 0
≤ −ψ(t) pα e−E(tWα |Iα =1) ,
α
X pα 0
= −λψ(t) e−E(tWα |Iα =1) ,
α
λ
pα
E(tWα0 |Iα =1)
P
≤ −λψ(t)e− α λ ,
t
E(Wα0 Iα )
P
−λ
= −λψ(t)e α ,
−(1+ ∆
λ )t
= −λψ(t)e .

En intégrant cette inéquation différentielle, on trouve :

λ ∆
log ψ(t) ≤ − ∆
(1 − e(1+ λ )t ) .
1+ λ

On passe alors à la transformée de Legendre.

64 ANNEXE B. INÉGALITÉS DE CORRÉLATION
Bibliographie

[AS08] Noga Alon and Joel H. Spencer. The probabilistic method. Wiley-
Interscience Series in Discrete Mathematics and Optimization. John
Wiley & Sons Inc., Hoboken, NJ, third edition, 2008. With an appendix
on the life and work of Paul Erdős.
[BHJ92] A. D. Barbour, Lars Holst, and Svante Janson. Poisson approximation,
volume 2 of Oxford Studies in Probability. The Clarendon Press Oxford
University Press, New York, 1992. Oxford Science Publications.

[Bol01] Béla Bollobás. Random graphs, volume 73 of Cambridge Studies in Ad-

vanced Mathematics. Cambridge University Press, Cambridge, second
edition, 2001.
[Dur10] Rick Durrett. Random graph dynamics. Cambridge Series in Sta-
tistical and Probabilistic Mathematics. Cambridge University Press,
Cambridge, 2010.
[JLR00] Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random graphs.
Wiley-Interscience Series in Discrete Mathematics and Optimization.
Wiley-Interscience, New York, 2000.

65
66 BIBLIOGRAPHIE
Table des matières

Introduction i
0.1 Présentation du personnage principal : G(n, p) . . . . . . . . . . . i
0.2 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
0.3 Phénomènes de seuil . . . . . . . . . . . . . . . . . . . . . . . . . iii
0.4 Notions élémentaires de théorie des graphes . . . . . . . . . . . . iv
0.5 Les méthodes du premier et du second moment . . . . . . . . . . v
0.6 Remarques sur les notations . . . . . . . . . . . . . . . . . . . . . v
0.7 Références principales . . . . . . . . . . . . . . . . . . . . . . . . v
0.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi

1 Petits sous-graphes 1
1.1 Seuil pour les petits sous-graphes . . . . . . . . . . . . . . . . . . 1
1.2 A l’intérieur du seuil . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Convergence en loi et distance en variation totale . . . . . 3
1.2.2 Approximation poissonienne par couplage . . . . . . . . . 6
1.2.3 Méthode des moments . . . . . . . . . . . . . . . . . . . . 8
1.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Connexité 11
2.1 Disparition des sommets isolés . . . . . . . . . . . . . . . . . . . 11
2.2 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Inégalités de concentration 15
3.1 Méthode de Cramér-Chernoff . . . . . . . . . . . . . . . . . . . . 16
3.2 Inégalités de Hoeffding, Bennett et Bernstein . . . . . . . . . . . 17
3.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Transition de phase d’Erdös-Rényi 21

4.1 Processus de Galton-Watson . . . . . . . . . . . . . . . . . . . . . 22
4.1.1 Construction par génération . . . . . . . . . . . . . . . . . 22
4.1.2 Codage par une marche aléatoire . . . . . . . . . . . . . . 25
4.1.3 Processus de branchement du graphe . . . . . . . . . . . . 27
4.2 Cas sous- et sur-critique . . . . . . . . . . . . . . . . . . . . . . . 29

67
68 TABLE DES MATIÈRES

4.2.1 Cas sous-critique . . . . . . . . . . . . . . . . . . . . . . . 29

4.2.2 Cas sur-critique . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Explication de la paramétrisation . . . . . . . . . . . . . . . . . . 34
4.4 Cas critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.1 Borne supérieure sur L1 . . . . . . . . . . . . . . . . . . . 35
4.4.2 Le cas des arbres . . . . . . . . . . . . . . . . . . . . . . . 36
4.5 Analyse du processus de branchement de Poisson . . . . . . . . . 38
4.6 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Nombre chromatique 41
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 Nombre d’indépendance et nombre clique dans G(n, 1/2) . . . . . 44
5.3 Nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

A Compléments sur la transition 49

A.1 Cas à peine sous-critique . . . . . . . . . . . . . . . . . . . . . . . 49
A.1.1 Comparaison des trois processus . . . . . . . . . . . . . . 49
A.1.2 Phase à peine sous-critique . . . . . . . . . . . . . . . . . 53
A.2 Cas à peine sur-critique . . . . . . . . . . . . . . . . . . . . . . . 57
A.2.1 Existence de la composante géante . . . . . . . . . . . . . 57
A.2.2 Dualité, unicité et complexité . . . . . . . . . . . . . . . . 58

B Inégalités de corrélation 61
B.1 Inégalité de Harris . . . . . . . . . . . . . . . . . . . . . . . . . . 61
B.2 Inégalité de Janson . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Vous aimerez peut-être aussi

Optimisation1 Chap1
Pas encore d'évaluation
Optimisation1 Chap1
30 pages
Analyse Statistique de Graphes
Pas encore d'évaluation
Analyse Statistique de Graphes
54 pages
Introduction à la théorie des graphes
100% (1)
Introduction à la théorie des graphes
41 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
53 pages
Chapitres Choisis de Théorie Des Probabilités B: - Yvan Velenik
Pas encore d'évaluation
Chapitres Choisis de Théorie Des Probabilités B: - Yvan Velenik
84 pages
Lois Discrètes et Continues en Probabilités
Pas encore d'évaluation
Lois Discrètes et Continues en Probabilités
6 pages
Graphe
Pas encore d'évaluation
Graphe
8 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
47 pages
Introduction à la théorie des graphes
100% (3)
Introduction à la théorie des graphes
47 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
58 pages
Partie 2 Theorie Graphe
Pas encore d'évaluation
Partie 2 Theorie Graphe
42 pages
Bon Melange
Pas encore d'évaluation
Bon Melange
8 pages
All Document Reader 1750176191729
Pas encore d'évaluation
All Document Reader 1750176191729
38 pages
Magnifique THG
Pas encore d'évaluation
Magnifique THG
198 pages
Sujet 00 Math AP
Pas encore d'évaluation
Sujet 00 Math AP
7 pages
Chapitre 1 Version 2018
Pas encore d'évaluation
Chapitre 1 Version 2018
10 pages
Introduction aux Graphes et Coloration
Pas encore d'évaluation
Introduction aux Graphes et Coloration
57 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
17 pages
Organisation d'équipes en recherche opérationnelle
Pas encore d'évaluation
Organisation d'équipes en recherche opérationnelle
10 pages
Probabilités pour Étudiants Avancés
Pas encore d'évaluation
Probabilités pour Étudiants Avancés
101 pages
Cours 2021
Pas encore d'évaluation
Cours 2021
57 pages
Graphe
Pas encore d'évaluation
Graphe
76 pages
Introduction À La Théorie Des Graphes by Zekrifa Djabeur Mohamed Seifeddine
Pas encore d'évaluation
Introduction À La Théorie Des Graphes by Zekrifa Djabeur Mohamed Seifeddine
236 pages
(Que Sais-Je 1554) Aimé Sac - (Z-Library)
Pas encore d'évaluation
(Que Sais-Je 1554) Aimé Sac - (Z-Library)
71 pages
Cours de Probabilités - Exercices Corrigés
Pas encore d'évaluation
Cours de Probabilités - Exercices Corrigés
108 pages
Développement Du Modèle D'ising À Haute Température Corrigé
Pas encore d'évaluation
Développement Du Modèle D'ising À Haute Température Corrigé
3 pages
Ex3 Corr
Pas encore d'évaluation
Ex3 Corr
9 pages
LEPL1108 APE12 Sol
Pas encore d'évaluation
LEPL1108 APE12 Sol
5 pages
Cour Theorie Des Graphes AIT ABDESSELAM
Pas encore d'évaluation
Cour Theorie Des Graphes AIT ABDESSELAM
68 pages
Coloriage
Pas encore d'évaluation
Coloriage
4 pages
Polycopie Cours Probas Stats 2023 24
Pas encore d'évaluation
Polycopie Cours Probas Stats 2023 24
38 pages
Théorie des Graphes: Concepts Clés
Pas encore d'évaluation
Théorie des Graphes: Concepts Clés
54 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
13 pages
Programme Terminale ES: Théorème d'Euler et Graphes
0% (1)
Programme Terminale ES: Théorème d'Euler et Graphes
27 pages
Graphes et Algorithmes Terminale ES
Pas encore d'évaluation
Graphes et Algorithmes Terminale ES
27 pages
Cours THG
Pas encore d'évaluation
Cours THG
44 pages
Casse Magistere
Pas encore d'évaluation
Casse Magistere
11 pages
Serie 3
Pas encore d'évaluation
Serie 3
52 pages
Introduction à la théorie des graphes
100% (1)
Introduction à la théorie des graphes
7 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
11 pages
Chapitre 3
Pas encore d'évaluation
Chapitre 3
43 pages
Théorie Des Graphes
Pas encore d'évaluation
Théorie Des Graphes
57 pages
Chap - 05 - Graphe1
Pas encore d'évaluation
Chap - 05 - Graphe1
77 pages
20-21 Chap1
Pas encore d'évaluation
20-21 Chap1
25 pages
The orieGraphesIntroChap1Chap2
Pas encore d'évaluation
The orieGraphesIntroChap1Chap2
48 pages
Cours Graphes IREM
Pas encore d'évaluation
Cours Graphes IREM
50 pages
Graphes (Recovered)
Pas encore d'évaluation
Graphes (Recovered)
44 pages
Introduction à la probabilité et statistique
Pas encore d'évaluation
Introduction à la probabilité et statistique
93 pages
Cour Theorie Des Graphes AIT ABDESSELAM 1-1 PDF
Pas encore d'évaluation
Cour Theorie Des Graphes AIT ABDESSELAM 1-1 PDF
36 pages
N1MA0011 Poly Elements de Theorie Des Graphes
Pas encore d'évaluation
N1MA0011 Poly Elements de Theorie Des Graphes
42 pages
Prob
Pas encore d'évaluation
Prob
46 pages
Graph Theory Notes
Pas encore d'évaluation
Graph Theory Notes
81 pages
Theorie Des Graphes
Pas encore d'évaluation
Theorie Des Graphes
4 pages
Théorie Des Graphes Et Combinatoires
Pas encore d'évaluation
Théorie Des Graphes Et Combinatoires
67 pages
Chapitre 1-VF (4429)
Pas encore d'évaluation
Chapitre 1-VF (4429)
67 pages
USTHB - FI - L3Info - ThGRA - Chapitre 1 - Corrige - Serie
Pas encore d'évaluation
USTHB - FI - L3Info - ThGRA - Chapitre 1 - Corrige - Serie
3 pages
Analyse de la Fonction f et Conjecture
Pas encore d'évaluation
Analyse de la Fonction f et Conjecture
2 pages
Polycopié Méthodes Numériques
Pas encore d'évaluation
Polycopié Méthodes Numériques
111 pages
Fiche de Travaux Diriges Tles C Suites Corriges
100% (1)
Fiche de Travaux Diriges Tles C Suites Corriges
78 pages
PEG - Généralités Sur Les Fonctions D'une Variable Réelle
Pas encore d'évaluation
PEG - Généralités Sur Les Fonctions D'une Variable Réelle
15 pages
Visa Du BAC TS2 PDF - 1
Pas encore d'évaluation
Visa Du BAC TS2 PDF - 1
267 pages
04 La Fonction Derivee Bis
Pas encore d'évaluation
04 La Fonction Derivee Bis
29 pages
Dérivabilité et Formule de Taylor
100% (1)
Dérivabilité et Formule de Taylor
8 pages
Cours Suites Réelles Et Complexes
Pas encore d'évaluation
Cours Suites Réelles Et Complexes
12 pages
Lemme de Fatou : Intégration de Lebesgue
Pas encore d'évaluation
Lemme de Fatou : Intégration de Lebesgue
9 pages
TD 1 - Révisions (Réels, Complexes, Récurrence), Fonctions Et Trigonométrie
Pas encore d'évaluation
TD 1 - Révisions (Réels, Complexes, Récurrence), Fonctions Et Trigonométrie
8 pages
HTTPSWWW - Maths Et Tiques - Frtelechtderfct PDF
Pas encore d'évaluation
HTTPSWWW - Maths Et Tiques - Frtelechtderfct PDF
21 pages
Mpsi 3 Cpge My Ali Cherif 2024-2025: Xercice 1
Pas encore d'évaluation
Mpsi 3 Cpge My Ali Cherif 2024-2025: Xercice 1
3 pages
Mathématique Economique 1ère Année de Licence en Economie Gestion
Pas encore d'évaluation
Mathématique Economique 1ère Année de Licence en Economie Gestion
74 pages
Chapitre 6
Pas encore d'évaluation
Chapitre 6
8 pages
Révision des Équations Différentielles
Pas encore d'évaluation
Révision des Équations Différentielles
4 pages
ECN700A12
Pas encore d'évaluation
ECN700A12
22 pages
MP 2020 2021 ds01
Pas encore d'évaluation
MP 2020 2021 ds01
10 pages
Introduction aux Fonctions Mathématiques
Pas encore d'évaluation
Introduction aux Fonctions Mathématiques
6 pages
2.resume Generalites - Sur.les - Fonctions
Pas encore d'évaluation
2.resume Generalites - Sur.les - Fonctions
2 pages
Fonction TS1 2025
Pas encore d'évaluation
Fonction TS1 2025
4 pages
Suites Arithmétiques et Géométriques
Pas encore d'évaluation
Suites Arithmétiques et Géométriques
22 pages
Chapitre 1 Limites Et Continuit e
Pas encore d'évaluation
Chapitre 1 Limites Et Continuit e
10 pages
Exercices sur les fonctions en maths
Pas encore d'évaluation
Exercices sur les fonctions en maths
2 pages
1sex G Fonction Res PDF
Pas encore d'évaluation
1sex G Fonction Res PDF
5 pages
Calcul Differentiel
Pas encore d'évaluation
Calcul Differentiel
16 pages
Cours Math - Chap 2 Analyse Continuité Et Limites - Bac Math (2009-2010) MR Abdelbasset Laataoui PDF
Pas encore d'évaluation
Cours Math - Chap 2 Analyse Continuité Et Limites - Bac Math (2009-2010) MR Abdelbasset Laataoui PDF
8 pages
(Collection Enseignement Des Sciences 44) Schwartz, Laurent-Analyse III - Calcul Intégral-Hermann (1993)
100% (1)
(Collection Enseignement Des Sciences 44) Schwartz, Laurent-Analyse III - Calcul Intégral-Hermann (1993)
459 pages
Correction Exo 3 8 10 12 18 v2
Pas encore d'évaluation
Correction Exo 3 8 10 12 18 v2
12 pages
Problème d'ATS par Huguette Klein
Pas encore d'évaluation
Problème d'ATS par Huguette Klein
2 pages
Cours de Mathématiques: Analyse et Probabilités
Pas encore d'évaluation
Cours de Mathématiques: Analyse et Probabilités
87 pages