# Graph Theory and Additive Combinatorics

- Institution: Massachusetts Institute of Technology
- Department: Mathematics
- Teacher: Prof. Yufei Zhao
- Term: Fall 2023
- Level: Graduate
- Language: English
- Subjects: Mathematics
- Source: [MIT OpenCourseWare](https://ocw.mit.edu/courses/18-225-graph-theory-and-additive-combinatorics-fall-2023/)
- Licence: [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) (Non-commercial use only.)
- Syllabus: [at the source](https://ocw.mit.edu/courses/18-225-graph-theory-and-additive-combinatorics-fall-2023/pages/syllabus/)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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.

## Lectures

1. [Lecture 1: A bridge between graph theory and additive combinatorics](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/f743cd04bee1), 1 h 17 min (Video)
2. [Lecture 2: Forbidding a Subgraph I: Mantel’s Theorem and Turán’s Theorem](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/dbf35d973f23), 1 h 13 min (Video)
3. [Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/146f07afdf6f), 1 h 17 min (Video)
4. [Lecture 4: Forbidding a Subgraph III: Algebraic Constructions](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/db9cf698cfa2), 1 h 20 min (Video)
5. [Lecture 5: Forbidding a Subgraph IV: Dependent Random Choice](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/89454fef0f73), 1 h 20 min (Video)
6. [Lecture 6: Szemerédi’s Graph Regularity Lemma I: Statement and Proof](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/3eb6728b0c8e), 1 h 20 min (Video)
7. [Lecture 7: Szemerédi’s Graph Regularity Lemma II: Triangle Removal Lemma](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/6b17e059db7c), 1 h 15 min (Video)
8. [Lecture 8: Szemerédi’s Graph Regularity Lemma III: Further Applications](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/1fe3680d1afd), 1 h 22 min (Video)
9. [Lecture 9: Szemerédi’s Graph Regularity Lemma IV: Induced Removal Lemma](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/b2cb5f4b7d7a), 1 h 24 min (Video)
10. [Lecture 10: Szemerédi’s Graph Regularity Lemma V: Hypergraph Removal and Spectral Proof](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/875c24cb36ac), 1 h 20 min (Video)
11. [Lecture 11: Pseudorandom Graphs I: Quasirandomness](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/58cb62762836), 1 h 19 min (Video)
12. [Lecture 12: Pseudorandom Graphs II: Second Eigenvalue](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/47bf26a35512), 1 h 20 min (Video)
13. [Lecture 13: Sparse Regularity and the Green-Tao Theorem](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/1e49a6c75fa5), 1 h 20 min (Video)
14. [Lecture 14: Graph Limits I: Introduction](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/965dcbc13c8a), 1 h 18 min (Video)
15. [Lecture 15: Graph Limits II: Regularity and Counting](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/ab76a5215ccb), 1 h 22 min (Video)
16. [Lecture 16: Graph Limits III: Compactness and Applications](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/0f373a9d7eeb), 1 h 20 min (Video)
17. [Lecture 17: Graph Limits IV: Inequalities between Subgraph Densities](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/f94f51ea4a66), 1 h 20 min (Video)
18. [Lecture 18: Roth’s Theorem I: Fourier Analytic Proof over Finite Field](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/bc75f5d3d2d6), 1 h 15 min (Video)
19. [Lecture 19: Roth’s Theorem II: Fourier Analytic Proof in the Integers](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/97f82395788f), 1 h 21 min (Video)
20. [Lecture 20: Roth’s Theorem III: Polynomial Method and Arithmetic Regularity](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/a648fd2d4a8e), 1 h 21 min (Video)
21. [Lecture 21: Structure of Set Addition I: Introduction to Freiman’s Theorem](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/1768e7ea039d), 1 h 15 min (Video)
22. [Lecture 22: Structure of Set Addition II: Groups of Bounded Exponent and Modeling Lemma](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/6360093f64c4), 1 h 20 min (Video)
23. [Lecture 23: Structure of Set Addition III: Bogolyubov’s Lemma and the Geometry of Numbers](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/efda6ff817e2), 1 h 19 min (Video)
24. [Lecture 24: Structure of Set Addition IV: Proof of Freiman’s Theorem](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/18c141219071), 1 h 20 min (Video)
25. [Lecture 25: Structure of Set Addition V: Additive Energy and Balog-Szemerédi-Gowers Theorem](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/9c7911137e59), 1 h 15 min (Video)
26. [Lecture 26: Sum-Product Problem and Incidence Geometry](https://invisiblenetwork.ai/learn/mit/18-225-graph-theory-and-additive-combinatorics-fall-2023/228de929202b), 1 h 15 min (Video)