Séminaire Bourbaki

Mylène Maïda — Convergence forte du spectre de permutations aléatoires et graphes presque Ramanujan , d'après C. Bordenave et B. Collins

Europe/Paris
Hermite (IHP)

Hermite

IHP

Description

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.