Advanced topics in Graph Theory

Course description

A mandatory course for CS graduate students.

The course covers a wide range of topics pertaining to the role of graphs in Computer Science & Data Science. The course takes aim at various aspects of the following topics where the specific topic selection may vary from one course instance to the next.

  • Spectral graph theory
  • Expansion in graphs
  • Random walks
  • Clustering and partitioning
  • Spanners
  • Graph Sparsifiers
  • Extremal graph theory & extremal combinatorics
  • Additive combinatorics
  • Ramsey theory
  • Random graphs & matrices
  • Complex networks
  • VC dimension of hypergraphs
  • Discrepancy
  • Property testing
  • Computational learning and neural networks

Lecture notes

The course follows these notes.

Please contact me if you find any mistakes, oversights, typos etc.

Logistic information

The course entails 26 two-hour lectures conducted through bi-weekly meetings.

Final grade composition:

  • 50% assignments
  • 50% final exam

In order to pass one has to:

  • Get a passing grade (≥ 65) in the final exam. 
  • After passing the final exam, score ≥ 65 in the final grade.

Bonus points can be obtained through:

  • Giving a lecture presentation in a departmental seminar regarding a topic related to the course.
  • Making progress on specific challenge/research problems.
  • Significant programming projects related to the course.

Those of you who are in pursuit of the bonus that can be attained from programming, here are some notes that may aid you on your way.

  1. Python lecture notes
  2. R lecture notes

We do not cover these notes in class.

Lecture Slides

  1. Some linear algebra prerequisites (rank-nullity theorem) | Slides
  2. Incidence matrices | Slides
  3. Prerequisites concerning eigenvalues | Slides
  4. Spectrum of a graph (adjacency matrix) | Slides
  5. The spectrum of Kn | Slides
  6. Projections | Slides
  7. Spectral Theorem | Slides
  8. Symmetric matrices | Slides
  9. Rayleigh’s principle | Slides
  10.  Closed walks and degree regularity | Slides
  11. The Perron-Frobenius Theorem | Slides
  12. The Courant-Fischer Theorem | Slides
  13. Cauchy’s interlacing theorem | Slides
  14. The Hoffman bound | Slides
  15. Spectral bounds for the chromatic number | Slides
  16. The Laplacian of a graph | Slides
  17. Graph connectivity via the Laplacian | Slides
  18. The normalised Laplacian | Slides
  19. Godsil-Newman Theorem (Hoffman bound revisited) | Slides
  20. Alon-Chang theorem (expander mixing lemma) | Slides
  21. Tanner’s theorem | Slides
  22. Existence of bipartite expanders | Slides
  23. Equivalence of spectral and vertex expansion | Slides
  24. Cheeger’s inequalities (edge expansion) | Slides
  25. Singular value decomposition (SVD) | Slides
  26. Best fit k-dimensional subspace | Slides
  27. Low rank approximations | Slides
  28. Principle Component Analysis (PCA) | Slides
  29. K-means via spectral clustering | Slides
  30. Random walks and connectivity | Slides
  31. Probability amplification via random walks on expanders | Slides
  32. The inequalities of Markov, Chebyshev, and Chernoff (split slides due to size)
    1. Monotone properties | Slides
    2. Markov, Chebyshev & thresholds | Slides
    3. Chernoff |Slides
  33. Graphs with high girth and high chromatic number | Slides
  34. Hadwiger’s conjecture for dense random graphs | Slides

Assignments

  1. Assignment 1 | Deadline: 02.04.2020 by 16:00 (after extension) | Link
  2. Assignment 2 | Deadline: 24.04.2020 by 18:00 (after extension) | Link
  3. Assignment 3 | Deadline: 24.04.2020 by 18:00 (after extension) | Link
  4. Assignment 4 | Deadline: 04.05.2020 by 18:00 (after extension) | Link
  5. Assignment 5 | Deadline: 10.05.2020 by 18:00 (after extension) | Link
  6. Assignment 6 | Deadline: 07.06.2020 by 18:00 (after extension) | Link

Additional resources

  1. Introductory lectures on spectral graph theory by Luca Trevisan at Berkley’s Simon Institute:
    1. Lecture 1
    2. Lecture 2
    3. Lecture 3
  2. Bojan Mohar’s mini-course on graphs and their eigenvalues Simon Fraser University. This is an 8 lecture series.
  3. Daniel Spielman’s “miracles of algebraic graph theory” lecture, Yale University.