CS598 Spectral Graph Theory

Spring 2015

Last Homework is out, due May 5.

Here is an UPDATED schedule for the final projects.

Please take a look and email me if you need to change your presentation day or topic. Please allocate 40 minutes for your presentation unless we have discussed otherwise



This course is about spectra of graphs and their multiple uses in mathematics and computer science. Course topics will include: Eigenvalues and eigenvectors of common graphs; random walks on graphs; eigenvalues and the diameter of a graph; eigenvalues, cuts and small set expansion via Cheeger's and generalized Cheeger's inequality; approximations of graphs and sparsification; expander graphs with applications in coding theory and derandomization; graph lifts and eigenvalues; eigenvalues of random graphs; finding cliques in and partitioning semi-random graphs; testing isomorphism of graphs of bounded eigenvalue multiplicity. This course will assume familiarity with graphs and linear algebra. While this background knowledge is elementary, the course will move at a fast pace. This course may be suitable for advanced undergraduates. Undergraduate students who are interested in taking the course are advised to consult with the instructor before registering.


CS473: Algorithms and MATH125: Elementary Linear Algebra, or equivalent.


Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK]


Tuesday 12:30PM - 01:45PM and Thursday 12:30PM - 01:45PM | 1304 SC

Office Hours

After appointment with the intrsuctor


# Date Topic Lecture Slides Reading Material
1 T January 20 Introduction, The Laplacian. Lecture 1
2 R January 22 Extremal Eigenvalues and Eigenvectors of the Laplacian and the Adjacency Matrix. Lecture 2
3 T January 27 The Other Eigenvalues and Eigenvectors of the Laplacian Lecture 3
4 R January 29 Graphic Inequalities and Lowerbounds on the Second Laplacian Eigenvalue Lecture 4
5 T February 3 Graph Cutting and Cheegers Inequality Lecture 5 See also those notes.
6 R February 5 Cheeger's Inequality Contd., Spectral k-Clustering Lecture 6 See this paper
7 T February 10 Random Walks and Eigenvalues Lecture 7
8 R February 12 PRGs and Random Walks on Expanders Lecture 8
9 T February 17 Guest Lecture: Maximal Inequalities on Product Graphs Lecture 9 See this paper, this paper, and this post
10 R February 19 Expander Graphs and their Properties Lecture 10
11 T February 24 Cayley Graphs Lecture 11 See this paper, and this paper Ramanujan graph Construction
12 R February 26 A Construction of Expanders Lecture 12 See also these notes for Zig-Zag Product.
13T March 3 Eigenvalues of Random Graphs (or, Random Graphs are Expanders) Lecture 13 See also this paper on Trace Method , this paper on eigenvalues of random graphs, and these notes on Wigner's Semi-Circle Law.
14R March 5 Spectral Algorithms for Unique GamesLecture 14See also this paper
15T March 10Ramanujan Graphs from 2-LiftsLecture 15See this paper
16R March 12Ramanujan Graphs from 2-Lifts, contd.
17T March 17Effective ResistanceLecture 17
18R March 19Graph Sparsification by Effective ResistancesLecture 18See also this paper
19 T March 24      
20 R March 26      
21T March 31Twice-Ramanujan SparsifiersFinal PresentationsSee this paper
R April 2Preconditioning/ Sum-of-Squares ProofsFinal PresentationsPresentation 1, Presentation 2
23T April 7Codes on GraphsFinal PresentationsSee these slides , this paper and this paper
24R April 9Lossless ExpandersFinal PresentationsSee these slides, this paper , and this paper
25T April 14Spectral Radius of Infinite GraphsFinal PresentationsSee this paper
26R April 16Matrix Bernstein Inequalities, Bounding Spectra of Random GraphsFinal PresentationsSee this paper and this paper
27T April 21Spectral Graph Theory in RoboticsFinal PresentationsSee these slides and this paper
28R April 23Spectral Clustering, Clustering via Random Walks, Clustering via high order Cheeger.Final PresentationsSee this paper, this paper, and this paper
29T April 28Spectral Graph DrawingFinal PresentationsSee these slides and this paper
30R April 30Quantum Random Walks, Consensus LearningFinal PresentationsSee this paper
31T May 5No class!


# Due Reading Material Homework Solutions
1 [pdf], [tex] February 12 Lectures 1-4
[pdf], [tex] March 16  Lectures 5-12 


There will be a total of 2 or 3 homeworks.
They can be turned in in groups of up to 3 students.
Please do not forget to cite your sources.