max planck institut
mpii logo Minerva of the Max Planck Society

Spectral Graph Theory (Winter 2011/12)

Lecturer   Thomas Sauerwald and He Sun



Time Wednesday 14-16, first meeting 19.10.2011
Syllabus PDF
  • For the background knowledge on mathematics and complexity theory, see Preliminaries (Nov. 8)
  • Problem Set 1 is available. The deadline is Nov. 25.
  • Homework 1 was corrected.
  • Problem Set 2 is available. The deadline is Jan. 11
  • Homework 2 was corrected.
  • Problem Set 3 is available. The deadline is Jan. 27.
  • Remarks for the final exam is available, see here.
Room 024 in the MPI building (E1 4)

Prerequisites Basic knowledge of discrete mathematics and linear algebra.  See Preliminaries.

Content The course studies advanced topics in graph theory and their applications in computer science.
  • Algebraic techniques in graph theory
  • Spectra of graphs, second eigenvalue of a graph and its relation to combinatorial properties
  • Randomized algorithms and Markov chains
  • Construction of expander graphs
  • Pseudorandomness theory
Credits You earn 5 Credit Points (LP)
Preliminary Schedule  
No. Date Lecturer Topic Slides/Lecture Notes Reference
1 19.10.2011 He Introduction slides
2 26.10.2011 He Spectra of Graphs Lecture Notes  
3 02.11.2011 He Expander Mixing Lemma Lecture Notes [5]
4 09.11.2011 Thomas Cheeger's Inequality Lecture Notes  
5 16.11.2011   No class    
6 23.11.2011 Thomas Introduction to Markov Chains Lecture Notes  
7 30.11.2011 Thomas Random Walks versus Independent Sampling Lecture Notes  
8 07.12.2011 Thomas Hitting Time and Cover Time of Random Walks Lecture Notes  
9 14.12.2011 He Construction of Expanders Lecture Notes  
10 11.01.2012 He Undirected Connectivity in Log-Space Lecture Notes  
11 18.01.2012 He Pseudorandom Generators Lecture Notes  
12 25.01.2012 Thomas Recap    
  • The final exam will be held in the last week of the semester.
  • You have to get 40% of the homework for the admission to the final exam.
Similar Classes
Main References
  • Fan R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, 1997.
  • S. Horry, N. Linial, and A. Wigderson. Expander Graphs and Their Applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006.
  • C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics 207, Springer
  • D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
Other References
  1. R. Impagliazzo, N. Nisn, and A. Wigderson: Pseudorandomness for network algorithms. In: Proceedings of the 26th STOC, pages 356-364, 1994
  2. L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics, pages 1-46, 1993.
  3. O. Reingold, S. Vadhan, and A. Wigderson: Entropy waves, the Zig-Zag product, and new constant-degree expanders. The Annals of Mathematics, 155(1):157-187.
  4. O. Reingold. Undirected ST-connectivity in Log-space. Journal of ACM, 55(4), 2008.
  5. P. Sarnak. Selberg's Eigenvalue Conjecture. Notices of the AMS. 42(11):1272-1277, 1995
  6. J. R. Shewchuck. Ladies and Gentleman, Allow me to Introduce Spectral and Isoperimetric Graph Partitioning. 2011.PDF
Search MPII (type ? for help)