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.
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.
@article{AFST_2015_6_24_4_801_0,
author = {Gharan, Shayan Oveis},
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},
pages = {801--815},
publisher = {Universit\'e Paul Sabatier, Institut de math\'ematiques},
address = {Toulouse},
volume = {Ser. 6, 24},
number = {4},
year = {2015},
doi = {10.5802/afst.1465},
mrnumber = {3434257},
zbl = {1349.05208},
language = {en},
url = {http://www.numdam.org/articles/10.5802/afst.1465/}
}
TY - JOUR AU - Gharan, Shayan Oveis TI - Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2015 SP - 801 EP - 815 VL - 24 IS - 4 PB - Université Paul Sabatier, Institut de mathématiques PP - Toulouse UR - http://www.numdam.org/articles/10.5802/afst.1465/ DO - 10.5802/afst.1465 LA - en ID - AFST_2015_6_24_4_801_0 ER -
%0 Journal Article %A Gharan, Shayan Oveis %T Spectral Graph Theory via Higher Order Eigenvalues and Applications to the Analysis of Random Walks %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2015 %P 801-815 %V 24 %N 4 %I Université Paul Sabatier, Institut de mathématiques %C Toulouse %U http://www.numdam.org/articles/10.5802/afst.1465/ %R 10.5802/afst.1465 %G en %F 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, 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. doi : 10.5802/afst.1465. http://www.numdam.org/articles/10.5802/afst.1465/
[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
[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 | Zbl
[3] Alon (N.). “Eigenvalues and expanders". In: Combinatorica 6, p. 83-96 (cit. on p. 1, 3) (2 Jan. 1986). | MR | Zbl
[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 | Zbl
[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 | Zbl
[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 | Zbl
[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 | Zbl
[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 | Zbl
[9] Guruswami (V.) and Sinop (A. K.).— “Faster SDP hierarchy solvers for local rounding algorithms". In: FOCS. (cit. on p. 5) (2012). | MR
[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 | Zbl
[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 | Zbl
[13] Louis (A.), Raghavendra (P.), Tetali (P.), and Vempala (S.).— “Many sparse cuts via higher eigenvalues". In: STOC. (cit. on p. 4) (2012). | Zbl
[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 | Zbl
[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
[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
[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 | Zbl
[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 | Zbl
[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 | Zbl
Cité par Sources :
