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

Description

É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 ...

Informations

• Publié par: Irro
• Nombre de lectures: 38
• Langue: Français

Extrait

Etudedesgraphesale´atoires

Jean-Benoˆıt Rossel

Projet de semestre

Professeur responsable : Thomas Mountford Chaire de Processus stochastiques

6fe´vrier2006

Resum´e ´

Ceprojetdesemestreapourbutd’´etudierquelquesproble`meslie´sauxgraphesale´atoires. C’estunethe´oriequifutinitialementd´eveloppe´epardeuxHongrois,PaulErd¨os(1913− 1996)etAlfre´dR´enyi(1921−1970). Nous allons tout d’abord rappeler quelques fondements delathe´oriedesgraphesetdesprobabilite´s,puispre´senterquelquesre´sultats.Nousnous inte´resseronsparexemple`alaprobabilite´qu’ungrapheale´atoirecontienneunecopied’un graphedonne´,ouencoreaucomportementdecegrapheale´atoirelorsquesonnombrede sommetstendversl’infini.N´eronsenfinunproble`mequin’estpasencorer´esolu`a ous evoqu l’heure actuelle.

Tabledesmati`eres

1 Introduction 1.1 Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2Pre´sentationdesmod`elesdebase......................... 2Outilsmathe´matiques 2.1Lame´thodedesmoments............................. 2.2Lam´ethodedeStein................................ 2.3 Le concept des valeurs critiques . . . . . . . . . . . . . . . . . . . . . . . . . . 3Leprobl`emedel’existenced’unecopied’ungraphedonne´ 3.1 Exemple fondamental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2Lethe´or`emedeBolloba´s.............................. 3.3Casinterm´ediaire.................................. 4 Le probl`me du recouvrement e 4.1 L’enracinement d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2Notationsetth´eore`me............................... 5 Couplages etG-facteurs 5.1Lethe´ore`medeHall................................ 5.2 Etude des couplages parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Quelques mots sur lesG. . . . . . . . . . . . . . . . . . . . . . . . -facteurs . Bibliographie

1

2 2 6 8 8 10 13 15 15 16 18 22 22 23 27 27 29 31 33

Chapitre 1

Introduction

Lanotiondegrapheale´atoireestapparuepourlapremi`erefoisdansunarticled’Erd¨osdat´e de1947.Sonmod`lconsistaita`choisir´equitablementungrapheparmiles2 ( n 2 qseuaphe ) gr e e l’onpeutformer`apartirdensurl’espsebasaitmndoe`elreem,sosecadnE.stemtsertua’oms deprobabilite´(Ω,F,PsposapheesgrouslnettnoitelcΩesbm`l’)tnade´snsommets, la , ou en tribuFustossles-ouseenelbmΩedslte,orpababilit´entientcoPceestd´enfieiedamine`era` que pour toutω∈Ω, on ait P(ω) = 2 − ( 2 n ) .(1.1) Aujourd’huionconside`reessentiellementdeuxmod`elesdegraphesale´atoires,quisontle mod`elebinomialetlemode`leuniforme.Nousallonslespr´esenter`alasuitedequelquesrappels et notations.

1.1 Rappels et notations Th´eoriedesgraphes Ond´efinitungrapheGapdrueexsnmelbset´noesVetE. Le premier est l’ensemble des sommets deGeplomrcniefid´uroP.seteˆrasesediceludestecontlese,rgpaehlietemtnnu ` faudraitencoreconside´rerlafonctiond’incidenceϕ:E→ P 2 (V)qcisoasuiuqahca`eeteˆrae uncoupledesommets.Maisdansceprojetonneconsid´ereraquedesgraphesnonorient´eset simples,etdonconpourrane´gligercettefonctionϕ, car il n’y aura pas de risque de confusion. En effet, pour tous sommetsietjmuxamimuliayruaaarˆete(uneseuletiistsncdi, j). Soit alorsG= (V, Etout´eesilisntutpaehuqle)nurgsetnoresssnoaviunoestitanqco.Lue au long de ce projet : •v G =v(G) =|V|=|V(G)|est le nombre de sommets deG. •e G =e(G) =|E|=|E(G)|sdteeeeltsbmon’dereˆraG, ete G (A, B) est le nombre d’areˆtesdeGauneeyanttime´rtxsnade´A⊆Vet l’autre dansB⊆V. •d(G) =e G /v G est lae´edtisndeG. •m(G) = max H⊆G d(H) est laeal´tmexamidneisdeG. •N(v) =N G (v) ={w∈V|(v, w)∈E}est levoisinage du sommetv. •N(S) =N G (S) = S v∈S N(v)  \Sest le voisinage deS⊆V. •N(v) =N(v)∪ {v}etN(S) =N(S)∪Ssont lesvoisinages closrespectifs devetS. •deg(v) =deg G (v) =|N(v)|etsomms´teldeudegerv. On note aussiδ G = min v∈G deg(v) ledegre´minimaldeG, et Δ G = max v∈G deg(vixamdleedrge´am)leG.

2

•On note parG= (V,P 2 (V)\E) leocehpargeneml´mpeirtadeG. •K n seltgearhppeoss´edantnmetsesomsommetva,snuceˆraeeeterentaqchpaueedir distincts. On l’appellegraphe complet surnsommetsntaireesompl´emetcehpargnoS. alors un graphevideanedt,ps´osndeetmmsolpeD.eteeuqahcsusonucuˆraetemmates K n egndaugela´r´ea`n−1. •Gestbipartil’onsitueprce´eriV=V 1 ∪V 2 , avecV 1 etV 2 non vides et disjoints, et toutearˆetecontientuneextre´mite´dansV 1 et l’autre dansV 2 . •K m,n est le graphe biparti avec|V 1 |=m,|V 2 |=neˆraneete,enutesommettrechaqu deV 1 et chaque sommet deV 2 . C’est ungraphe biparti complet. On appelle´iote`alen branchesle grapheK 1,n . • ∅e,temmosnucuatnataenqu´enscoartpselts´edeposphenegraucunearˆete. •C k nglouruede´isnguecncyeledk, avec donckateˆrteseksommets. •P k urigned´esmeninuhcgneuedolk, avec donckteseterˆak sommets.+ 1 •PourW⊆V, on noteG[W] = (W, E∩ P 2 (W)) lesous-graphe deGinduit parW. •PourF⊆E, on noteG[F] = (V, F) legraphe partiel deGinduit parF. •On dit qu’un grapheG 0 contient une copie induite du grapheGs’il existe un sous-graphe deG 0 qsotiesui`aherpmoG. Et on dira queG 0 contient une copie deGs’il existe un sous-graphe partiel deG 0 e`aorphisomG. •On note enfin aut(G) le nombre d’automorphismes deG. L’ensemble des automorphismes deGest un groupe, dont la loi est la composition d’appli- cations,not´ee◦ecetensembleestuenpalpcitaoibnjitiecdevet,ffene.Ee´euqahcdtneme´lG danslui-meˆme,etdonctoute´le´mentposse`deuninverse.L’identit´efaitofficed’´el´ementneutre, et enfin la composition d’applications est toujours associative. Elle l’est donc en particulier dans cet ensemble. Pour un grapheGpaencilpoitajibnisphesmenftetuaiectivee´u,odnnmoroantuσ:V→V telle que pour toute paire de sommets voisinsietjon aσ(i) voisin deσ(j). Ainsi un automorphisme deGedtecha´esdommequesesvrrpe´edrgleseG. Par exemple, dans la figure 1.1,unautomorphismedugrapheconside´re´doitenvoyerlasommetavers un autre sommet de degr´e3,c’est-a`-direleaou lecissoilibse´txfiedleermmsoetpxuedtnemelage´alyeiitsuEn. b. Et une fois que les sommetsaetbont´et´efixpeuoil´tr’nli,se´uqsulpayulsene’ubisiosep fixer les deux autres. Au final on obtient dans ce cas aut(G) = 4.

Fig.1.1 – Exemple de graphe.

3