# Spectral Graph Theory, Fall 2009

####
Applied Mathematics 561/ Computer Science 662

Instructor:
Dan Spielman.

Teaching Assistant: Andrei Osipov, office hours Monday 10:25-11:25 and
Thursday 11:45-12:45, in AKW 114

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

Recommended book: Algebraic
Graph Theory by Chris Godsil and Gordon Royle

Here is the course announcement.

## Lecture Notes:

- Sept 2, 2009: course introduction (postscript)
- Sept 4, 2009: Introduction to The
Laplacian (postscript)
- Sept 9, 2009: Laplacians and Adjacency
Matrices (postscript)
- Sept 11, 2009: Courant-Fischer and Graph
Coloring (postscript)
- Sept 16, 2009: Other eigenvectors of the
Laplacian (postscript)
- Sept 18, 2009: Graphic Inequalities (postscript)
- Sept 23, 2009: Cheeger's Inequality (postscript)
- Sept 25, 2009: Random Walks on Graphs (postscript)
- Sept 30, 2009: Pseudo-Random Generators
from Random Walks on Expanders (postscript)
- Oct 2, 2009: Properties of Expander
Graphs (postscript)
- Oct 7, 2009: Introduction to
Error-Correcting Codes (postscript)

- Oct 9, 2009: Error-Correcting Codes from
Expanders (postscript)
- Oct 14, 2009: Algebraic Constructions of
Graphs (postscript)
- Oct 16, 2009: The Simplest Construction of
Expanders (postscript)
- Oct 21, 2009: Iterative solvers for linear
equations (postscript)
- Oct 23, 2009: Preconditioning Laplacians by
Low-Stretch Trees (postscript)
- Oct 28, 2009: Guest lecture by Nikhil Srivastava on Sparsification
- Oct 30, 2009: Guest lecture by Nikhil Srivastava on things Nikhil thinks you should know, that Dan didn't cover.
- Nov 4, 2009: Diameter, Probability, and
Concentration of Measure (postscript)
- Nov 6, 2009: Spectra of Random Graphs (postscript)
- Nov 11, 2009: Spectral Partitioning in the Planted Model (postscript)
- Nov 13, 2009: Testing Isomorphism of Graphs with Distinct Eigenvalues
- Nov 18, 2009: Strongly Regular Graphs
- Nov 20, 2009: Three stories about Strongly Regular Graphs
- Dec 2, 2009: Planar Graphs, part 1
- Dec 4, 2009: Planar Graphs 2, the Colin de Verdiere graph parameter

This material is based upon work supported by the National Science
Foundation under Grant Nos. 0634957 and 0915487.
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).