Speaker : | Élie de Panafieu |
Nokia Bell Labs France | |
Date: | 26/02/2018 |
Time: | 10:30 am - 12:00 pm |
Location: | Telecom Paristech, I304 (3rd floor) |
Abstract
Orateur : Élie de Panafieu
La question qui guidera l’exposé est l’étude de la loi limite du
nombre de triangles dans un graphes aléatoire à n sommet et m = O(n)
sommets. C’est aussi un prétexte pour présenter quelques outils de
combinatoire analytique (manipulation de séries génératrices). Les
résultats présentés sont classiques et ont été démontrés par Erdös et
Rényi en 1960 par des techniques probabilistes (méthodes du premier et
du second moment). L’intérêt de la preuve analytique est sa robustesse
: elle s’étend naturellement à des familles de graphes plus complexes,
notamment aux graphes dont la distribution des degrés suit une loi de
puissance (“power-law” ou “scale-free networks” selon les auteurs), et
qui se rencontrent dans de nombreuses applications — mais nous
n’aurons sans doute pas le temps d’aborder ces extensions…