Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks

Gharan, Shayan Oveis¹

¹ University of Washington

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Numéro Spécial : Conférence “Talking Across Fields” du 24 au 28 mars 2014 à l’Institut de Mathématiques de Toulouse, Tome 24 (2015) no. 4, pp. 801-815

Abstract (VO)

A basic goal in the field of spectral theory is to relate eigenvalues of matrices associated to a graph, namely the adjacency matrix, the Laplacian matrix or the random walk matrix, to the combinatorial properties of that graph. Classical results in this area mostly study the properties of first, second or the last eigenvalues of these matrices [2, 3, 4, 21]. In the last several years many of these results are extended and the bounds are improved using higher order eigenvalues. In this short monologue we overview several of these recent advances, and we describe one of the fundamental tools employed in these results, namely, the spectral embedding of graphs.

Résumé

Un objectif primordial de la théorie spectrale est de faire le lien entre les valeurs propres des matrices associées à un graphe, comme la matrice d’adjacence, la matrice du laplacien, ou la matrice de transition de la marche aléatoire, et des propriétés combinatoires de ce graphe. Les résultats classiques dans ce domaine étudient surtout les propriétés de la première, de la seconde ou de la dernière valeur propre de ces matrices [2, 3, 4, 21]. Ces dernières années, beaucoup de ces résultats ont été étendus et les bornes correspondantes améliorées, par le biais des valeurs propres d’ordre supérieur. Dans ce court monologue, nous donnons un aperçu de ces progrès récents et nous décrivons l’un des outils fondamentaux permettant d’y aboutir, le plongement spectral des graphes.

Détail

DOI : 10.5802/afst.1465