Graphes aléatoires presque de Ramanujan

by mikael de la salle (CNRS, Université Lyon 1)

Wednesday Oct 2, 2024, 12:00 PM → 12:30 PM Europe/Paris

Fokko du Cloux (Braconnier)

Les graphes de Ramanujan sont des graphes finis réguliers qui ont des propriétés d'expansion optimale. L'origine du nom est que pendant longtemps, la seule preuve de leur existence reposait sur des travaux très profonds de théorie des nombres dûs à Deligne. J'expliquerai une preuve nouvelle et surprenante qu'un graphe choisi au hasard parmi les graphes réguliers à n sommets est presque de Ramanujan avec grande probabilité quand n tend vers l'infini : l'idée est de voir un graphe aléatoire à n sommets comme une fonction de 1/n et de faire un développement de Taylor. Cette preuve, par Chen--Garza-Vargas--Tropp--van Handel, combine 3 ingrédients : un zeste de théorie des représentations, une inégalité des frères Markov sur des polynômes, et une pincée d'analyse fonctionnelle/théorie des distributions.