Mardi 08 juin 2010 - Alain Valette (Neuchâtel)
Graphes expanseurs et applications
Les expanseurs sont des familles de graphes réguliers, finis, "très connexes" (au sens qu'ils sont difficiles à déconnecter). Depuis leur introduction en 1972, ils ont trouvé des application en informatique théorique (circuits de communication, codes correcteurs d'erreurs, dérandomisation, théorie de la complexité) mais aussi en mathématiques (théorie des graphes, théorie des groupes, topologie en dimension 3, théorie de la mesure). Après avoir discuté 3 définitions équivalentes des expanseurs (combinatoire, spectrale, probabiliste), nous donnerons la première construction explicite d'expanseurs (Margulis 1973), puis une application aux plongements uniformes d'espaces métriques dans un espace de Hilbert (Gromov 2001).
