Yufei Zhao: Graph Theory and Additive Combinatorics

1st September, 2019

This is a 26-lecture course, with each lecture being about 60-90 minutes, given at MIT in person by Yufei Zhao. It is a graduate lecture course in graphs and additive combinatorics.

This course examines classical and modern developments in graph theory and additive combinatorics, with a focus on topics and themes that connect the two subjects. The course also introduces students to current research topics and open problems.

  1. A bridge between graph theory and additive combinatorics
  2. Forbidding a subgraph I: Mantel’s theorem and Turán’s theorem
  3. Forbidding a subgraph II: Complete bipartite subgraph
  4. Forbidding a subgraph III: Algebraic constructions
  5. Forbidding a subgraph IV: Dependent random choice
  6. Szemerédi’s graph regularity lemma I: Statement and proof
  7. Szemerédi’s graph regularity lemma II: Triangle removal lemma
  8. Szemerédi’s graph regularity lemma III: Further applications
  9. Szemerédi’s graph regularity lemma IV: Induced removal lemma
  10. Szemerédi’s graph regularity lemma V: Hypergraph removal and spectral proof
  11. Pseudorandom graphs I: Quasirandomness
  12. Pseudorandom graphs II: Second eigenvalue
  13. Sparse regularity and the Green-Tao theorem
  14. Graph limits I: Introduction
  15. Graph limits II: Regularity and counting
  16. Graph limits III: Compactness and applications
  17. Graph limits IV: Inequalities between subgraph densities
  18. Roth’s theorem I: Fourier analytic proof over finite field
  19. Roth’s theorem II: Fourier analytic proof in the integers
  20. Roth’s theorem III: Polynomial method and arithmetic regularity
  21. Structure of set addition I: Introduction to Freiman’s theorem
  22. Structure of set addition II: Groups of bounded exponent and modelling lemma
  23. Structure of set addition III: Bogolyubov’s lemma and the geometry of numbers
  24. Structure of set addition IV: Proof of Freiman’s theorem
  25. Structure of set addition V: Additive energy and Balog-Szemerédi-Gowers theorem
  26. Sum-product problem and incidence geometry

These videos are of a lecture course by Yufei Zhao at the Massachusetts Institute of Technology in 2019, and made available as part of its OpenCourseWare initiative. The website for the course may be found here.