max planck institut
mpii logo Minerva of the Max Planck Society

Doctoral Privatissima: Spectral Graph Theory (Winter 2013/2014)

Lecturer He Sun  



Date: March 3-14, and March 24-28, 2014
Place: Rotunda of the 3rd floor, Campus E1. 4
Time: 2-4pm, everyday
Notice This Doctoral Privatissima is a block course for three weeks. For more information about Doctoral Privatissima, click HERE.
Credits You earn 6 Credit Points (LP).
Grading Students who register the course need to read one paper from the list below, and give an about 2-hour presentation with detailed analysis.
Prerequisites Basic knowledge of algorithm design and linear algebra.
Content Spectral Graph Theory studies the matrix representations of graphs, and offers many unexpected and beautiful connections between two apparently unrelated branches of mathematics: Algebra and Graph Theory. Due to this connection, various algebraic questions can be reduced to graph problems, and this insights lead to some new techniques in designing graph algorithms.
  • Graphs and Groups.
  • Matrix Theory.
  • Cheeger's Inequality.
  • Paths, Flows, and Routing.
  • Explicit Constructions of Expanders.
  • Spectral Graph Theory on Subgraphs.
Date Topic References
March 4 Eigenvalues and the Laplacian of a graph Chapter 1 of Ref. 1
March 5 Isoperimetric problems Chapter 2 of Ref. 1
March 6 Path, flows, and routing Chapter 4 of Ref. 1
March 10 Eigenvalues and quasi-randomness Chapter 5 of Ref. 1
March 11 Expanders and explicit constructions Chapter 6 of Ref. 1, Ref. 2, and My Old Notes
March 12 Eigenvalues of Symmetric Graphs Chapter 7
March 13 Eigenvalues of subgraphs with boundary conditions Chapter 8
Papers for Presentation
  • Shayan Oveis Gharan, Luca Trevisan: A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM 2013: 303-316.
  • James R. Lee, Shayan Oveis Gharan, Luca Trevisan: Multi-way Spectral Partitioning and Higher-order Cheeger Inequalities. STOC 2012: 1117-1130.
  • Adam Marcus, Daniel Spielman, and Nikhil Srivastava: Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem, 2013.
  • Daniel Spielman, and Nikhil Srivastava: Graph Sparsification by Effective Resistances, SIAM Journal on Computing, 40(6), pages 1913-1926, 2011.
  • Anastasios Zouzias: A Matrix Hyperbolic Cosine Algorithm and Applications. ICALP (1) 2012: 846-858.
Similar Courses
Main References
  • [1] Fan Chung: Spectral Graph Theory, American Mathematical Society, 1997. First four chapters can be downloaded via the link.
  • [2] Omer Reingold, Salil Vadhan and Avi Wigderson. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Annals of Maths. 155:157-187, 2002.
Search MPII (type ? for help)