# 18.S997 Graph Theory and Additive Combinatorics

Fall 2017, MIT

**Time:** Tuesdays and Thursdays 9:30—11am

**Class location:** 2-139

**Lecturer:** Yufei Zhao

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

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

## Grading

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

## Lectures

Class participants will be responsible for writing and editing the course notes. More details coming soon.

## Homework

There will be 3~4 graded homework assignments. Details to be decided.

In addition, there will be a continually updated list of ungraded exercises to provide practice with the course material.

## References

The content of the course will primarily be drawn from several sources listed below.

**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 (the 4th edition contains a new section on graph limits)
- 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