Bornes géométriques sur les valeurs propres de graphes

par Nalini Anantharaman (Université Paris-Sud- France)

Les videos (au format mp4) de ces cours se trouvent sur la page de N. Anantharaman ici

Résumé : Dans ce cours on parlera du lien entre théorie spectrale et géometrie, dans le cadre simple du laplacien combinatoire sur un graphe fini, ou plus généralement de marches aléatoires sur un graphe fini.
Chapitre 1 : Inégalités de Poincaré et de Cheeger. Il s'agit d'inégalités donnant une borne inférieure sur la première valeur propre du laplacien, en fonctions de quantités géométriques telles que le nombre de chemins passant par une arête, la longueur de ces chemins, le diamètre,...
Dans les 2 chapitres suivants on parle uniquement de graphes réguliers:
Chapitre 2 : Le théorème d'Alon-Boppana. On donne une borne supérieure sur la première valeur propre, en fonction du diamètre. On définit les notions d'expanseurs et de graphes de Ramanujan.
Chapitre 3 : Existence de graphes de Ramanujan bipartis de degré quelconque (d'après Marcus, Spielman, Srivastava).

Références (tous ces articles sont facilement accessibles en ligne) :

• Persi Diaconis, Daniel Stroock, Geometric Bounds for Eigenvalues of Markov Chains, The Annals of Applied Probability, Vol. 1, No. 1. (Feb. 1991), pp. 36-61.
• A. W. Marcus, D. A. Spielman, N. Srivastava, Ramanujan graphs and the solution of the Kadison-Singer problem, Proc. ICM, Vol III (2014), 375-386.
• S. Hoory, N. Linial, A. Widgerson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561.

nb. Ce cours sera donné en différé à raison de quatre fois une heure.