Télécharger le corrigé partiel
La deuxième composition 2024 du concours Mines-Ponts MP/MPI portait sur une la théorie spectrale des graphes, c’est-à-dire sur des propriétés algébriques des matrices d’adjacence, ainsi que sur des phénomènes de seuils sur des graphes aléatoires. Il s’agit d’un sujet relativement atypique présentant des difficultés techniques non négligeables. NB : en l’état, le corrigé mis en ligne s’arrête aux premières questions de la troisième et dernière partie.
La première partie du problème explore des propriétés algébriques des matrices d’adjacence des graphes simples non orientés. Concernant les graphes, cette partie ne nécessite aucune connaissances au-delà des définitions, au programme de première année d’ITC, rappelées dans le sujet. D’un point de vue algébrique, les outils utilisés sont ceux de la réduction algébrique, avec un accent particulier sur l’étude du polynôme caractéristique des matrices d’adjacence. La dernière question de la première partie introduit un espace probabilisé lié à des graphes aléatoires.
La deuxième partie étudie la probabilité asymptotique, pour un très grand graphe aléatoire, de posséder ou non une arête et établit un phénomène de seuil : pour un graphe à n sommets, si la probabilité pour chacune des arêtes d’être présente dans le graphe aléatoire est négligeable devant 1/n², alors asymptotiquement on peut assurer que le graphe ne possèdera pas d’arêtes. A l’inverse, si cette probabilité est prépondérante devant 1/n², alors on peut assurer que le graphe possèdera au moins une arête. Cette partie, relativement courte, fait appel au formalisme des variables aléatoires finies et à des raisonnements combinatoires.
La troisième et dernière partie propose d’étudier un phénomène de seuil plus subtil relatif à la probabilité pour un grand graphe aléatoire de contenir une copie d’un plus petit graphe. Nettement plus technique, cette partie n’est pour l’instant pas traitée dans ce corrigé. J’y reviendrai peut-être plus tard, mais pour l’heure je dois me consacrer à la préparation des épreuves orales de mes étudiants…
Et toujours faute de temps, je n’ai pas tapé le sujet. Il vous faudra donc le chercher ailleurs…
Comme d’habitude, je rappelle que je n’ai aucun lien avec les jurys de concours et que ce corrigé n’est en rien officiel. Il contient très probablement des coquilles, maladresses ou erreurs. N’hésitez pas à me le signaler le cas échéant.