AnnalesÉcoles d'ingénieurs

Mines-Ponts MPI 2024 — Maths 2

Phénomènes de seuil dans les graphes · 18 pages

PDF hébergé hors du site officiel — source : archive officielle (ZIP)

Le sujet étudie d'abord les matrices d'adjacence des graphes : diagonalisabilité, rang, polynôme caractéristique des étoiles et des doubles étoiles grâce à une formule de récurrence. Dans le modèle de graphe aléatoire où chaque arête est présente indépendamment avec probabilité $p_n$ , il établit par les inégalités de Markov et de Bienaymé-Tchebychev (méthode du second moment) des fonctions de seuil : $1/n^2$ pour l'existence d'une arête, puis $n^{-\omega_0}$ pour la présence d'une copie d'un graphe fixé $G_0$ , où $\omega_0$ est le minimum de $s_H/a_H$ sur ses sous-graphes $H$ ayant au moins une arête.

Le sujet, partie par partie

Préambule et Partie I — Quelques propriétés algébriques des matrices d'adjacence p. 2–6

Graphes · Théorème spectral · Déterminants · Groupe symétrique · Matrices remarquables — matrice d'adjacence, polynôme caractéristique d'un graphe, graphe étoile, double étoile, matrices de permutation, rang, développement d'un déterminant

Graphes aléatoires et Partie II — Une première fonction de seuil p. 6–7

Matrices et graphes aléatoires · Inégalités de Markov et de Bienaymé-Tchebychev · Lois de Bernoulli et binomiale · Graphes · Espérance, variance, moments · Espaces probabilisés — graphe aléatoire d'Erdős-Rényi, fonction de seuil, inégalité de Markov, inégalité de Bienaymé-Tchebychev, méthode du second moment

Partie III — Fonction de seuil de la copie d'un graphe p. 8–9

Matrices et graphes aléatoires · Inégalités de Markov et de Bienaymé-Tchebychev · Espérance, variance, moments · Graphes · Coefficients binomiaux · Équivalents et comparaison · Dénombrement de configurations — fonction de seuil, copie d'un sous-graphe, méthode du second moment, variance d'une somme d'indicatrices, étoile à $d$ branches

Dans l'édifice

Matrices d'une application linéaire Espaces de Hilbert et théorème de projection Déterminant d'un endomorphisme Formes multilinéaires alternées Groupe symétrique et signature Variables aléatoires, lois, fonctions de répartition Espérance, variance et inégalités Espaces probabilisés et probabilités conditionnelles Ensembles finis et principe des tiroirs Suites réelles et limites