MIT OpenCourseWare

Browse materialsMIT 18.217 · Fall 2019

Graph Theory and Additive Combinatorics

Subjects: Mathematics · Statistics

Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain

Instructor: Prof. Yufei Zhao
Term: Fall 2019
Level: Graduate
What's inside: 26 videos · 1 problem set · 2 lecture notes · 34 other files · 4 web pages
Materials open: Videos here · files on MIT OCW

Start here

Start course: Lecture 1: A bridge between graph theory and additive…Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.217 Graph Theory and Additive Combinatorics, Fall 2019, Prof. Yufei Zhao — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

How this course was organized

What's here, and what isn't

MIT's own materials here did not support a verified, course-wide order, so they are grouped by section instead.

Not included here

4 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely. (3 items)
Referenced in a table, but without MIT's own verified order, so it isn't used to claim a sequence.

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

9 files

Assignments

18.217 F2019 Problem SetPDF Download

Other materials from this course

26 video transcripts

2 images

MIT OpenCourseWare, Prof. Yufei Zhao, 18.217 Graph Theory and Additive Combinatorics, Fall 2019.

License: CC BY-NC-SA 4.0 · Edition: Fall 2019 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Graph Theory and Additive Combinatorics

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Other materials from this course

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