Spectral Graph Theory and its Applications

Applied Mathematics 500A

Instructor: Dan Spielman. (in AKW 207a)

T-Th 2:30-3:45 in AKW 500

• Course Announcement

• Lecture 1. Introductory Survey.
  Available in pdf and postscript. Revised 9/3/04 17:00
  Here's what I've written so far, but I am writing more. This contains more than I covered in lecture, and is meant as a survey of some of the most important topics of the course.

  Matlab files for lecture 1:

  • yale.mat
  • yale2.mat
  • airfoil1.mat
  • dodec.txt
  • gcube.mat
  • lsg.mat
  • dcube.m

• Lecture 2. Topics: Many examples of graphs and their Laplacians.
  Available in pdf and postscript.

• Lecture 3. Topics: Lower bounding \lambda_2, and Fiedler's analysis of the eigenvectors of weighted path graphs. Available in pdf and postscript.

• Problem Set 1 is now available in pdf and postscript. (Revised 9/16/04)

• Lecture 4. Topics: Cutting graphs and Cheeger's inequality.
  Available in pdf and postscript.

• Lecture 5. Lambda_2 for planar graphs.
  Available in pdf and postscript.

• Lecture 6. Random walks on expanders.
  Available in pdf and postscript.

• Lecture 7. Convergence of random walks
  Available in pdf and postscript.

• No Class on 9/28/04. Go to the YALE 2004 WORKSHOP on DISCRETE MATHEMATICS and THEORETICAL COMPUTER SCIENCE

• Suggested topics for future lectures, please provide preferences.
  Available in pdf and postscript.

• Lecture 8. Diameter, Doubling, and Applications
  Available in pdf and postscript.

• Lecture 9. Expanders
  Available in pdf and postscript.

• Lecture 10. Expander Codes.
  Available in pdf and postscript.

• Lecture 11. Expander Codes II.
  

• Lecture 12. Algebraic Graphs.
  Available in pdf and postscript.

• Problem Set 2 is now available in pdf and postscript. (10/19/04) Revised 10/29/04

• Lecture 13. Strongly Regular Graphs.
  The material from this lecture was drawn from a lecture that I gave a few years ago.
  The lectures notes are from (11/13/96)

• Lecture 14. Distances in point sets.
  Available in pdf and postscript.

• Lecture 15. Random graphs. (10/26/04)
  Lecture notes are not yet finished.
  The material for this lecture came from Concentration of eigenvalues of random matrices, by Alon, Krivelevich and Vu.

• Lecture 16. Random graphs, II (10/28/04)
  Available in pdf and postscript.

• Lecture 17. Sparsification I (11/2/04)
  Incomplete lecture notes available in pdf and postscript.
  The content of this lecture may be found on pages 29-33 of Nearly-linear time algorithm for ...

• No Lecture on 11/4/04

• Lecture 18. Solving Linear Systems (11/9/04)
  Incomplete lecture notes available in pdf and postscript.
  

• Lecture 19. Preconditioning by augmented trees (11/11/04)
  Incomplete lecture notes available in pdf and postscript.
  

• Lecture 20. Graph Decomposotions (11/18/04)
  Lecture notes available in pdf and postscript.
  

• Lecture 21. Tutte's rubber band embeddings of planar graphs (11/30/04)
  Lecture notes available in pdf and postscript.