# Spectral Graph Theory, Fall 2009

####
Applied Mathematics 561/ Computer Science 662

Instructor:
Dan Spielman.

Time: W-F 2:30-3:45

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

This is the second time I am teaching this course. To get a
feeling for what the class is going to be like, I recommend looking
at
The topics for this year's course will include:

- Eigenvalues and eigenvectors of common graphs: paths, trees,
cliques, grids, products.
- Random walks on graphs.
- Eigenvalues and the diameter of a graph.

- Cheeger's inequality.
- Hoffman's bound on the size of an independent set in a graph.
- Approximations of graphs and sparsification.
- Low-stretch spanning tress and generalized eigenvalues of graphs.

- Expander graphs, with applications in coding theory and
derandomization.
- Eigenvalues of random graphs.
- Finding cliques in and partitioning semi-random graphs.
- Testing isomorphism of graphs of bounded eigenvalue multiplicity.

- Constructions of special graphs: strongly regular graphs and
expanders.
- Eigenvalues of planar graphs.
- The Colin de Verdière number of a graph.
- Spectral theory for directed graphs.

The work for the course will consist of approximately 6 problem sets.

This course will assume familiarity with graphs and linear
algebra. While this background knowledge is

elementary, the course will move at a fast pace. This course may
be suitable for advanced undergraduates.

Undergraduate students who are interested in taking the course are
advised to consult with the instructor

before registering.