Les graphes expandeurs sont des graphes creux mais fortement connexes. Ils peuvent se substituer aux graphes denses ou même aux graphes complets dans beaucoup d’applications, et ainsi permettre une réduction de complexité de calcul ou d’aléa. Ils jouent un rôle clé dans plusieurs domaines de l’informatique fondamentale, notamment dans la dérandomisation et le pseudo-aléa.

Dans cet exposé nous présenterons les graphes expandeurs, leur(s) définition(s), quelques lemmes structurels fondamentaux, et quelques exemples de leur utilisation dans la dérandomisation. Nous esquisserons également la construction basée sur le produit zigzag.