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).

Announcements

  • 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.

    Homeworks

    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.

    Lectures

    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