Algebraic Methods in Combinatorics 2015

Lecturer

Frank de Zeeuw

Feel free to email me with any questions.

Lectures and notes

Lecture 1 (Feb 16): Chapter 1 (Introduction)

Lecture 2 (Feb 23): Chapter 2 (Warmup theorems, Elekes-Sharir framework)

Lecture 3 (Mar   3): Chapter 3 (Joints)

Lecture 4 (Mar   6): Chapter 3 (Triple intersection points)

Lecture 5 (Mar 24): Chapter 4 (Intersection points)

Lecture 6 (Mar 27): Chapter 4 (More intersection points)

Lecture 7 (Mar 31): Chapter 5 (Polynomial partitioning)

Lecture 8 (Apr 14): Chapter 6 (Point-line incidences in R^3)

Lecture 9 (Apr 21): Chapter 7 (Distinct distances)

Lecture 10 (Apr 28): Chapter 8 (Point-surface incidences in R^3)

Lecture 11 (May 5): Chapter 9 (Incidences in C^2) [2-4pm in the coffee room]

Lecture 12 (May 12): Student presentations

Lecture 13 (May 19): Chapter 10 (Sum-product inequalities)

Lecture 14 (May 26): Chapter 11 (The Elekes-Rónyai Theorem)

 

Lecture notes (updated June 17) (This pretty much covers the course, but more will be added later.)

Details

– Course book entry

– Lectures: Tuesdays, 11-13, in MA A1 12. (We start at 11 sharp and end at 12:50.)

– Examination: There will be a written exam and a small project. The project will consist of a writeup of a few pages, covering something that complements the lectures.

– Level: The course is listed as a doctoral course, but Master students are very welcome. Although the material covers recent research, it should be relatively accessible, because both the problems (about points, lines, distances, …) and the methods (polynomials, curves, counting, …) are fairly elementary.

Description

We will study recent applications of algebraic geometry to combinatorial geometry (and so we will not consider algebraic methods in the most general sense).

The first half of the course will focus on the recent breakthrough result of Guth and Katz, who used a new algebraic to solve the long-standing distinct distances problem. We will see the entire proof (perhaps up to some black boxes), together with some of the results leading up to it. In the second half we will study various related problems, depending on the interests of the audience. For instance, we may consider Sylvester-Gallai problems, including the recent algebraic breakthrough of Green and Tao, or sum-product problems. In all of the above we will encounter a lot of incidence geometry with an algebraic flavor.

Reading

There will be lecture notes to accompany the lectures.

The following great surveys have a large overlap with the course:

  • Tao – Algebraic Combinatorial Geometry (journal / arXiv)
  • Guth – Unexpected Applications of Polynomials in Combinatorics (book / free / video)
  • Dvir – Incidence Theorems and Their Applications (journal / arXiv)

Guth has great notes on his website. And here are two videos of survey lectures by Micha Sharir.

The following papers are very relevant to the course:

  • Elekes – On the number of sums and products (journal)
  • Sharir-Sheffer-Solymosi – Distinct distances on two lines (journal / arXiv)
  • Kaplan-Sharir-Shustin – On Lines and Joints (journal / arXiv)
  • Elekes-Kaplan-Sharir – On Lines, Joints, and Incidences in Three Dimensions (journal / arXiv)
  • Kaplan-Matoušek-Sharir – Simple Proofs in Discrete Geometry (journal / arXiv)
  • Guth-Katz – On the Erdős distinct distances problem in the plane (journal / arXiv / video)
  • Rudnev-Selig – On the use of the Klein quadric (arXiv)
  • Kaplan-Matousek-Sharir – Unit Distances in Three Dimensions (journal / arXiv)

Suggested papers for the projects:

  • Dvir – On the size of Kakeya sets in finite fields (journal / arXiv)
  • Guth – Distinct Distance Estimates and Low Degree Polynomial Partitioning (journal / arXiv / video)
  • Hablicsek-Scherr – On the number of rich lines in high dimensional real vector spaces (arXiv)
  • Sharir-Sheffer-Zahl – Improved Bounds for Incidences Between Points and Circles (journal/arXiv/video)
  • Sharir-Solomon – Incidences between points and lines in three dimensions (arXiv)
  • Zahl – A Szemerédi-Trotter type theorem in R^4 (arXiv)
  • Fox-Pach-Sheffer-Suk-Zahl – A semi-algebraic version of Zarankiewicz’s problem (arXiv)
  • Sharir-Solymosi – Distinct distances from three points (arXiv)
  • Raz-Sharir – The number of unit-area triangles in the plane: Theme and variations (arXiv)
  • Shen – Algebraic methods in sum-product phenomena (journal / arXiv)