18.225 Graph Theory and Additive Combinatorics

Fall 2023, MIT, graduate level

Quick links: [Textbook] [Canvas] [Homework]

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

Instructor: Prof. Yufei Zhao

Graders: Yuan Yao (lead), Zi Song Yeoh, Saba Lepsveridze

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.

Textbook: Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, Cambridge University Press, 2023

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

Prerequisites

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

Grading

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

Lectures


Problem sets

Schedule

Problem set Due date
PS 1 Sun Sep 24
PS 2 Sun Oct 8
PS 3 Sun Oct 22
PS 4 Sun Nov 5
PS 5 Sun Nov 19
PS 6 Sun Dec 10

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

Submissions

Late policy

Collaborations

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.


Research project proposal assignment

Topic selection:

What should be in the proposal?

Ideas on where to find open problems

Previous versions of the course: Fall 2017, Fall 2019, Fall 2021