Spectral Graph Theory, Fall 2015

Applied Mathematics 561/ Computer Science 662

Instructor: Dan Spielman. Office Hours: TBA

Time: M-W 2:30-3:45, in AKW 200 (51 Prospect Street)

Here is the course syllabus.

For alternative treatements of material from this course, I recommend my notes from 2012, 2009, and 2004, as well as the notes from other related courses.

For a sales pitch for the type of material I cover in this course see the notes from my first lecture in 2009.

Lectures:

  1. Sep 2, 2015: Course Introduction
  2. Sep 4, 2015: The Laplacian Matrix and Spectral Graph Drawing
  3. Sept 9, 2015: The Adjacency Matrix and Graph Coloring
  4. Sept 14, 2015: Bounding Eigenvalues
  5. Sept 16, 2015: Rings, Paths, and Cayley Graphs
  6. Sept 21, 2015: Conductance, the Normalized Laplacian, and Cheeger's Inequality
  7. Sept 23, 2015: Resistor Networks
  8. Sept 28, 2015: Resistor Networks
  9. Sept 30, 2015: How to draw a planar graph.
  10. Oct 5, 2015: The spectral gap of planar graphs.
  11. Oct 7, 2015: Random walks and diffusion.
  12. Oct 12, 2015: Pseudo-random generators from random walks on expanders.
  13. Oct 14, 2015: Properties of expander graphs.
  14. Oct 19, 2015: A simple construction of expander graphs.
  15. Oct 26, 2015: Sparsification by random sampling.
  16. Oct 28, 2015: The best sparsifiers.
  17. Nov 2, 2015: Iterative Solvers for Linear Equations.
  18. Nov 4, 2015: The Conjugate Gradient.
  19. Nov 9, 2015: Preconditioning and low stretch spanning trees.
  20. Nov 11, 2015: Fast Laplacian solvers by sparsification.
  21. Nov 16, 2015: Partitioning in block models.
  22. Nov 18, 2015: Expected characteristic polynomials: the finite free convolution.
  23. Nov 30, 2015: Quadrature for the finite free convolution.
  24. Dec 2, 2015: Interlacing polynomials and Ramanujan Graphs.
  25. Dec 7, 2015: The matching polynomial of a graph.
  26. Dec 9, 2015: Ramanujan covers of graphs.

This material is based upon work supported by the National Science Foundation under Grant Nos. 0634957, 0915487, and 1111257. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).