logo AFST
Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 24 (2015) no. 4, pp. 801-815.

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.

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.

Published online : 2016-01-21
@article{AFST_2015_6_24_4_801_0,
     author = {Shayan Oveis Gharan},
     title = {Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 24},
     number = {4},
     year = {2015},
     pages = {801-815},
     zbl = {1349.05208},
     mrnumber = {3434257},
     language = {en},
     url={afst.centre-mersenne.org/item/AFST_2015_6_24_4_801_0/}
}
Gharan, Shayan Oveis. Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 24 (2015) no. 4, pp. 801-815. https://afst.centre-mersenne.org/item/AFST_2015_6_24_4_801_0/

[1] Arora (S.), Barak (B.), and Steurer (D.).— “Subexponential Algorithms for Unique Games and Related Problems". In: FOCS. Washington, DC, USA: IEEE Computer Society, p. 563-572. url: http://dx.doi.org/10.1109/FOCS.2010.59 (cit. on p. 4, 5) (2010). | MR 3025231

[2] Alon (N.) and Kahale (N.).— “A spectral technique for coloring random 3-colorable graphs". In: SIAM Journal on Computing 26 (1997), p. 1733-1748 (cit. on p. 1). | MR 1484153 | Zbl 0884.05042

[3] Alon (N.). “Eigenvalues and expanders". In: Combinatorica 6, p. 83-96 (cit. on p. 1, 3) (2 Jan. 1986). | MR 875835 | Zbl 0661.05053

[4] Alon (N.) and Milman (V.).— “Isoperimetric inequalities for graphs, and superconcentrators". In: Journal of Combinatorial Theory, Series B 38.1, p. 73-88 (cit.on p. 1, 3) (Feb. 1985). | MR 782626 | Zbl 0549.05051

[5] Barak (B.), Raghavendra (P.), and Steurer (D.).— “Rounding Semidefinite Programming Hierarchies via Global Correlation". In: FOCS., p. 472-481 (cit. on p. 5) (2011). | MR 2932723 | Zbl 1292.90226

[6] Coulhon (T.), Grigor’yan (A.), and Pittet (C.).— “A geometric approach to on-diagonal heat kernel lower bounds on groups". In: Ann. Inst. Fourier (Grenoble) 51.6, p. 1763-1827. url: http://aif.cedram.org/item?id=AIF_2001__51_6_1763_0 (cit. on p. 6) (2001). | MR 1871289 | Zbl 1137.58307

[7] Dodziuk (J.).— “Difference equations, Isoperimetric Inequality and Transience of Certain Random Walks". In: Transaction of the American Mathematical Society 284.2, p. 787-794 (cit. on p. 3) (1984). | MR 743744 | Zbl 0512.39001

[8] Guruswami (V.) and Sinop (A. K.).— “Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives". In: FOCS. p. 482-491 (cit. on p. 5) (2011). | MR 2932724 | Zbl 1292.90222

[9] Guruswami (V.) and Sinop (A. K.).— “Faster SDP hierarchy solvers for local rounding algorithms". In: FOCS. (cit. on p. 5) (2012). | MR 3186606

[10] Kwok (T. C.), Lau (L. C.), Lee (Y. T.), Oveis Gharan (S.), and Trevisan (L.).— “Improved Cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap". In: STOC. p. 11-20 (cit. on p. 5) (2013). | MR 3210762 | Zbl 1293.05301

[11] Lyons (R.) and Oveis Gharan (S.).— “Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding". submitted. (cit. on p. 6, 9) (2012).

[12] Lee (J. R.), Oveis Gharan (S.), and Trevisan (L.).— “Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities". In: J. ACM 61.6, p. 1117-1130 (cit. on p. 4) (2014). | MR 3293072 | Zbl 1286.05091

[13] Louis (A.), Raghavendra (P.), Tetali (P.), and Vempala (S.).— “Many sparse cuts via higher eigenvalues". In: STOC. (cit. on p. 4) (2012). | Zbl 1286.05095

[14] Miclo (L.).— “On eigenfunctions of Markov processes on trees". In: Probability Theory and Related Fields 142.3-4, p. 561-594 (cit. on p. 4) (2008). | MR 2438701 | Zbl 1149.60059

[15] Miclo (L.).— “On hyperboundedness and spectrum of Markov operators". In: Inventiones mathematicae 200.1, p. 311-343 (cit. on p. 4) (Apr. 2015). | MR 3323580

[16] Ng (A.), Jordan (M.), and Weis (Y.).— “On Spectral Clustering: Analysis and an algorithm". In: NIPS. (cit. on p. 6) (2002).

[17] Oveis Gharan (S.) and Trevisan (L.).— “A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues". CoRR abs/1212.2701. (cit. on p. 5) (2012).

[18] Oveis Gharan (S.) and Trevisan (L.).— “Partitioning into Expanders". In: SODA. p. 1256-1266 (cit. on p. 5) (2014).

[19] Oveis Gharan (S.) and Trevisan (L.).— “A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold-Rank Graphs". In: Theory of Computing 11.9, p. 241-256. url: http://www.theoryofcomputing.org/articles/v011a009 (cit. on p. 5) (2015). | MR 3358452

[20] Simon (B.) and Hëgh-Krohn (R.).— “Hypercontractive semigroups and two dimensional self-coupled Bose fields". In: J. Functional Analysis 9, p. 121-180 (cit. on p. 4) (1972). | MR 293451 | Zbl 0241.47029

[21] Sinclair (A.) and Jerrum (M.).— “Approximate counting, uniform generation and rapidly mixing Markov chains". In: Inf. Comput. 82.1 (July 1989), p. 93-133 (cit. on p. 1). | MR 1003059 | Zbl 0668.05060

[22] Shi (J.) and Malik (J.).— “Normalized Cuts and Image Segmentation". In: IEEE Transactions on Pattern Analysis and Machine Intelligence 22.8, p. 888-905 (cit. on p. 6) (2000).

[23] Wilf (H.).— “The eigenvalues of a graph and its chromatic number". In: J. London Math. Soc. 1, p. 330-332 (cit. on p. 3) (1967). | MR 207593 | Zbl 0144.45202