Spectral Graph Theory, Fall 2012
This is the third 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.
- Isoperimetry, with applications in probability.
- Eigenvalues of random graphs.
- Finding cliques in and partitioning semi-random graphs.
- Testing isomorphism of graphs of bounded eigenvalue multiplicity.
- Constructions of higly symmetric 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 5 or 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.