Catalog

Graph Theory and Additive Combinatorics

Mathematics MIT CC BY-NC-SA 4.0 26 lectures

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. This course was previously numbered 18.217.

Syllabus

  1. 1 Lecture 1: A bridge between graph theory and additive combinatorics
  2. 2 Lecture 2: Forbidding a Subgraph I: Mantel’s Theorem and Turán’s Theorem
  3. 3 Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph
  4. 4 Lecture 4: Forbidding a Subgraph III: Algebraic Constructions
  5. 5 Lecture 5: Forbidding a Subgraph IV: Dependent Random Choice
  6. 6 Lecture 6: Szemerédi’s Graph Regularity Lemma I: Statement and Proof
  7. 7 Lecture 7: Szemerédi’s Graph Regularity Lemma II: Triangle Removal Lemma
  8. 8 Lecture 8: Szemerédi’s Graph Regularity Lemma III: Further Applications
  9. 9 Lecture 9: Szemerédi’s Graph Regularity Lemma IV: Induced Removal Lemma
  10. 10 Lecture 10: Szemerédi’s Graph Regularity Lemma V: Hypergraph Removal and Spectral Proof
  11. 11 Lecture 11: Pseudorandom Graphs I: Quasirandomness
  12. 12 Lecture 12: Pseudorandom Graphs II: Second Eigenvalue
  13. 13 Lecture 13: Sparse Regularity and the Green-Tao Theorem
  14. 14 Lecture 14: Graph Limits I: Introduction
  15. 15 Lecture 15: Graph Limits II: Regularity and Counting
  16. 16 Lecture 16: Graph Limits III: Compactness and Applications
  17. 17 Lecture 17: Graph Limits IV: Inequalities between Subgraph Densities
  18. 18 Lecture 18: Roth’s Theorem I: Fourier Analytic Proof over Finite Field
  19. 19 Lecture 19: Roth’s Theorem II: Fourier Analytic Proof in the Integers
  20. 20 Lecture 20: Roth’s Theorem III: Polynomial Method and Arithmetic Regularity
  21. 21 Lecture 21: Structure of Set Addition I: Introduction to Freiman’s Theorem
  22. 22 Lecture 22: Structure of Set Addition II: Groups of Bounded Exponent and Modeling Lemma
  23. 23 Lecture 23: Structure of Set Addition III: Bogolyubov’s Lemma and the Geometry of Numbers
  24. 24 Lecture 24: Structure of Set Addition IV: Proof of Freiman’s Theorem
  25. 25 Lecture 25: Structure of Set Addition V: Additive Energy and Balog-Szemerédi-Gowers Theorem
  26. 26 Lecture 26: Sum-Product Problem and Incidence Geometry

Course materials