Programme

Les expandeurs ont des liens avec de nombreux domaines: codes correcteurs d'erreur, réseaux de communications, graphes pseudoaléatoires, convergence des chaine de Markov, etude des algorithmes Monte-Carlo, ... Nous proposons lors de cette journée d'aborder la théorie des expandeurs ainsi que certains liens avec d'autres domaines.

Voici le programme des journées. L'idée générale est d'introduire les expandeurs, de voir quelques exemples et quelques applications. Enfin nous terminerons par une session de problèmes.
Nous avons rédigé un petit texte correspondant aux deux premiers exposés introductifs.

9h00--9h30	Accueil
9h30--10h45	Introduction aux expandeurs -- S. Thomassé Définitions, les valeurs propres et le facteur d'expansion, graphes de Ramanujan. Cf les surveys de Ram Murty et de S. Hoory, N. Linial and A. Wigderson
11h--11h50	Sommet-expandeurs - Marches aléatoires et expandeurs. -- F. Havet Voir le chapitre 9 du livre de B.Chazelle Discrepency method. Pour une introduction sur les marches aleatoires lire le papier de Lovasz
11h55--12h30	Applications aux réseaux de télécommunications -- F. Giroire Voir cet article et celui-la
12h30--14h	Repas
14h--15h15	Exemples d'expandeurs: graphes de Cayley; produit Zig-Zag -- O. Amini Voir l' article de O. Reingoldd, S. Vadhan et A. Wigderson
15h30--16h15	Expandeurs et graphes pseudo-aléatoires -- F. Huc Voir l'article de Krivelevich et Sudakov
16h15--17h	Sessions de problèmes

Pour toutes suggestions ou questions concernant cette journée, veuillez contacter Frédéric Havet.