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)