Graph Theory and Additive Combinatorics
Offered By: Massachusetts Institute of Technology via MIT OpenCourseWare
Course Description
Overview
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
- 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
Tags
Related Courses
Graph Theory and Additive CombinatoricsMassachusetts Institute of Technology via MIT OpenCourseWare Associativity Testing - Ben Green
Institute for Advanced Study via YouTube Analysis of Boolean Functions at CMU - Additive Combinatorics
Ryan O'Donnell via YouTube The Selberg Sieve and Large Sieve - Lecture 1
International Centre for Theoretical Sciences via YouTube The Selberg Sieve - Lecture 1
International Centre for Theoretical Sciences via YouTube