Time: Friday 12:10 pm - 3:10 pm
Place: Livingston, Lucy Stone Hall (LSH), B267
Instructor: Peng Zhang
Email: pz149@cs.rutgers.edu
Office hours: Wednesday 3 - 4 pm (Hill 444) or by appointment
Course description
You could think of this course as "advanced linear algebra with applications in graph theory." We will explore how eigenvalues and eigenvectors of graphs can help us understand graph structures and design efficient algorithms. We will cover basics in spectral graph theory, graph sparsification, solvers for Laplacian linear equations, interlacing polynomials for Ramanujan graphs and the Kadison-Singer problem.
Prerequisites
You will need knowledge of linear algebra, some familiarity with graphs, and comfort with mathematical proofs.
Reading materials
We will not have a textbook. But I highly recommend:
Spectral and Algebraic Graph Theory, by Daniel Spielman
Very good courses on spectral graph theory:
Spectral graph theory, by Daniel Spielman: http://www.cs.yale.edu/homes/spielman/462/462schedule.html
Spectral graph theory, by Lap Chi Lau: https://cs.uwaterloo.ca/~lapchi/cs860-2019/
Spectral graph theory, by Gary Miller: http://www.cs.cmu.edu/afs/cs/academic/class/15859n-s21/index.html
Assignments
Problem sets (60%): 3 problem sets
Project (25%): team project presentation (last week in class)
Scribe notes (15%)
Participation (5% bonus)
Schedule
Week 1: Introduction, basic spectral graph theory, bounding eigenvalues by the Courant-Fischer TheoremÂ
Week 2: Isoperimetric number, conductance, Cheeger's inequality
Week 3: The zoo of graphs, their eigenvalues and eigenvectors
Week 4: Random walks on graphs
Week 5: Eigenvalues of random graphs
Week 6: Effective resistance, spectral sparsification by random sampling
Week 7: Better spectral sparsification by barrier functions
Week 8: Graph structured systems of linear equations, Gaussian elimination, Nested dissection
Week 9: Iterative methods, conjugate gradient
Week 10: preconditioning, fast Laplacian solvers
Week 11: Bipartite Ramanujan graphs and interlacing polynomials, Part I
Week 12: Bipartite Ramanujan graphs and interlacing polynomials, Part II
Week 13: Kadison-Singer and interlacing polynomials
Week 14: Project presentation