18.225 Graph Theory and Additive Combinatorics

Fall 2021, MIT, graduate level (Link to the most current version of the course)

Quick links: [Book draft] [Problem set] [Canvas]

Class meetings: Mondays and Wednesdays 2:30–4pm, room 4-153

Instructor: Prof. Yufei Zhao

Graders: Yibo Gao (lead), Milan Haiman, Anqi Li,

Emails and Piazza

Office hours

Course description

The 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.

A foundational result in additive combinatorics is Roth’s theorem, which says that every subset of {1, 2, …, n} without a 3-term arithmetic progression contains o(N) elements. We will see a couple of different proofs of Roth’s theorem: (1) a graph theoretic approach and (2) Roth’s original Fourier analytic approach. A central idea in both approaches is the dichotomy of structure versus pseudorandomness, and it is one of the key themes of the course.

Roth’s theorem laid the groundwork for many important later developments, e.g.,

The course will explore these and related topics, including:

Although the course will be largely divided into two parts (graph theory in the first half and additive combinatorics in the second), we will emphasize the interactions between the two topics and highlight the common themes.

Lecture video recordings from Fall 2019 (may not correspond exactly to the current semester) may be found on MIT OpenCourseWare and YouTube.


Mathematical maturity at the level of a first-year math graduate student. Comfortable with undergraduate real analysis (18.100) and algebra (18.701/3).


Final letter grade cutoffs:

Grades of A and A+ are awarded at my discretion based on overall performance. Solving a significant number of starred problems is a requirement for grades of A and A+ (please don’t ask me what “a significant number” means). Note that for MIT students, ± grade modifiers do not count towards the GPA and do not appear on the external transcript.

Students needing support should consider reaching out to Student Support Services (S3), GradSupport, or Student Disability Services.


  1. W 9/8 A bridge between graph theory and additive combinatorics §0

  2. M 9/13 Forbidding a subgraph: Mantel’s Theorem and Turán’s Theorem §1.1–1.2

  3. W 9/15 Forbidding a subgraph: supersaturation, Kővári–Sós–Turán, Erdős–Stone–Simonovits §1.3–1.5

  4. M 9/20 Forbidding a subgraph: forbidding cycles, dependent random choice, randomized lower bounds constructions §1.6–1.9

  5. W 9/22 Forbidding a subgraph: algebraic and randomized algebraic lower bound constructions §1.10–1.11

  6. M 9/27 Graph regularity: statement and proof §2.1

  7. W 9/29 Graph regularity: triangle counting and removal lemmas, proof of Roth’s theorem §2.2–2.4

  8. M 10/4 Graph regularity: Behrend’s construction of 3-AP-free sets, graph counting and removal, Erdős–Stone–Simonovits again, graph property testing. §2.5–2.6, 2.9

  9. W 10/6 Graph regularity: induced removal and strong regularity, hypergraph removal and regularity §2.10–2.11

  10. W 10/13 Pseudorandom graphs: Chung–Graham–Wilson equivalences for quasirandom graphs, §3.1

  11. M 10/18 Pseudorandom graphs: expander mixing lemma, Cayley graphs on Z/pZ, §3.2–3.3

  12. W 10/20 Pseudorandom graphs: quasirandom groups, quasirandom Cayley graphs, §3.4–3.5

  13. M 10/25 Pseudorandom graphs: second eigenvalue bound §3.6

  14. W 10/27 Graph limits: introduction, graphon, cut distance §4.1–4.3

  15. M 11/1 Graph limits: homomorphism density, counting lemma, weak regularity lemma, §4.3, 4.5–4.6

  16. W 11/3 Graph limits: martingale convergence theorem, compactness of the graphon space, equivalence of convergence, §4.7–4.9

  17. M 11/8 Graph homomorphism inequalities: edge-triangle region, Cauchy–Schwarz §5.1–5.2

  18. W 11/10 Graph homomorphism inequalities: flag algebra, Hölder, Lagrangian §5.3–5.4

  19. M 11/15 Forbidding 3-term arithmetic progressions: finite field §6.1–6.2

  20. W 11/17 Forbidding 3-term arithmetic progressions: integers §6.3–6.4

  21. M 11/22 Forbidding 3-term arithmetic progressions: polynomial method §6.5. Structure of set addition: statement of Freiman’s theorem §7.1

  22. W 11/24 Structure of set addition: Ruzsa triangle inequality, Plünnecke’s inequality, Ruzsa covering lemma, Freiman’s theorem in groups of bounded exponent §7.2–7.5

  23. M 11/29 Structure of set addition: Freiman homomorphisms, Ruzsa’s model lemma, Bogolyubov’s lemma §7.6–7.8

  24. W 12/1 Structure of set addition: Geometry of numbers, proof of Freiman’s theorem, polynomial Freiman—Ruzsa conjecture §7.9–7.12

  25. M 12/6 Structure of set addition: Additive energy and the Balog—Szemerédi—Gowers theorem §7.13

  26. W 12/8 Sum-product problem §8

Problem sets

Problem set PDF

The problem set will be updated over the course of the semester. I will announce on Canvas when each problem set is complete.

You should only submit the designated problems, but are encouraged to try the rest as well.

Starred problems are generally more challenging.

To get the most out of this course, you are expected to spend a significant amount of time solving these problems. It will be essential to start thinking about these problems early.


Problem set Due date
PS 1 Sun Sep 26
PS 2 Sun Oct 10
PS 3 Sun Oct 24
PS 4 Sun Nov 7
PS 5 Sun Nov 21
PS 6 Sun Dec 5

Starred problems on each problem set should be submitted separately, with an automatic 7-day extension without penalty (and no additional extensions permitted).


Late policy


Acknowledging collaborators and sources

It is required to acknowledge your sources (even if you worked independently)

Intentional violations of the above policies may be considered academic dishonesty/misconduct.

Book draft

I am in the process of editing and rewriting the course notes from Fall 2019 into a textbook. I will be updating the book draft as the semester progresses. Check there for the latest available version. This book draft will also serve as course notes.

The book is still very much in an unfinished state, especially in the later sections.

The numberings (sections, theorems, etc.) in the book draft are unstable. When quoting theorems for homework, please include the statement or a description of the result rather than simply the theorem number.

Your feedback on the book draft is appreciated. Please help me find errors (both of the English and math kind). Also point out places where the exposition is unclear. Suggestions are welcome. Please post your comments in Piazza in the “book” folder. Your active participation in giving feedback on the book draft contributes to the 10% of the grade as discussed in the grading scheme.

Wikipedia assignment

Wikipedia is often the first landing page for students (and even researchers) when looking to learn about a new concept. Unfortunately, many of topics in combinatorics are poorly represented on Wikipedia.

Your assignment: pick some topic related to this course (even tangentially related is okay) where the Wikipedia page is either non-existent or has room for substantial improvements. Edit Wikipedia to make it better.

Tutorial: editing Wikipedia

You are asked to do more than simply editing. This is a literature research and expository writing assignment. It is your job to look up and learn a topic and then distill the most important information in the format of a Wikipedia article.

How to select a topic:

Some components of a good Wikipedia article:

We will do this assignment in several stages, mimicking a double-blind review process.

Everyone should contribute individually (not working in groups).

For this assignment, use “private” post on Piazza (your name hidden to other students but visible to me) in the folder wiki.

Stage I - proposal (due Sat Nov 13)

Stage II - initial edit (due Sat Nov 27)

Stage III - peer review and comments (due Sat Dec 4)

Stage IV - revision (due Wed Dec 8)

Please edit your initial Piazza post for all the stages rather than creating new ones (one post per student).

Use bold section headers (Stage I, II, IV) to clearly separate different parts of your post.


Additional references for material covered in the course

Extremal graph theory

Pseudorandom graphs and graph limits

Additive combinatorics