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.

Lectures:

Office hours:

- By appointment (email for an appointment)

- Linear algebra review
- Introduction
- Fiedler's algorithm and Cheeger's inequalities
- Cheeger's inequalities continued
- Random graphs and random matrices
- Techniques from random matrix theory
- Spectral methods for planted clique
- Spectral methods for SBM and an introduction to Semidefinite Programming
- Grothendieck inequality and approximate community detection in the SBM
- Exact community detection in the SBM
- Semidefinite programming for planted clique
- The spectrum of Abelian Cayley graphs

- 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