Spring 2023 — 41000 Graph Theory
This course is about algorithms and analytical techniques to study networks, particularly
random networks sampled from interesting generative models. The course assumes basic
familiarity with directed and undirected graphs, the notions of connectivity and strong
connectivity, and of BFS and DFS visits of graphs and their properties.
We will study applications of linear algebraic techniques to graphs, various results about
spectral graph theory and spectral algorithms, and we will analyze spectral algorithms for
community detection in the stochastic block model and to find planted cliques in random
graphs.
General information
Instructor: Luca Trevisan
Lectures: Wednesdays and Thursdays, 14:45-16:15, classroom 4B, Via Sarfatti 25, 4th floor
Office hours: Wednesdays, 17:00-18:00, office 3-E1-14, Via Roentgen 1
Lecture notes
Notes will be posted after each lecture (they will be similar to last year's notes)
Lecture plan
- 2022-02-01.
Laplacian matrix of an undirected graphs, eigenvalues of Laplacian and connectivity.
Readings: [Linear Algebra Review] and [Notes on Lecture 1]
- 2022-02-02.
Spectral algorithms for graph partitioning and their analysis.
Readings: [Notes for Lecture 2]
- no lecture on February 8
- 2022-02-09.
Proof of Cheeger's inequality.
Readings: [Notes for Lecture 3]
- 2022-02-14, 16:30-18:00 (note unusual day and time).
Spectrum of the adjacency matrix of random graphs, Matrix Chernoff bounds, applications.
Readings: [Notes for Lecture 4]
We also discussed Cheeger's inequality in manifolds and Buser's inequality: you can find an informal treatment [here], [here], and [here].
- 2022-02-15.
Bounding the operator norm of a random matrix: epsilon-nets and trace methods.
Readings: [Notes for Lecture 5]
- 2022-02-16.
Spectral algorithms for finding planted cliques in random graphs.
Readings: [Notes for Lecture 6]
- 2022-02-22.
More on community detection, and an introduction to Semidefinite programming.
Readings: [Notes for Lecture 7]
- 2022-02-23.
Grothendieck inequality, and SDP for approximate community detection in the stochastic block model.
Readings: [Notes for Lecture 8]
- 2022-03-01.
SDP for exact community detection in the stochastic block model.
Readings: [Notes for Lecture 9]
- 2022-03-02.
SDP for planted clique and a study of robustness.
Readings: [Notes for Lecture 10]
- 2022-03-08.
Eigenvalues and eigenvectors of Cayley graphs.
- 2022-03-09.
More on eigenvalues and eigenvectors of Cayley graphs.