18.S997 Graph Theory and Additive Combinatorics

Fall 2017, MIT (Link to the most current version of the course)

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

• 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?
• Roth’s theorem. Every subset of $\{1, 2, \dots, n\}$ without a 3-term arithmetic progression contains $o(N)$ elements. And more generally …
• 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.
• Freiman’s theorem and the structure of sum sets. What can one say about sets $A$ such that $A + A = \{a + a’ : a,a’ \in A\}$ is not too large?
• Sum-product phenomenon. A set $A$ cannot simultaneously have $A + A$ and $A \cdot A = \{a a’ : a,a’\in A\}$ both small in size.

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.

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.

Grading

• 30% Lecture notes writing and editing
• 70% Problem sets
• There will be no exams

Student Support Services (S³) and Student Disability Services

Lectures

• Lecture 1 (9/7) Introduction to the course. Schur’s theorem and Ramsey’s theorem. Overview of developments in additive combinatorics
• Lecture 2 (9/12) Mantel’s theorem and Turán’s theorem. Statement of Erdős–Stone–Simonovits theorem
• Lecture 3 (9/14) Proof of Erdős–Stone–Simonovits theorem. Kővári-–Sós–-Turán theorem
• Lecture 4 (9/19) Constructions of $K_{s,t}$-free graphs
• Lecture 5 (9/21) Excluding bounded degree bipartite graphs. Dependent random choice. Statement of Szemerédi’s regularity lemma
• Lecture 6 (9/26) Proof of Szemerédi’s regularity lemma. Triangle counting lemma. Triangle removal lemma
• Lecture 7 (9/28) Property testing. Graph theoretic proof of Roth’s theorem. Behrend’s construction of 3-AP-free set
• Lecture 8 (10/3) Corners. General graph embedding and counting lemmas
• Lecture 9 (10/5) Regularity proof of Erdős–Stone–Simonovits theorem. Deducing Szemerédi’s theorem from the hypergraph removal lemma. Expander mixing lemma
• Lecture 10 (10/12) Cayley graphs. Fourier analysis on finite abelian groups
• Lecture 11 (10/17) Quasirandom graphs
• Lecture 12 (10/19) Quasirandom Cayley graphs. Introduction to graph limits
• Lecture 13 (10/24) Graph limits: statement of main results (equivalence, limit, compactness), counting lemma, statement of weak regularity lemma
• Lecture 14 (10/26) Graph limits: proof of weak regularity lemma, martingale convergence theorem, compactness of the space of graphons
• Lecture 15 (10/31) Comments on problem set 2. Graph limits: applications of compactness, strong regularity lemma
• Lecture 16 (11/2) Equivalence of convergence. Edge vs. triangle densities. Linear inequalities between clique densities. Razborov’s theorem (without proof)
• Lecture 17 (11/7) More on extremal graph theory. History of Roth’s theorem. Fourier analytic proof of Roth’s theorem for $\mathbb{F}_3^n$
• Lecture 18 (11/9) Roth’s proof of Roth’s theorem
• Lecture 19 (11/14) Polynomial method proof of Roth’s theorem in $\mathbb{F}_3^n$. Statement of Freiman’s theorem
• Lecture 20 (11/16) Ruzsa triangle inequality, Plünnecke–Ruzsa inequality, Ruzsa covering lemma, Freiman’s theorem in groups of bounded exponent
• Lecture 21 (11/21) Freiman homomorphisms, Ruzsa’s model lemma, statement of Bogolyubov’s lemma
• Lecture 22 (11/28) Bogolyubov’s lemma, geometry of numbers
• Lecture 23 (11/30) Proof of Minkowski’s second theorem, proof of Freiman’s theorem
• Lecture 24 (12/5) Polynomial Freiman–Ruzsa conjecture. Balog–Szemerédi–Gowers theorem
• Lecture 25 (12/7) Proof of graph BSG. Sum-product problem, crossing number inequality
• Lecture 26 (12/12) Szemerédi–Trotter theorem, Elekes’ proof of sum-product. Solymosi’s proof of sum-product

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.

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

• 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
• Tao and Vu, Additive Combinatorics