Spring 2022 — 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:
Tuesdays 10:20-11:50
Wednesdays 15:00-16:30
Thursdays 15:00-16:30
Office hours:
- By appointment (email for an appointment)
Notes
Problem Set
Lecture plan
Week 1: connectivity, cuts, and spectral graph theory
- 2022-02-08, 10:20-11:50
Laplacian matrix of an undirected graphs, eigenvalues of Laplacian and connectivity
Readings: [Handout 0] [Handout 1]
- 2022-02-09, 15:00-16:30
Spectral algorithms for graph partitioning and their analysis
Readings: [Handout 2]
- 2022-02-10, 15:00-16:30
Other connection between Laplacian eigenvalues and combinatorial properties
Readings: [Handout 3]
- Exercises for week 1: [Problem Set 1]
Week 2: random matrix theory, matrix perturbation theory, and spectral algorithms for random graphs
- 2022-02-15, 10:20-11:50
Spectrum of the adjacency matrix of random graphs, Matrix Chernoff bounds, applications
Readings: [Handout 4]
- 2022-02-16, 15:00-16:30
Bounding the operator norm of a random matrix: epsilon-nets and trace methods
Readings: [Handout 5]
- 2022-02-17, 15:00-16:30
Spectral algorithms for finding planted cliques in random graphs
Readings: [Handout 6]
- Exercises for week 2: [Problem Set 2]
Week 3: other matrix norms and semidefinite programming algorithms
- 2022-02-22, 10:20-11:50
More on community detection, and an introduction to Semidefinite programming
Readings: [Handout 7]
- 2022-02-23, 15:00-16:30
Grothendieck inequality, and SDP for approximate community detection in the stochastic block model
Readings: [Handout 8]
- 2022-02-24, 15:00-16:30
SDP for exact community detection in the stochastic block model
Readings: [Handout 9]
Week 4: spectra of graphs, random walks, and other random processes
- 2022-03-01, 10:20-11:50
SDP for planted clique and a study of robustness
Readings: [Handout 10]
- 2022-03-02, 15:00-16:30
Eigenvalues and eigenvectors of Cayley graphs
Readings: [Handout 11]
- 2022-03-03, 15:00-16:30
More on eigenvalues and eigenvectors of Cayley graphs
Readings: same as previous lecture