18.225 Graph Theory and Additive Combinatorics

Fall 2021, MIT, graduate level

Quick links: [Class files on Dropbox] [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 files: Dropbox folder. Will be updated throughout the term.

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.

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

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.

Problem sets

See Dropbox folder for the problem set. It 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.

Schedule

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

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.

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 in the Dropbox folder 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.

References

Additional references for material covered in the course

Extremal graph theory

Pseudorandom graphs and graph limits

Additive combinatorics

Previous versions of the course: Fall 2017, Fall 2019