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


  • Tuesdays 10:20-11:50
  • Wednesdays 15:00-16:30
  • Thursdays 15:00-16:30
  • Office hours:


    Problem Set

    Lecture plan

    Week 1: connectivity, cuts, and spectral graph theory

    Week 2: random matrix theory, matrix perturbation theory, and spectral algorithms for random graphs

    Week 3: other matrix norms and semidefinite programming algorithms

    Week 4: spectra of graphs, random walks, and other random processes