Site menu:

Lecture notes

week 1 (Jan 9): course introduction [pdf, one] (updated Jan 11 3:30pm)
  • course overview
  • background in linear algebra
  • graph spectrum
week 2 (Jan 16): second eigenvalue [pdf, one]
  • Rayleigh quotient, Courant Fischer theorem, first eigenvalue
  • Cheeger's inequality: proofs, examples, related results
week 3 (Jan 31): last eigenvalue [pdf, one]
  • maximum cut, spectral, SDP
  • independent set, Hoffman's bound, extremal combinatorics
week 4 (Feb 7): more eigenvalues [pdf, one]
  • small-set expansion
  • multi-way spectral partitioning