Mines-Ponts 2024 — Mathématiques 2 — MP
Phénomènes de seuil dans les graphes
Dans ce problème, {n} désigne un entier supérieur à {1}. On note {\llbracket1,n\rrbracket} l’ensemble des entiers compris entre {1} et {n}, {\mathfrak S_n} le groupe de ses permutations et {\mathcal M_n(\mathbb R)} l’ensemble des matrices réelles carrées d’ordre {n}.
Le cardinal d’un ensemble fini {E} est noté {\operatorname{card}(E)} ou {|E|}.
Un graphe {G} est un couple {(S,A)} où {S} est un ensemble fini non vide de sommets, et {A} un ensemble, éventuellement vide, d’arêtes. Chaque arête est une paire {\{s,s'\}} de sommets distincts.
Un sommet n’appartenant à aucune arête est dit isolé. Par convention, le graphe vide est le couple {(\varnothing,\varnothing)}.
On représente les sommets par des disques et les arêtes par des segments les reliant. Il n’y a ni boucle reliant un sommet à lui-même, ni arête répétée.
Figure 1 de l’énoncé. Le graphe à neuf sommets a pour ensemble de sommets {\llbracket1,9\rrbracket} et pour ensemble d’arêtes :
{\begin{array}{l}A=\{\{1,2\},\{1,5\},\{1,6\},\\[4pt]\qquad\{2,3\},\{2,9\},\{2,8\}\}.\end{array}}Les sommets {4} et {7} sont isolés. Sa représentation est reprise dans la figure jointe.
Une étoile de centre {s} à {d\geq1} branches est un graphe dont les {d+1} sommets sont {s,s_1,\ldots,s_d}, et dont les arêtes sont exactement les {\{s,s_i\}}, pour {1\leq i\leq d}.
Figure 2 de l’énoncé. L’étoile de centre {4} à cinq branches a pour sommets {\{1,3,4,5,6,8\}} ; elle est également représentée dans la planche jointe.
Pour deux graphes {G=(S,A)} et {G'=(S',A')}, on dit que {G'} est inclus dans {G} si {S'\subset S} et {A'\subset A}.
On dit que {G'} est une copie de {G} s’il existe une bijection {\sigma:S'\to S} telle que, pour tous {s',t'\in S'} :
{\{s',t'\}\in A'\ \Longleftrightarrow\ \{\sigma(s'),\sigma(t')\}\in A.}Le graphe de la figure 1 contient plusieurs copies d’étoiles à une ou deux branches, une étoile à trois branches de centre {1}, et une étoile à quatre branches de centre {2}.
La première partie étudie des propriétés algébriques des matrices d’adjacence. Les deux parties suivantes, indépendantes de la première, étudient deux exemples de fonctions de seuil pour des graphes aléatoires.
Partie I — Quelques propriétés algébriques des matrices d’adjacence
Soit {G=(S,A)} un graphe non vide avec {|S|=n}. Une indexation des sommets est une bijection {\sigma:\llbracket1,n\rrbracket\to S}. On écrit ainsi {S=\{\sigma(1),\ldots,\sigma(n)\}}.
La matrice d’adjacence associée est définie par :
{(M_{G,\sigma})_{i,j}=\left\{\begin{array}{ll}1&\text{si }\{\sigma(i),\sigma(j)\}\in A,\\[4pt]0&\text{sinon}.\end{array}\right.}Elle est symétrique et tous ses coefficients diagonaux sont nuls.
Pour le graphe de la figure 1, avec l’indexation naturelle, on obtient :
{M_{G,\mathrm{id}}=\begin{pmatrix}0&1&0&0&1&1&0&0&0\\[4pt]1&0&1&0&0&0&0&1&1\\[4pt]0&1&0&0&0&0&0&0&0\\[4pt]0&0&0&0&0&0&0&0&0\\[4pt]1&0&0&0&0&0&0&0&0\\[4pt]1&0&0&0&0&0&0&0&0\\[4pt]0&0&0&0&0&0&0&0&0\\[4pt]0&1&0&0&0&0&0&0&0\\[4pt]0&1&0&0&0&0&0&0&0\end{pmatrix}.}Soient {\rho\in\mathfrak S_n} et {M=(m_{i,j})_{1\leq i,j\leq n}\in\mathcal M_n(\mathbb R)}.
En déduire que, si {G=(S,A)} est un graphe non vide et si {\sigma,\sigma'} sont deux indexations de {S}, les matrices {M_{G,\sigma}} et {M_{G,\sigma'}} sont semblables.
Comme les matrices d’adjacence d’un même graphe sont semblables, elles ont le même polynôme caractéristique. On note {\chi_G} ce polynôme, appelé polynôme caractéristique du graphe.
Par convention, celui du graphe vide est le polynôme constant égal à {1}.
{\chi_G(X)=X^n+\sum_{k=0}^{n-1}a_kX^k.}Donner {a_{n-1}} et exprimer {a_{n-2}} à l’aide de {|A|}.
Déterminer les valeurs et vecteurs propres d’une matrice d’adjacence de ce graphe.
Si {G=(S,A)} est non vide et {s\in S}, le graphe {G\setminus s} a pour sommets {S\setminus\{s\}} et conserve exactement les arêtes de {G} ne contenant pas {s}.
La figure 3 de l’énoncé illustre cette suppression pour le sommet {2}. Les deux graphes sont repris dans la planche jointe.
Soient {G_1=(S_1,A_1)} et {G_2=(S_2,A_2)} deux graphes non vides avec {S_1\cap S_2=\varnothing}. Fixons {s_1\in S_1} et {s_2\in S_2}.
On définit {G=(S,A)} en ajoutant une arête entre ces deux sommets :
{S=S_1\cup S_2,\qquad A=A_1\cup A_2\cup\{\{s_1,s_2\}\}.}
{\chi_G=\chi_{G_1}\chi_{G_2}-\chi_{G_1\setminus s_1}\chi_{G_2\setminus s_2}.}
Quel est le rang de sa matrice d’adjacence ?
Dans toute la suite, on suppose {n\geq2}. On note :
{N=\binom n2=\frac{n(n-1)}2.}On désigne par {\Omega_n} l’ensemble des graphes dont l’ensemble des sommets est {S=\llbracket1,n\rrbracket}. On fixe {p_n\in]0,1[} et l’on pose {q_n=1-p_n}.
Pour chaque paire {\{i,j\}\subset S} avec {i\neq j}, on définit :
{X_{\{i,j\}}(G)=\left\{\begin{array}{ll}1&\text{si }\{i,j\}\in A,\\[4pt]0&\text{sinon},\end{array}\right.\qquad G=(S,A).}L’événement {(X_{\{i,j\}}=1)} est donc l’ensemble des graphes contenant l’arête {\{i,j\}}. Pour {G=(S,A)}, on a :
{\begin{array}{l}\displaystyle\{G\}=\left(\bigcap_{\{i,j\}\in A}\{X_{\{i,j\}}=1\}\right)\\[4pt]\qquad\displaystyle\cap\left(\bigcap_{\{i,j\}\notin A}\{X_{\{i,j\}}=0\}\right).\quad(1)\end{array}}Les intersections portent sur les paires de sommets distincts de {S}.
On admet l’existence d’une probabilité {\mathbb P} sur {(\Omega_n,\mathcal P(\Omega_n))} pour laquelle ces {N} indicatrices sont indépendantes et de loi de Bernoulli de paramètre {p_n}.
On note {\mathcal E_n=(\Omega_n,\mathcal P(\Omega_n),\mathbb P)} cet espace probabilisé. Les arêtes y apparaissent indépendamment, chacune avec probabilité {p_n}.
On étudie une propriété {\mathcal P_n} vérifiée par certains graphes de {\Omega_n}.
Une fonction de seuil pour cette propriété est une suite {(t_k)_{k\geq2}} de réels strictement positifs telle que, lorsque {n\to+\infty} :
{\begin{array}{l}p_n=o(t_n)\ \Longrightarrow\ \mathbb P(\mathcal P_n)\longrightarrow0,\\[4pt]t_n=o(p_n)\ \Longrightarrow\ \mathbb P(\mathcal P_n)\longrightarrow1.\end{array}}
Partie II — Une première fonction de seuil
Section A — Deux inégalités
Soit {X} une variable aléatoire à valeurs dans {\mathbb N}, définie sur un espace probabilisé {(\Omega,\mathcal A,\mathbb P)}, admettant une espérance {E(X)} et une variance {V(X)}.
{\mathbb P(X=0)\leq\frac{V(X)}{E(X)^2}.}Indication : on remarquera que {(X=0)\subset(|X-E(X)|\geq E(X))}.
Section B — Une fonction de seuil
Partie III — Fonction de seuil de la copie d’un graphe
Pour un graphe {G=(S,A)}, on note {s_G=|S|} et {a_G=|A|}.
Fixons un graphe {G_0=(S_0,A_0)}, et posons {s_0=|S_0|\geq2} et {a_0=|A_0|\geq1}. On étudie la propriété {\mathcal P_n} : « contenir une copie de {G_0} ».
La variable {X_n^0(G)} compte le nombre de copies de {G_0} contenues dans {G\in\Omega_n}.
On note {\mathcal C_0} l’ensemble des copies {H=(S_H,A_H)} de {G_0} telles que {S_H\subset\llbracket1,n\rrbracket}.
Pour tout graphe {H} dont les sommets sont dans {\llbracket1,n\rrbracket}, on définit l’indicatrice :
{X_H(G)=\left\{\begin{array}{ll}1&\text{si }H\subset G,\\[4pt]0&\text{sinon}.\end{array}\right.}Enfin, on pose :
{\omega_0=\min_{\substack{H\subset G_0\\[4pt]a_H\geq1}}\frac{s_H}{a_H}.}Cette quantité est bien définie et strictement positive : le minimum porte sur un ensemble fini non vide, puisque {G_0} a au moins une arête.
Précision sur l’inclusion. Contenir une copie n’impose pas l’absence d’autres arêtes entre les sommets de cette copie. Il s’agit de sous-graphes, pas nécessairement de sous-graphes induits.
Exprimer {|\mathcal C_0|} à l’aide de {c_0}. En utilisant un majorant simple de {c_0}, justifier que {|\mathcal C_0|} est inférieur à {n^{s_0}}.
{E(X_n^0)=\sum_{H\in\mathcal C_0}\mathbb P(H\subset G)\leq n^{s_0}p_n^{a_0}.}
Indication : on pourra introduire {H_0\subset G_0} réalisant le minimum définissant {\omega_0}.
On suppose dorénavant que {n^{\omega_0}p_n\to+\infty} lorsque {n\to+\infty}.
{\begin{array}{rl}E((X_n^0)^2)&=\displaystyle\sum_{(H,H')\in\mathcal C_0^2}\mathbb P(H\cup H'\subset G)\\[4pt]&=\displaystyle\sum_{(H,H')\in\mathcal C_0^2}p_n^{2a_0-a_{H\cap H'}}.\end{array}}
Pour {k\in\llbracket0,s_0\rrbracket}, on note :
{\Sigma_k=\sum_{\substack{(H,H')\in\mathcal C_0^2\\[4pt]s_{H\cap H'}=k}}\mathbb P(H\cup H'\subset G).}
{\begin{array}{rl}\Sigma_k&\leq\displaystyle\sum_{H\in\mathcal C_0}\binom{s_0}k\binom{n-s_0}{s_0-k}\\[4pt]&\qquad\times c_0p_n^{2a_0}p_n^{-k/\omega_0}.\end{array}}
{\binom rq r^{-q}\geq\frac1{q!}\left(1-\frac{q-1}q\right)^q.}En déduire que, pour {k\in\llbracket1,s_0\rrbracket}, on a {\Sigma_k=o(E(X_n^0)^2)} lorsque {n\to+\infty}.
{\lim_{n\to+\infty}\frac{V(X_n^0)}{E(X_n^0)^2}=0.}
Fin du problème.