Le théorème d’Alon-Friedman et une généralisation

Jeudi 8 mars 14:00-15:00 - Simon Coste - Université Paris Diderot - Paris 7

Résumé : Dans cet exposé, on s’intéressera au spectre de grands graphes aléatoires d-réguliers. Lorsque la taille d’un tel graphe G tend vers l’infini, le graphe converge vers le réseau de Bethe B et la mesure spectrale de G converge vers celle de B, qui est connue : c’est la loi de Kesten-McKay, supportée par l’intervalle [-2sqrt(d-1), +2sqrt(d-1)]. Cependant, cette convergence est globale et n’apporte pas d’informations sur le comportement de certaines valeurs propres particulières de G. En particulier, la deuxième valeur propre est d’importance capitale puisqu’elle gouverne la vitesse de convergence de la marche aléatoire simple sur G vers sa loi stationnaire.
La borne classique d’Alon-Boppana dit que cette deuxième valeur propre est plus grande que 2 sqrt(d-1) ; cependant, en 1986, Alon a conjecturé que la plupart des graphes d-réguliers avaient une deuxième valeur propre très proche de cette borne 2 sqrt (d-1). Cette conjecture s’est révélée très difficile et ne fut démontrée qu’en 2005. On présentera ce résultat ainsi qu’une généralisation à des graphes non-réguliers dirigés.

Le théorème d’Alon-Friedman et une généralisation  Version PDF