Polynomial Method in Combinatorics

logo 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 non-coplanar 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.


Scribe notes by Eric Naslund

Homework exercises


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: