18.217 Graph Theory and Additive Combinatorics

Fall 2019, MIT

Quick links: [Lecture videos: MIT OCW, YouTube] [Notes] [Homework]

Class meetings: Mondays and Wednesdays 2:30–4pm in 2-190

Lecturer: Yufei Zhao (see link for contact info)

Office hours: Instead of scheduling regular office hours, the lecturer will be generally be available in the Math Common Room (2-290) after lectures to chat and answer questions. Please email for individual appointments. Special office hours may be set up before homework due dates according to demand.

Please include “18.217” in the subject line of your emails.

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.

Prerequisites: Mathematical maturity at the level of a first-year math graduate student.

Grading. The final grade will be determined by the minimum of the student’s performance in the two categories:

There will be no exams. For borderline grades, participation may play a factor in determining the final grade. In addition, there will be a list open problems for which any significant progress/resolution may, at the discretion of the instructor, result in a grading bonus, overriding the above grading criteria.

Student Support Services (S3) and Student Disability Services

Course notes

Completed notes available here as PDF

Registered students may access the write-enabled link to the course notes from the email sent to class at the beginning of term, or via the link in Stellar. Read-only link to course notes on Overleaf

Each student taking the class for credit is expected to write course notes on one lecture (possbily in collaboration with another student, depending on course enrollement).

Please see the beginning of the document for important information regarding this writing assignment. In particular, the students responsible for writing up a lecture should:

Everyone is encouraged and expected to contribute to editing the notes.

Notes from the previous version of the course. They may be consulted but not copied when writing the new course notes.

Lectures

Lecture videos: MIT OpenCourseWare and YouTube

Chapter/section numbers (§) refer to the course notes

Homework

Problem set: a list of problems for practice. A subset of these problems will be designated as to-be-turned in by 11:59pm of each due date. You should only submit the designated problems.

Problem set Due date (♣ tentative)
PS 1 Sunday September 29
PS 2 Sunday October 13
PS 3 Sunday October 27
PS 4 Sunday November 10
PS 5 Sunday November 24
PS 6 Wednesday December 11

Stellar/Gradebook – primarily used for submitting and returning homework

Submissions. All homework submissions should be typed in LaTeX and submitted as PDF on Stellar. To make the grader’s job easier, please name your file ps#_Lastname_Firstname.pdf (replace # by problem set number, and the rest by your name). Remember to include your name at the top of your submission. Suggested LaTeX template for homework submissions.

Late policy. Submissions are due on Stellar by 11:59pm of each due date. Late submissions will be penalized by 20% per each late day. For example, for an assignment due on Sunday, a submission worth x points if turned in on time will be worth $0.6x$ points if submitted on Tuesday.

Sources. Important! Please acknowledge, individually for every problem at the beginning of each solution, a list of all collaborators and sources consulted (people, books, websites, etc.). Write sources consulted: none even if no sources are consulted. Failure acknowledge sources will lead to an automatic 10% penalty. You may not look up solutions to homework problems online or offline.

Collaboration policy. You are strongly encouraged to start early and first work on the problems on your own. Reasonable collaboration is permitted, but everyone must write their solutions individually and acknowledge their collaborators.

Wikipedia contributions

You may work in teams of sizes 1~3 to create or revise one or more articles on Wikipedia on topics related to the course (the topic does not have be one covered in the course; anything that is tangentially related is okay)

Due date: Sunday December 1. Please send the instructor an email (one per team) containing a short summary with links of your team’s contributions to Wikipedia

This is an open-ended assignment. The goal is to create more useful “entry points” to the subject, since Wikipedia is often among the first search results when someone Googles a term.

Quality matters more than quantity. A very rough guideline is that each person should have contributions equivalent to 30~50% of one high quality article.

Link to page for coordination sent out in email (link also available in Stellar)

Open problems

Open problems will regularly be mentioned in the course. You are encouraged to talk to Prof. Zhao if one of these problems interests you. Any major progress/resolution of one of the open problems (e.g., leading to a significant and publishable result) would be quite exciting, and could, among other things, result in an automatic A+ grade at the instructor’s discretion.

References

Additional references for material covered in the course

Extremal graph theory

Pseudorandom graphs and graph limits

Additive combinatorics

Previous version of the course Fall 2017