Année 2023-24 - Equipe PEIPS (CMAP)

Groupe de Travail Discrete Random Objects: Limits and EStimates

Résumé de la séance 1 - Introduction au modèle d'Erdős-Rényi

Oratrice : Vanessa Dan (résumé par Maxime Marivain)

Sommaire

• Présentation du modèle
• Transition de phase en $\log(n)/n$
• Premières bornes : comparaisons avec des Galton-Watson
• Références

Présentation du modèle

Soit $n\geq 1$ et $p\in (0,1)$ on considère le graphe de sommets $1,2,\dots,n$ tel que pour tous $i< j$ on a $$\mathbb{P}(i\text{ relié à }j)=p,$$ indépendamment pour les $\binom{n}{2}$ arêtes potentielles. En général, on note ce graphe $G(n,p)$. Pour un sommet $v$ donné, on note également $C(v)$ la composante connexe contenant $v$ et $\mid C(v) \mid$ la taille de cette composante connexe. Dans la suite on aura $p=\frac{\lambda}{n}$. On notera aussi:

• $\mathbb{P}_{\lambda}$ la distribution de $G(n,\frac{\lambda}{n})$
• $\mathbb{P}_{n,p}$ la distribution d'un $\mu -BGW, \mu\sim Bin(n,p)$

Connectivité : Transition de phase en $\log(n)/n$

Théorème:

Soit $c\in\mathbb{R}$ et $p$ tel que $np=\log(n)+c$. On a alors: $$\lim_{n\rightarrow+\infty} \mathbb{P}(G(n,p) \;est\; connexe)=\exp(-\exp(-c)).$$

Premières bornes : comparaisons avec des Galton-Watson

Théorème:

$\mid C(1) \mid\leq T^{>}$ i.e $\forall k \geq 1$ $$\mathbb{P}_{n,p}(\mid C(1) \mid\geq k)\leq \mathbb{P}_{n,p}(T^{>}\geq k)$$ où $T^{>}$ est le nombre d'individus dans un $\mu-BGW$, $\mu\sim Bin(n,p)$.

Théorème:

$\forall k \in \{1;...n\}$ $$\mathbb{P}_{n,p}(\mid C(1) \mid\geq k)\geq \mathbb{P}_{n-k,p}(T^{<}\geq k)$$ où $T^{<}$ est le nombre d'individus dans un $\mu-BGW$, $\mu\sim Bin(n-k,p)$.

Références

N.Curien. Random Graphs (2023). Disponible sur ce lien .
M.Draief et L.Massoulié. Epidemics and rumours in complex networks (2009). Cambridge University Press.
R.van der Hofstad. Random graphs and complex networks (2009). Disponible sur ce lien.