# Spectral Graph Theory, Fall 2015

####
Applied Mathematics 561/ Computer Science 662

Instructor:
Dan Spielman.
Office Hours: Friday, 3:00 - 4:00

Time: M-W 2:30-3:45.
**DL 220**

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:

- Sep 2, 2015:
Course Introduction
. Solutions to exercises are available under "Resources" on ClassesV2.

Here are the Matlab files I used in the lecture:
lap.m,
gplot3.m,
yaleShieldBig.mat, and
dodec.mat.

- Sep 4, 2015:
The Laplacian Matrix and Spectral Graph Drawing.
Solutions to exercises are available under "Resources" on
ClassesV2.
**(PS 1 out)**

- Sept 9, 2015:
The Adjacency Matrix and Graph Coloring

- Sept 14, 2015:
Bounding Eigenvalues

- Sept 16, 2015:
Rings, Paths, and Cayley Graphs

- Sept 21, 2015:
Conductance, the Normalized Laplacian, and Cheeger's Inequality.
**(PS 1 due, PS 2 out)**

- Sept 23, 2015:
Spring and resistor networks

- Sept 28, 2015:
Effective resistance and Schur complements

- Sept 30, 2015:
How to draw a planar graph.

- Oct 5, 2015:
Random walks and diffusion.
**(PS 2 due, PS 3 out)**

- Oct 7, 2015:
Pseudo-random generators from random walks on expanders.

- Oct 12, 2015:
Iterative Solvers for Linear Equations.

- Oct 14, 2015:
The Conjugate Gradient. This will be a guest lecture by Sushant
Sachdeva. I have posted my old notes on the topic.
I also recommend his monograph
Faster Algorithms via Approximation Theory.

- Oct 19, 2015:
Preconditioning and low stretch spanning trees.
**(PS 3 due)**

- Oct 26, 2015:
Properties of expander graphs.
**(PS 4 out)**

- Oct 28, 2015:
A simple construction of expander graphs.

- Nov 2, 2015:
Sparsification by effective resistance random sampling.

- Nov 4, 2015:
Linear sized sparsifiers.

- Nov 9, 2015:
Fast Laplacian solvers by sparsification.

- Nov 11, 2015:
The spectral gap of planar graphs.
**(PS 4 due, PS 5 out)**

- Nov 16, 2015:
Partitioning in block models.

- Nov 18, 2015:
Expected characteristic polynomials.

- Nov 30, 2015:
Quadrature for the finite free convolution.

- Dec 2, 2015:
Interlacing polynomials and Ramanujan Graphs.

- Dec 7, 2015:
The matching polynomial of a graph.
**(PS 5 due)**

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