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