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
- Graph Sparsifiers
- Extremal graph theory & extremal combinatorics
- Additive combinatorics
- Ramsey theory
- Random graphs & matrices
- Complex networks
- VC dimension of hypergraphs
- Property testing
- Computational learning and neural networks
The course follows these notes.
Please contact me if you find any mistakes, oversights, typos etc.
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.
We do not cover these notes in class.
- Some linear algebra prerequisites (rank-nullity theorem) | Slides
- Incidence matrices | Slides
- Prerequisites concerning eigenvalues | Slides
- Spectrum of a graph (adjacency matrix) | Slides
- The spectrum of Kn | Slides
- Projections | Slides
- Spectral Theorem | Slides
- Symmetric matrices | Slides
- Rayleigh’s principle | Slides
- Closed walks and degree regularity | Slides
- The Perron-Frobenius Theorem | Slides
- The Courant-Fischer Theorem | Slides
- Cauchy’s interlacing theorem | Slides
- The Hoffman bound | Slides
- Spectral bounds for the chromatic number | Slides
- The Laplacian of a graph | Slides
- Graph connectivity via the Laplacian | Slides
- The normalised Laplacian | Slides
- Godsil-Newman Theorem (Hoffman bound revisited) | Slides
- Alon-Chang theorem (expander mixing lemma) | Slides
- Tanner’s theorem | Slides
- Existence of bipartite expanders | Slides
- Equivalence of spectral and vertex expansion | Slides
- Cheeger’s inequalities (edge expansion) | Slides
- Singular value decomposition (SVD) | Slides
- Best fit k-dimensional subspace | Slides
- Low rank approximations | Slides
- Principle Component Analysis (PCA) | Slides
- K-means via spectral clustering | Slides
- Random walks and connectivity | Slides
- Probability amplification via random walks on expanders | Slides
- The inequalities of Markov, Chebyshev, and Chernoff (split slides due to size)
- Graphs with high girth and high chromatic number | Slides
- Hadwiger’s conjecture for dense random graphs | Slides
- Assignment 1 | Deadline: 02.04.2020 by 16:00 (after extension) | Link
- Assignment 2 | Deadline: 24.04.2020 by 18:00 (after extension) | Link
- Assignment 3 | Deadline: 24.04.2020 by 18:00 (after extension) | Link
- Assignment 4 | Deadline: 04.05.2020 by 18:00 (after extension) | Link
- Assignment 5 | Deadline: 10.05.2020 by 18:00 (after extension) | Link
- Assignment 6 | Deadline: 07.06.2020 by 18:00 (after extension) | Link
- Introductory lectures on spectral graph theory by Luca Trevisan at Berkley’s Simon Institute:
- Bojan Mohar’s mini-course on graphs and their eigenvalues Simon Fraser University. This is an 8 lecture series.
- Daniel Spielman’s “miracles of algebraic graph theory” lecture, Yale University.