Connectez-vous pour consulter le corrigé.
Phénomènes de seuil dans les graphes
Durée de l’épreuve : 4 heures. L’usage de la calculatrice et de tout dispositif électronique est interdit.
Sujet du Concours commun Mines-Ponts 2024, propriété du GIP CCMP, reproduit avec son autorisation.
Dans ce problème, \(n\) désigne un entier supérieur à 1.
On désigne par \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) l’ensemble des entiers compris entre 1 et \(n\).
Le groupe symétrique des permutations de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) est noté \(\mathcal{S}_n\).
L’ensemble des matrices carrées d’ordre \(n\) à coefficients réels est noté \(\mathcal{M}_n(\mathbb{R})\).
Le cardinal d’un ensemble fini \(E\) sera noté \(\mathrm{card}(E)\) ou \(|E|\).
Un graphe \(G\) est un couple \((S,A)\) où :
\(S\) désigne un ensemble fini non vide d’éléments appelés sommets du graphe \(G\)
\(A\) désigne un ensemble éventuellement vide d’éléments appelés arêtes du graphe \(G\), une arête étant un ensemble \(\big\{s,s'\big\}\) où \(s\) et \(s'\) sont des sommets distincts de \(S\).
Un sommet n’appartenant à aucune arête est dit isolé.
Par convention, le graphe vide est le couple d’ensembles vides \((\varnothing,\varnothing)\).
On peut représenter un graphe non vide dans un plan à l’aide :
de disques schématisant les sommets du graphe
de segments reliant ces disques pour les arêtes du graphe.
Par exemple, on a représenté sur la Figure 1, le graphe \(G=(S,A)\) avec : \[S=\left[\kern-0.15em\left[ {1,9} \right]\kern-0.15em\right]\quad\text{et}\quad A=\Big\{\big\{1,2\big\},\big\{1,5\big\},\big\{1,6\big\},\big\{2,3\big\},\big\{2,9\big\},\big\{2,8\big\}\Big\}\]
Figure 1 – un graphe à 9 sommets et 6 arêtes
On remarquera que les arêtes sont constituées de deux sommets distincts, ce qui interdit la présence de « boucles» reliant un sommet à lui-même.
De plus, une même arête ne peut être présente plusieurs fois dans un graphe.
Un type de graphe utilisé dans ce problème est l’étoile.
Une étoile de centre \(s\) et à \(d\) branches avec \(d\) entier naturel non nul, est un graphe \((S,A)\) où \(S=\big\{s,s_1,s_2,\dots,s_d\big\}\) est de cardinal \(d+1\), et \(A\) est du type \[A=\Big\{\big\{s,s_1\big\},\big\{s,s_2\big\},\dots,\big\{s,s_d\big\}\Big\}\]
On a représenté Figure 2 une étoile de centre 4 à 5 branches avec \(S=\big\{1,3,4,5,6,8\big\}\).
Figure 2 – une étoile à 5 branches
Soient \(G=(S,A)\) et \(G'=(S',A')\) deux graphes ; on dit que :
\(G'\) est inclus dans \(G\) si \(S'\subset S\) et \(A'\subset A\)
\(G'\) est une copie de \(G\) s’il existe une bijection \(\sigma\) de \(S'\) dans \(S\) telle que : \[\forall(s',t')\in S'\times S'\qquad\big\{s',t'\big\}\in A'\iff\big\{\sigma(s'),\sigma(t')\big\}\in A\]
Par exemple, le graphe de la Figure 1 contient plusieurs copies d’étoiles à une branche (correspondant aux segments), plusieurs copies d’étoiles à deux branches, mais aussi une copie d’une étoile à 3 branches (de centre 1) et une copie d’une étoile à 4 branches (de centre 2).
Dans une première partie, on étudie quelques propriétés algébriques des matrices d’adjacence.
On introduit ensuite la notion de fonction de seuil en probabilité des graphes aléatoires.
Les deux parties qui suivent la première partie sont indépendantes de celle-ci, et sont consacrées à l’étude de deux exemples.
Soit \(G=(S,A)\) un graphe non vide où \(|S|=n\). Indexer arbitrairement les sommets de 1 à \(n\) revient à choisir une bijection (appelée aussi indexation) \(\sigma\) entre \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) et \(S\). On pourra alors noter : \[S=\big\{\sigma(1),\sigma(2),\dots,\sigma(n)\big\}\] où \(\sigma(i)\) est le sommet d’index \(i\).
Une indexation \(\sigma\) étant choisie, on définit la matrice d’adjacence \(M_{G,\sigma}\) du graphe \(G\) associée à \(\sigma\) comme étant la matrice de \(\mathcal{M}_n(\mathbb{R})\) dont le coefficient situé sur la \(i^{\mathrm{e}}\) ligne et la \(j^{\mathrm{e}}\) colonne est : \[(M_{G,\sigma})_{i,j}=\begin{cases}1 & \text{si } \{\sigma(i),\sigma(j)\}\in A\\ 0 & \text{sinon}\end{cases}\]
On remarquera d’une part que la matrice \(M_{G,\sigma}\) est toujours symétrique (car pour tous \(i\) et \(j\) entiers, \(\big\{i,j\big\}=\big\{j,i\big\}\)) et d’autre part que les termes de la diagonale sont tous nuls (pas de boucle dans un graphe).
Voici par exemple la matrice d’adjacence \(M_{G,\mathrm{id}}\) du graphe \(G\) représenté sur la Figure 1 : \[M_{G,\mathrm{id}}=\left(\begin{smallmatrix} 0&1&0&0&1&1&0&0&0\\ 1&0&1&0&0&0&0&1&1\\ 0&1&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0 \end{smallmatrix}\right)\]
Soit \(\rho\) une permutation du groupe symétrique \(\mathcal{S}_n\) et \(M=(m_{i,j})_{1\leqslant i,j\leqslant n}\) une matrice de \(\mathcal{M}_n(\mathbb{R})\).
Montrer que les matrices \(M\) et \((m_{\rho(i),\rho(j)})_{1\leqslant i,j\leqslant n}\) sont semblables.
En déduire que si \(G=(S,A)\) est un graphe non vide, et si \(\sigma\) et \(\sigma'\) sont deux indexations de \(S\), alors \(M_{G,\sigma}\) et \(M_{G,\sigma'}\) sont semblables.
Justifier qu’une matrice d’adjacence d’un graphe non vide est diagonalisable.
Montrer qu’une matrice d’adjacence d’un graphe non vide n’est jamais de rang 1.
Montrer qu’une matrice d’adjacence d’un graphe dont les sommets non isolés forment un graphe de type étoile est de rang 2 et représenter un exemple de graphe dont la matrice d’adjacence est de rang 2 et qui n’est pas du type précédent.
Si \(G=(S,A)\) est un graphe non vide et si \(\sigma\) et \(\sigma'\) sont des indexations de \(S\), comme les matrices \(M_{G,\sigma}\) et \(M_{G,\sigma'}\) sont semblables, elles ont même polynôme caractéristique (ce que l’on ne demande pas de démontrer).
On notera \(\chi_G\) ce polynôme caractéristique commun et on dira que \(\chi_G\) est le polynôme caractéristique du graphe \(G\).
Par convention, le polynôme caractéristique du graphe vide est le polynôme constant égal à 1.
Soit \(G\) un graphe et \(G'\) une copie de \(G\). Justifier que \(\chi_G=\chi_{G'}\).
Soit \(G=(S,A)\) un graphe avec \(|S|=n\geqslant2\). On note \(\chi_G(X)=X^n+\displaystyle\sum_{k=0}^{n-1}a_kX^k\).
Donner la valeur de \(a_{n-1}\) et exprimer \(a_{n-2}\) à l’aide de \(|A|\).
En déduire le polynôme caractéristique d’un graphe à \(n\) sommets dont les sommets non isolés forment une étoile à \(d\) branches avec \(1\leqslant d\leqslant n-1\).
Déterminer alors les valeurs et vecteurs propres d’une matrice d’adjacence de ce graphe.
Si \(G=(S,A)\) est un graphe non vide et si \(s\) appartient à \(S\), on définit le graphe \(G\setminus s\) comme étant le graphe dont l’ensemble des sommets est \(S\setminus\big\{s\big\}\) et l’ensemble des arêtes est constitué des arêtes de \(A\) qui ne contiennent pas \(s\). Voici par exemple Figure 3 un graphe \(G\) et le graphe \(G\setminus2\) :
(a) Un graphe \(G\)
(b) Le graphe \(G\setminus2\)
Figure 3 – un graphe \(G\), et le graphe \(G\setminus2\)
Soient \(G_1=(S_1,A_1)\) et \(G_2=(S_2,A_2)\) deux graphes non vides tels que \(S_1\) et \(S_2\) soient disjoints, c’est-à-dire tels que \(S_1\cap S_2=\varnothing\). Soit \(s_1\in S_1\) et soit \(s_2\in S_2\).
On définit le graphe \(G=(S,A)\) avec \(S=S_1\cup S_2\) et \(A=A_1\cup A_2\cup\Big\{\big\{s_1,s_2\big\}\Big\}\).
Montrer que : \[\chi_G=\chi_{G_1}\times\chi_{G_2}-\chi_{G_1\setminus s_1}\times\chi_{G_2\setminus s_2}\]
Déterminer le polynôme caractéristique de la double étoile à \(d_1+d_2+2\) sommets, constituée respectivement de deux étoiles disjointes à \(d_1\) et \(d_2\) branches, à qui l’on a ajouté une arête supplémentaire reliant les deux centres des deux étoiles.
Quel est le rang de la matrice d’adjacence de cette double étoile ?
Dans toute la suite de ce problème, on suppose que \(n\) est supérieur à 2 et on notera :
\(N\) l’entier \(\displaystyle\binom{n}{2}=\frac{n(n-1)}{2}\)
\(\Omega_n\) l’ensemble des graphes de sommets \(S=\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\)
\(p_n\) un réel dépendant de \(n\) appartenant à l’intervalle \(\left]0,1\right[\) et \(q_n=1-p_n\).
Pour tous \(i\) et \(j\) appartenant à \(S=\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) avec \(i\neq j\), on note \(X_{\{i,j\}}\) l’application de \(\Omega_n\) dans \(\big\{0,1\big\}\) telle que pour tout \(G\in\Omega_n\) avec \(G=(S,A)\) : \[X_{\{i,j\}}(G)=\begin{cases}1 & \text{si } \big\{i,j\big\}\in A\\ 0 & \text{si } \big\{i,j\big\}\notin A\end{cases}\]
Ainsi, \((X_{\{i,j\}}=1)=\big\{G\in\Omega_n\mid X_{\{i,j\}}(G)=1\big\}\) est l’ensemble des graphes de \(\Omega_n\) dont \(\big\{i,j\big\}\) est une arête. Réciproquement, on remarquera aussi que pour \(G=(S,A)\), on peut écrire \[\{G\}=\bigcap_{\{i,j\}\in A}(X_{\{i,j\}}=1)\bigcap_{\{i,j\}\notin A}(X_{\{i,j\}}=0)\tag{1}\]
On admet l’existence d’une probabilité \(\mathbb{P}\) sur \(\big(\Omega_n,\mathcal{P}(\Omega_n)\big)\) telle que les applications \(X_{\{i,j\}}\) soient des variables aléatoires de Bernoulli de paramètre \(p_n\) et indépendantes. On note \(\mathcal{E}_n=\big(\Omega_n,\mathcal{P}(\Omega_n),\mathbb{P}\big)\) l’espace probabilisé ainsi construit.
Autrement dit, pour un graphe \(G\) donné appartenant à \(\Omega_n\), la probabilité qu’une arête \(\big\{i,j\big\}\) soit contenue dans \(G\) est \(p_n\), et les arêtes apparaissent dans \(G\) de façon indépendante.
Soit \(G=(S,A)\in\Omega_n\). Déterminer la probabilité \(\mathbb{P}(\big\{G\big\})\) de l’événement élémentaire \(\big\{G\big\}\) en fonction de \(p_n\), \(q_n\), \(N\) et \(a=\mathrm{card}(A)\).
Retrouver alors le fait que \(\mathbb{P}(\Omega_n)=1\).
Dans la suite du problème on étudie la notion de fonction de seuil pour une propriété \(\mathcal{P}_n\) vérifiée sur une partie des graphes de \(\Omega_n\).
Une fonction de seuil pour la propriété \(\mathcal{P}_n\) est une suite \((t_k)_{k\geqslant2}\) de réels strictement positifs tels que :
si \(p_n=\circ(t_n)\) alors la limite, lorsque \(n\) tend vers \(+\infty\), de la probabilité pour que la propriété \(\mathcal{P}_n\) soit réalisée vaut 0
si \(t_n=\circ(p_n)\) alors la limite, lorsque \(n\) tend vers \(+\infty\), de la probabilité pour que la propriété \(\mathcal{P}_n\) soit réalisée vaut 1.
Soit \(X\) une variable aléatoire définie sur un espace probabilisé \((\Omega,\mathcal{A},\mathbb{P})\) à valeurs dans \(\mathbb{N}\) et admettant une espérance \(\mathbb{E}(X)\) et une variance \(\mathbb{V}(X)\).
Montrer que \(\mathbb{P}(X>0)\leqslant\mathbb{E}(X)\).
Montrer que si \(\mathbb{E}(X)\neq0\), alors \(\mathbb{P}(X=0)\leqslant\dfrac{\mathbb{V}(X)}{\big(\mathbb{E}(X)\big)^2}\).
Indication : on remarquera que \((X=0)\subset\big(|X-\mathbb{E}(X)|\geqslant\mathbb{E}(X)\big)\).
Quelle est la loi suivie par la variable aléatoire \(A_n\) représentant le nombre d’arêtes d’un graphe de \(\Omega_n\) ?
Montrer que si \(p_n=\circ\!\left(\dfrac{1}{n^2}\right)\) au voisinage de \(+\infty\), alors \(\displaystyle\lim_{n\to+\infty}\mathbb{P}(A_n>0)=0\).
Montrer que si \(\dfrac{1}{n^2}=\circ(p_n)\) au voisinage de \(+\infty\), alors \(\displaystyle\lim_{n\to+\infty}\mathbb{P}(A_n>0)=1\).
En déduire une propriété \(\mathcal{P}_n\) et sa fonction de seuil associée.
Si \(G=(S,A)\) est un graphe, on note \(s_G\) (resp. \(a_G\)) le cardinal de \(S\) (resp. \(A\)).
Soit \(G_0=(S_0,A_0)\) un graphe particulier fixé. Par commodité d’écriture, on note \(s_0=s_{G_0}\) le cardinal de \(S_0\), \(a_0=a_{G_0}\) le cardinal de \(A_0\) et on suppose que \(s_0\geqslant2\) et que \(a_0\geqslant1\).
On va étudier la fonction de seuil de la propriété \(\mathcal{P}_n\) : « contenir une copie de \(G_0\)».
On note \(X_n^0\) la variable aléatoire réelle discrète définie sur l’espace probabilisé \(\mathcal{E}_n\) telle que pour \(G\in\Omega_n\), l’entier \(X_n^0(G)\) est égal au nombre de copies de \(G_0\) contenues dans \(G\).
On introduit :
l’ensemble \(\mathcal{C}_0\) des copies de \(G_0\) dont les sommets sont inclus dans \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) : \[\mathcal{C}_0=\Big\{H\mid H\text{ est une copie de }G_0\text{ et }H=(S_H,A_H)\text{ avec }S_H\subset\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\Big\}\]
pour un graphe \(H=(S_H,A_H)\) avec \(S_H\subset\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), la variable aléatoire suivant une loi de Bernoulli \(X_H\) définie par : \[\forall G\in\Omega_n\qquad X_H(G)=\begin{cases}1 & \text{si } H\subset G\\ 0 & \text{sinon}\end{cases}\]
le réel \(\omega_0\) défini par : \[\omega_0=\min_{\substack{H\subset G_0\\ a_H\geqslant1}}\frac{s_H}{a_H}\]
Montrer que \[\mathbb{E}(X_H)=p_n^{a_H}\]
Soit \(S_0'\) un ensemble fixé de cardinal \(s_0\). On note \(c_0\) le nombre des graphes dont l’ensemble des sommets est \(S_0'\) et qui sont des copies de \(G_0\).
Exprimer le cardinal de \(\mathcal{C}_0\) à l’aide de \(c_0\) et en utilisant un majorant simple de \(c_0\), justifier que le cardinal de \(\mathcal{C}_0\) est inférieur à \(n^{s_0}\).
Exprimer \(X_n^0\) à l’aide de variables aléatoires du type \(X_H\), et montrer que : \[\mathbb{E}(X_n^0)=\sum_{H\in\mathcal{C}_0}\mathbb{P}(H\subset G)\leqslant n^{s_0}p_n^{a_0}\]
En déduire que si \(p_n=\circ\!\left(n^{-\omega_0}\right)\), alors \(\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n^0>0)=0\).
Indication : on pourra introduire \(H_0\subset G_0\) réalisant le minimum donnant \(\omega_0\).
On suppose dorénavant que \(\displaystyle\lim_{n\to+\infty}\Big(n^{\omega_0}p_n\Big)=+\infty\).
Montrer que l’espérance \(\mathbb{E}\Big((X_n^0)^2\Big)\) vérifie : \[\mathbb{E}\Big((X_n^0)^2\Big)=\sum_{(H,H')\in\mathcal{C}_0^2}\mathbb{P}(H\cup H'\subset G)=\sum_{(H,H')\in\mathcal{C}_0^2}p_n^{2a_0-a_{H\cap H'}}\]
Pour \(k\in\left[\kern-0.15em\left[ {0,s_0} \right]\kern-0.15em\right]\), on note : \[\Sigma_k=\sum_{\substack{(H,H')\in\mathcal{C}_0^2\\ s_{H\cap H'}=k}}\mathbb{P}(H\cup H'\subset G)\]
Montrer que \(\Sigma_0\leqslant\Big(\mathbb{E}(X_n^0)\Big)^2\).
Soit \(k\in\left[\kern-0.15em\left[ {1,s_0} \right]\kern-0.15em\right]\) ; montrer que : \[\Sigma_k\leqslant\sum_{H\in\mathcal{C}_0}\binom{s_0}{k}\binom{n-s_0}{s_0-k}c_0p_n^{2a_0}p_n^{-\frac{k}{\omega_0}}\]
Justifier que pour tous entiers naturels \(q\) et \(r\) vérifiant \(1\leqslant q\leqslant r\), on a : \[\binom{r}{q}r^{-q}\geqslant\frac{1}{q!}\left(1-\frac{q-1}{q}\right)^q\] et en déduire que pour \(k\in\left[\kern-0.15em\left[ {1,s_0} \right]\kern-0.15em\right]\), on a \(\Sigma_k=\circ\!\left(\Big(\mathbb{E}(X_n^0\Big)^2\right)\) lorsque \(n\) tend vers \(+\infty\).
Montrer que \(\displaystyle\lim_{n\to+\infty}\frac{\mathbb{V}(X_n^0)}{\Big(\mathbb{E}(X_n^0)\Big)^2}=0\) où \(\mathbb{V}(X_n^0)\) désigne la variance de \(X_n^0\).
Montrer alors que la suite \((k^{-\omega_0})_{k\geqslant2}\) est une fonction de seuil pour la propriété \(\mathcal{P}_n\).
Retrouver le résultat de la question 16 \(\triangleright\) et déterminer une fonction de seuil pour la propriété « contenir une copie de l’étoile à \(d\) branches» avec \(d\) entier fixé supérieur à 1.
Fin du problème
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Un sujet original mêlant algèbre linéaire et probabilités : spectre des matrices d'adjacence de graphes (étoiles, complets), puis graphes aléatoires et apparition d'un sous-graphe au-delà d'un seuil par la méthode des premier et second moments.
Long mais très guidé.