Overview

Description

COURSE DETAILS:

The course will provide an introduction to algebraic and probabilistic techniques in combinatorics and graph theory. The main topics included will be: Eigenvalues of graphs and their applications, probabilistic methods (first order, second order, Lovasz local lemma), Szemeredi regularity lemma. Some recent developments, including the proof of the Sensitivity conjecture, the use of eigenvalues for equiangular lines, and spectral sparsifiers, will be part of the course.

Note: This course is also offered through PIMS and WDA (Western Dean's Agreement) as an online course. A Zoom link will be shared with registered students.
https://courses.pims.math.ca/

Prerequisites:
Undergraduate course in graph theory
Undergraduate course on (discrete) probability
Linear algebra

Course outline:

Part I
Introduction (warmup application of graph eigenvalues)
Eigenvalue basics (including Perron-Frobenius Theorem)
Eigenvalue interlacing (bounds on the maximum clique and chromatic number)
Wilf's Theorem, proof of sensitivity conjecture
Graph Laplacians (Matrix-tree Theorem, Cheeger inequality)
Random walks, effective resistance
Spectral sparsifiers

Part II
Random graphs, probabilistic method (including Lovasz local lemma)
Quasirandom graphs
Eigenvalues of random graphs (Wigner, Tao-Vu)
Regularity Lemma
Finding regular partitions
Random covers and Ramanujan graphs

Grading

Materials

REQUIRED READING NOTES: