18.217 Graph Theory and Additive Combinatorics

Fall 2019, MIT

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

• Announcement: The first lecture of 18.217 will be Monday Sept 9. We will not meet on Wed Sept 4

Lecturer: Yufei Zhao (see website 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.,

• Szemerédi’s theorem. Every set of integers of positive density contains arbitrarily long arithmetic progressions;
• Green–Tao theorem. The primes contain arbitrarily long arithmetic progressions.

The course will explore these and related topics, including:

• Extremal graph theory. What is the maximum number of edges in a triangle-free graph on n vertices? What if instead we forbid cycles of length 4? At most how many edges can an n-vertex graph have if every edge is contained in exactly one triangle?
• Szemerédi’s regularity lemma. A powerful tool in combinatorics that provides an approximate description/decomposition for every large graph.
• Pseudorandom graphs. What does it mean for some graph to resemble a random graph?
• Graph limits. In what sense can a sequence of graphs, increasing in size, converge to some limit object?
• Fourier analysis in additive combinatorics. An important technique for studying combinatorial properties in arithmetic settings, e.g., in the proof of Roth’s theorem.
• Freiman’s theorem and the structure of sum sets. What can one say about sets A such that the sum set $A + A = \{a + a’ : a,a’ \in A\}$ is small?
• Sum-product phenomenon. Can a set $A$ simultaneously have both small sum set $A + A$ and product set $A \cdot A$?

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:

• Problem sets, 4~6 problem sets
• Writing assignments, consisting of (1) course notes and (2) Wikipedia contributions.

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 (S³) and Student Disability Services

Course notes

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

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.

More information to come later

Lectures

• 9/9 Introduction to the course. Schur’s theorem and Ramsey’s theorem. Overview of Szemerédi’s theorem and related results

Homework

Problem set (coming soon): a list of problems for practice. A subset of these problems will be designated as to-be-turned in by midnight of each due date. You should only submit the designated problems.

Due dates to be posted soon

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.

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. 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 are expected to contribute to Wikipedia by creating or significantly improving an article on a topic related to the course. You may do this in collaboration with another student. Quality matters more than quantity, and a general rule of thumb is that each person should have contributions roughly amounting to one high quality article. More information to come later.

Open problems

There will be a list of open problems related to the topic of 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

• David Conlon’s notes on extremal graph theory
• Asaf Shapira’s notes on extremal graph theory
• Choongbum Lee’s notes on extremal combinatorics

Pseudorandom graphs and graph limits

• Chapter 9 of Alon and Spencer, The Probabilitic Method
• László Lovász, Large Networks and Graph Limits

Additive combinatorics

• Ben Green’s notes on additive combinatorics
• K. Soundararajan’s notes on additive combinatorics
• Adam Sheffer’s notes on additive combinatorics
• Tao and Vu, Additive Combinatorics

Previous version of the course Fall 2017