Spectral Graph Theory, Fall 2009
Applied Mathematics 561/ Computer Science 662
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
The topics for this year's course will include:
The work for the course will consist of approximately 6 problem sets.
- 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
- 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
- Eigenvalues of planar graphs.
- The Colin de Verdière number of a graph.
- Spectral theory for directed graphs.
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