18.S997 Graph Theory and Additive Combinatorics

Fall 2017, MIT

Class time: Tuesdays and Thursdays 9:30—11am

Location: 66-144 (Room change!)

Lecturer: Yufei Zhao (see website for contact info). Office hours by email appointment

Course description

The course examines classical and modern developments in graph theory and additive combinatorics, with a focus on topics that connect the two subjects. Topics include: extremal graph theory, Szemerédi’s regularity lemma and applications, pseudorandom graphs, graph limits, Roth’s theorem and Szemerédi’s theorem on arithmetic progressions, Gowers uniformity norms, and the Green-Tao theorem. The course also introduces students to current research topics and open problems.

Here is a taste of some of the topics discussed in the course (time-permitting).

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

Student Support Services (S3) and Student Disability Services

Lectures

Course notes

Each student taking the class for credit is expected to write course notes on one (or more, depending on class size) lecture(s). The LaTeX files are hosted on our Overleaf project (registered class participants have received a separate link by email allowing read-write access to the project).

Everyone should contribute to editing the notes.

Piazza forum can be used for discussions of the notes, e.g., edit requests.

More instructions are found in the “About this document” section of the notes.

Homework

Stellar/Gradebook

Submissions. All homework submissions should be typed in LaTeX and submitted on Stellar.

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

Sources. At the top of each assignment, you must write either “Sources consulted: none” or a list of all sources consulted other than the course notes. Examples include: names of people you discussed homework with, books, other notes (including the ones listed in the references below), Wikipedia and other websites.

You should not look up solutions to homework problems online (or offline).

Collaboration policy. You are allowed and encouraged to collaborate, but everyone must write their solutions individually and acknowledge their collaborators.

The problem sets, below, will be updated with new problems after each lecture, up to until about a week before the due date. It is a good idea to start early and pace accordingly.

Problem set Due date (♣ tentative)
Problem set 1 Friday Sept 29
Problem set 2 Friday Oct 27
Problem set 3 Tuesday Nov 21
Problem set 4 Tuesday Dec 12

References

The content of the course will primarily be drawn from several sources listed below. The books have been placed on reserve at Hayden Library.

Extremal graph theory

Pseudorandom graphs and graph limits

Additive combinatorics