Introduction aux graphes expanseurs : définitions et premières propriétés, 1er exposé

Orateur: Matthieu FRADELIZI
Type: Groupe de travail analyse, probabilités et statistique
Site: UPEM
Salle: 3B081
Date de début: 04/11/2014 - 10:30
Date de fin: 04/11/2014 - 10:30

Cet exposé est le premier d’une série consacrée aux graphes expanseurs, un des thèmes principaux de notre groupe de travail cette année. Le but général est de présenter les suites de graphes expanseurs, leurs propriétés, démontrer leur existence, de façon probabiliste et comme graphes de Cayley et enfin leurs différentes utilisations, en particulier en informatique. Au cours de ce premier exposé, je présenterai les relations entre isopérimétrie, trou spectral et convergence de la marche aléatoire standard dans les graphes et j’en déduirai l’équivalence de différentes définition de graphes expanseurs. Les références utilisées pour préparer cet exposé et sans doute les suivants sont : - « Expansion in finite simple groups of Lie types » de Tao (http://terrytao.files.wordpress.com/2013/11/expander-book.pdf) - « Discrete groups, expanding graphs and invariant measures » de Lubotzky - « Expander graphs and their applications » de Hoory, Linial et Wigderson (www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf)