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