Logo Université Pierre et Marie Curie
Logo Université Denis Diderot
Logo LPMA

Groupe de Travail des Thésards

du Laboratoire de Probabilités et Modèles Aléatoires
des Universités Pierre et Marie Curie
et Denis Diderot

Site Jussieu : 4 place Jussieu 75005 Paris, Métro Jussieu
Site Sophie Germain : Bâtiment Sophie Germain, Avenue de France 75013 Paris (Plan)

Logo du GTT

Un nouveau site est en préparation.

Rendez-vous le mercredi à 17h00
en salle Paul Lévy à Jussieu (barre 16-26, salle 113)
en salle 2015 à Sophie Germain

Responsables : Carlo Bellingeri, Yann Chiffaudel, Henri Elad-Altman, Michel Pain

Prochain exposé

8 février 2017 : Simon Coste (Paris 7) en salle Paul Lévy à Jussieu.

Graphes expanseurs et théorème d'Alon-Friedman

Les graphes expanseurs sont des graphes réguliers qui ont peu d'arêtes et qui sont très bien connectés. Ils occupent une place importante dans l'ingénierie des réseaux. Il se trouve que les propriétés d'expansion des graphes réguliers sont reliées à la deuxième plus grande valeur propre lambda_2 de leur matrice d'adjacence : plus celle-ci est petite, plus le graphe est un bon expanseur. Or, lambda_2 ne peut pas être trop petite (c'est la borne d'Alon-Boppana) : la question de savoir s'il existe des graphes tels que lambda_2 est minimale est une question difficile. Les constructions explicites de tels graphes, appelés graphes de Ramanujan, sont rares. Cependant, Alon a conjecturé en 1986 qu'un graphe pris au hasard parmi tous les grands graphes réguliers est presque un graphe de Ramanujan. Nous présenterons les bases de la théorie des graphes expanseurs, puis nous expliquerons pourquoi les méthodes classiques (en particulier, la méthode de la trace pour les matrices aléatoires) sont inefficaces pour démontrer cette conjecture. Enfin, nous présenterons rapidement les idées qui ont abouti à sa résolution, et des généralisations à des graphes orientés.

Liste des exposés passés ou à venir