Questions du sujet
1. 1~Û Montrer que les matrices \( M \) et \( (m_{\varphi(i),\varphi(j)})_{1 \leq i,j \leq n} \) sont semblables.\\
En déduire que si \( G = (S, A) \) est un graphe non vide, et si \( \iota \) et \( \iota’ \) sont deux indexations de \( S \), alors \( M_{G,\iota} \) et \( M_{G,\iota’} \) sont semblables.
2. 2~Û Justifier qu’une matrice d’adjacence d’un graphe non vide est diagonalisable.
3. 3~Û Montrer qu’une matrice d’adjacence d’un graphe non vide n’est jamais de rang 1.
4. 4~Û 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.
5. 5~Û Soit \( G \) un graphe et \( G’ \) une copie de \( G \). Justifier que \( \chi_G = \chi_{G’} \).}
6. 6~Û Soit \( G = (S, A) \) un graphe avec \( |S| = n \geq 2 \). On note \( \chi_G(X) = X^n + \sum_{k=0}^{n-1} a_k X^k \).\\
Donner la valeur de \( a_{n-1} \) et exprimer \( a_{n-2} \) à l’aide de \( |A| \).
7. 7~Û 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 \leq d \leq n-1 \).\\
Déterminer alors les valeurs et vecteurs propres d’une matrice d’adjacence de ce graphe.
8. 8~Û Montrer que :\\[\jot]
\( \chi_G = \chi_{G_1} \cdot \chi_{G_2} – \chi_{G_1 \setminus s_1} \cdot \chi_{G_2 \setminus s_2} \)
9. 9~Û 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~?
10. 10~Û Soit \( G = (S, A) \in \mathcal{N}_n \). Déterminer la probabilité \( P(\{G\}) \) de l’événement élémentaire \( \{G\} \) en fonction de \( p_n, q_n, N \) et \( a = \operatorname{card}(A) \).\\
Retrouver alors le fait que \( P(\mathcal{N}_n) = 1 \).}
11. 11~Û Montrer que \( \mathbb{P}(X > 0) \leq \mathbb{E}(X) \).
12. 12~Û Montrer que si \( \mathbb{E}(X) \neq 0 \), alors \( \mathbb{P}(X = 0) \leq \dfrac{\mathrm{V}(X)}{(\mathbb{E}(X))^2} \).\\
\emph{Indication~: on remarquera que \( (X = 0) \subset \{|X – \mathbb{E}(X)| \geq \mathbb{E}(X)\} \).}
13. 13~Û Quelle est la loi suivie par la variable aléatoire \( A_n \) représentant le nombre d’arêtes d’un graphe de \( \mathcal{N}_n \)~?
14. 14~Û Montrer que si \( p_n = o\left(\frac{1}{n^2}\right) \) au voisinage de \( +\infty \), alors \( \lim_{n \to +\infty} \mathbb{P}(A_n > 0) = 0 \).
15. 15~Û Montrer que si \( \frac{1}{n^2} = o(p_n) \) au voisinage de \( +\infty \), alors \( \lim_{n \to +\infty} \mathbb{P}(A_n > 0) = 1 \).}
16. 16~Û En déduire une propriété \( \mathcal{P}_n \) et sa fonction de seuil associée.
17. 17~Û Montrer que \( \mathbb{E}(X_H) = p_n^{a_H} \).
18. 18~Û 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} \).
19. 19~Û 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) \leq n^{s_0} p_n^{a_0} \).
20. 20~Û En déduire que si \( p_n = o(n^{-\Theta_0}) \), alors \( \lim_{n \to +\infty} \mathbb{P}(X_n^0 > 0) = 0 \).\\
\emph{Indication~: on pourra introduire \( H_0 \subset G_0 \) réalisant le minimum donnant \( \Theta_0 \).}}
21. 21~Û Montrer que l’espérance \( \mathbb{E}\left((X_n^0)^2\right) \) vérifie~:\\
\( \mathbb{E}\left((X_n^0)^2\right) = \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 \llbracket 0, s_0 \rrbracket \), on note~:\\
\( S_k = \sum_{(H,H’) \in \mathcal{C}_0^2,\, |S_H \cap S_{H’}| = k} \mathbb{P}(H \cup H’ \subset G) \).
22. 22~Û Montrer que \( 0 \leq \dfrac{\operatorname{Var}(X_n^0)}{(\mathbb{E}(X_n^0))^2} \).
23. 23~Û Soit \( k \in \llbracket 1, s_0 \rrbracket \) ; montrer que~:\\
\( S_k \leq \sum_{H \in \mathcal{C}_0} \binom{s_0}{k} \binom{n-s_0}{s_0 – k} c_0 p_n^{2a_0 – \Theta_0 k} \).
24. 24~Û Justifier que pour tous entiers naturels \( q \) et \( r \) vérifiant \( 1 \leq q \leq r \), on a~:\\
\( \binom{r}{q} r^{r-q} \geq \dfrac{1}{q!}\binom{r-1}{q}^{q} \).\\
et en déduire que pour \( k \in \llbracket 1, s_0 \rrbracket \), on a \( S_k = o((\mathbb{E}(X_n^0))^2) \) lorsque \( n \) tend vers \( +\infty \).
25. 25~Û Montrer que \( \lim_{n \to +\infty} \dfrac{\operatorname{Var}(X_n^0)}{(\mathbb{E}(X_n^0))^2} = 0 \) où \( \operatorname{Var}(X_n^0) \) désigne la variance de \( X_n^0 \).}
26. 26~Û Montrer alors que la suite \( (n^{-\Theta_0})_{n \geq 2} \) est une fonction de seuil pour la propriété \( \mathcal{P}_n \).
27. 27~Û Retrouver le résultat de la question 16~Û 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.}