Etude des graphes aléatoires - Jean-Benoît Rossel

ÉC O L E P O L Y T E C H N I Q U EFÉ DÉR A L E D E L A U S A N N EEtude des graphes al´eatoiresJean-Benoˆıt RosselProjet de semestreProfesseur responsable : Thomas MountfordChaire de Processus stochastiques6 f´evrier 2006R´esum´eCe projet de semestre a pour but d’´etudier quelques probl`emes li´es aux graphes al´eatoires.C’est une th´eorie qui fut initialement d´evelopp´ee par deux Hongrois, Paul Erd¨ os (1913−1996) et Alfr´ed R´enyi (1921− 1970). Nous allons tout d’abord rappeler quelques fondementsde la th´eorie des graphes et des probabilit´es, puis pr´esenter quelques r´esultats. Nous nousint´eresserons par exemple `a la probabilit´e qu’un graphe al´eatoire contienne une copie d’ungraphe donn´e, ou encore au comportement de ce graphe al´eatoire lorsque son nombre desommets tend vers l’infini. Nous ´evoquerons enfin un probl`eme qui n’est pas encore r´esolu a`l’heure actuelle.Table des mati`eres1 Introduction 21.1 Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Pr´esentation des mod`eles de base . . . . . . . . . . . . . . . . . . . . . . . . . 62 Outils math´ematiques 82.1 La m´ethode des moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 La m´ethode de Stein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Le concept des valeurs critiques . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Le probl`eme de l’existence d’une copie d’un graphe donn´e 153.1 ...