Polynomial Method in Combinatorics
Graduate course, Trinity Term 2016
Instructor: Yufei Zhao
Time: Tuesday 10—11.30
Location: C3 (week 1), C4 (weeks 2—8)
Mathematical Institute, University of Oxford
Course description
We study a number of surprising applications of polynomials to problems in combinatorics. Many of these results were discovered only in the past decade, and their solutions are often surprising and short. The method provided solutions to a number of long standing open problems that appear to have little to do with polynomials, such as the finite field Kakeya conjecture and the joints problem. The method also played a central role in the solution of the Erdős distinct distance problem. In this course, we will examine these solutions, and understand how algebraic structure arises naturally in problems in combinatorial geometry and coding theory.
Here are some examples of results that will be discussed in this course. The first two have very short proofs. The third is much more involved, and we will be discussing many of the ideas that go into its proof.
Finite field Kakeya problem. (Dvir) If $A \subset \mathbb{F}_q^n$ contains a line in every direction, then $A \ge c_n q^n$.
Joints problem. (Guth–Katz) Any $N$ lines in $\mathbb{R}^3$ contain at most $O(N^{3/2})$ joints, where a joint is a point incident to three noncoplanar lines.
Erdős distinct distance problem. (Guth–Katz) Any $N$ points in $\mathbb{R}^2$ have at least $c N/\log N$ distinct pairwise distances.
Lectures
Scribe notes by Eric Naslund

Lecture 1 — 26 April 2016 [Board photos]
Introduction. Basic method (parameter counting and vanishing lemma). Finite field Nikodym and Kakeya problems. Joints problem. 
Lecture 2 — 3 May 2016
Finite field Kakeya without polynomials – bush method and Wolff’s hairbrush argument. What’s so special about polynomials? Algebraic examples: Hermitian variety, doubly ruled surfaces. 
Lecture 3 — 10 May 2016 [Board photos]
Remarks on Croot–Lev–Pach result on progressionfree sets in $\mathbb{Z}_4^n$. Linear algebraic method in combinatorics—distinct distances in high dimensions. The polynomial method in error correcting codes: Berlekamp–Welch algorithm and Sudan list decoding algorithm; Reed–Solomon and Reed–Muller codes. 
Lecture 4 — 17 May 2016 [Board photos]
Szemerédi–Trotter theorem on pointline incidences in the plane. The cutting method. Polynomial partitioning method.
References: Matoušek’s note, Tao’s blog. 
Lecture 5 — 24 May 2016 [Board photos]
Proof of Szemerédi–Trotter using polynomial partitioning. Elekes–Sharir framework. Partial symmetries of the plane. Reduction of the distinct distances problem to incidence geometry of lines in $\mathbb{R}^3$.
Reference: Guth–Katz Section 2 
Lecture 6 — 31 May 2016 [Board photos]
Reguli. Algebraic structure and degree reduction.
Reference: Guth Lecture notes 
Lecture 7 — 7 June 2016 [Board photos]
Proof of the planar clustering theorem. Flat and critical points. Plane detection lemma.
Reference: Guth Lecture notes 14 and 15 
Lecture 8 — 14 June 2016 [Board photos]
Outline of the rest of the proof of the Guth–Katz theorem. Classification of doubly ruled surfaces. Flecnodes. Szemerédi–Trotter type theorem in 3dimensions.
Homework exercises
References
This course is based on another course taught by Larry Guth at MIT in Fall 2012. Notes from that course are available from its website.
The following survey discusses many of the topics that will be examined in this course: