Exposé Bourbaki 1202 : Convergence forte du spectre de permutations aléatoires et graphes presque Ramanujan [d'après Charles Bordenave et Benoît Collins]
Exposé Bourbaki 1202 : Strong convergence of the spectrum of random permutations and almost-Ramanujan graphs [after Charles Bordenave and Benoît Collins]
Anglais
Un graphe fini est dit Ramanujan si sa matrice d'adjacence possède un trou spectral maximal, ce qui lui assure d'excellentes propriétés de graphe expanseur. À partir d'une famille de permutations aléatoires, Bordenave et Collins construisent une suite de graphes aléatoires presque Ramanujan. Cette propriété peut dans ce cas se reformuler en termes de convergence forte en probabilités libres. L'exposé sera l'occasion de présenter les résultats connus de convergence forte et quelques-unes de leurs applications. Nous insisterons par ailleurs sur un outil important de leur preuve, l'opérateur non-backtracking associé à l'opérateur d'adjacence pondéré d'un graphe. Nous expliquerons comment le spectre de ces deux opérateurs est relié et évoquerons son usage pour l'étude des graphes aléatoires.