CS 598: Spectral Graph Theory

Spring 2012

Instructor: Alexandra Kolla
Wed-Fri 11:00-12:15
SC 1103
Office Hours: By appointment.
(Please send me an email to set up a meeting).


  • No class on Friday 3/16!
  • We will be having a reading group on Mondays, at 11:15 am in Room 3401 Siebel. We start on Monday, March 12.


    Homework policy: you can work in groups of 2-3, but each one of you has to submit an individual write-up.
    Please give credit wherever credit is due (collaborators, online sources...).
    Some of the solutions to the problems might be available online, I advise against looking them up.

  • HW 1 - (new deadline) due 03/14/2012.

    Useful Books and Lecture Notes

  • Algebraic Graph Theory, by Chris Godsil and Gordon Royle.
  • Spectra of Graphs: Theory and Applications. by Dragos M. Cvetkovic, Michael Doob, Horst Sachs.
  • Randomized algorithms by Raghavan and Motwani.
  • Probability and Computing, by Michael Mitzenmacher, Eli Upfal.
  • Spectral Graph Theory, Lecture Notes. by Dan Spielman.
  • An Algorithmist's Toolkit, Lecture Notes. by Johnathan Kelner.


    Date Topics Reading
    Lecture 1:
    January 18
    Introduction to Graphs, Spectra and Random Walks, Walking on Grids and Lines. Sariel's notes on random walks
    Lecture 2:
    January 20
    Random Walks and 2SAT, Markov Chains Sariel's notes on random walks
    Lecture 3:
    January 25
    Random Walks on Graphs,Hitting time, Commute time, Cover time, Random Walks and Electrical Networks. Sariel's notes on random walks
    Lecture 4:
    January 27
    More on Cover time, Graph Connectivity, Start Graphs and Eigenvalues. Sariel's notes on random walks
    Lecture 5:
    February 1
    Erdos-Renyi Random Graphs. Dan Spielman's notes on random graphs
    Lecture 6:
    February 3
    Galton-Watson Process, Giant Component. Dan Spielman's notes on random graphs
    Lecture 7:
    February 10
    The Laplacian. class slides
    Lecture 8:
    February 15
    Extremal Eigenvalues and Eigenvectors of the Laplacian and the Adjacency Matrix. class slides
    Also see Section 3.3 of These Lecture Notes
    Lecture 9:
    February 17
    The Other Eigenvectors and Eigenvalues of the Laplacian. class slides
    Lecture 10:
    February 22
    Graphic Inequalities and Lowerbounds on the Second Laplacian Eigenvalue. class slides
    Lecture 11:
    February 24
    Graph Cutting and Cheeger's Inequality. class slides
    Also see These Notes and These Notes
    Lecture 12:
    March 7
    Relaxations, Duality and the Connection with lambda_2. class slides
    Also see chapters 4 and 5 from This Book
    Lecture 13:
    March 9
    The Unique Games Conjecture and SDP Duality. class slides
    Lecture 14:
    March 14
    Random Walks and Eigenvalues. class slides
    Lecture 15:
    March 28
    Pseudorandom Generators and Random Walks on Expanders. class slides
    Lecture 16:
    March 30
    Expander Graphs and Their Properties. class slides
    Lecture 17:
    April 4
    Error-Correcting Codes. class slides
    Lecture 18:
    April 6
    Expander Codes. class slides
    Lecture 19:
    April 11
    Cayley Graphs. class slides
    Lecture 20:
    April 13
    Construction of Expanders. See These lecture notes
    Lecture 21:
    April 18
    Diameter and Second Eigenvalue. See These lecture notes