Séance Séminaire

Séminaire de culture générale Mathématique

Graphes expanseurs et propriété (T)

Les graphes expanseurs sont ceux pour lesquels déconnecter une partie des sommets nécessite de retirer un nombre d'arêtes proportionnel au nombre de sommets. De tels graphes ont des applications nombreuses, notamment en informatique et dans la simulation de variables aléatoires. L'existence de tels graphes découle d'arguments probabilistes élémentaires, mais leur construction explicite n'est pas évidente a priori. Une méthode due à Margulis permet d'en obtenir à partir de groupes de type finis dont l'espace des représentations unitaires satisfait une condition étrange nommée propriété (T). Cette méthode peut être raffinée pour obtenir les meilleurs graphes expanseurs, dits de Ramanujan. Le but de l'exposé est de raconter cette histoire à un public non expert.