Math 60610 – Polynomial Methods in Combinatorics – Fall 18
Math 60610 – Polynomial Methods in Combinatorics – Fall 18
NOTE: all course policies announced here are subject to change up to the first day of semester!
Instructor: Abdul Basit
Office: HAYE 248
Email: abasit@nd.edu
Office Hours: By appointment.
Meeting Times: MWF 10:30 am – 11:20 am, O’Shaughnessy Hall 209
We will loosely following the textbook, Polynomial Methods in Combinatorics, by Larry Guth (ISBN: 978-1-4704-2890-7). In addition, it will be useful to reference the following:
The objective of this course is to study recent applications of algebraic geometry to extremal problems in combinatorial geometry. The first half of the course will focus on a breakthrough result of Guth and Katz, who used algebraic methods to solve the long-standing distinct distances problem. I expect that we will see most of the proof (up to some black boxes), along with some of the results leading up to it.
In the second half we will study various related problems, based on class interest. For example, we may consider more general frameworks under which the Guth-Katz and many other results fall, i.e., the Elekes-Szabo problem and Zarankiewicz’s problem for semi-algebraic graphs.
Topics: Below is a tentative list of topics we will cover:
Zarankiewicz’s problem
Incidence problems in the Euclidean Plane.
Joints problem.
Guth and Katz’s distinct distances result.
Incidences in higher dimensions.
Zarankiewicz’s problem for semi-algebraic graphs.
The Elekes-Rónyai problem.
Mathematical Preparation: Although the material covers recent research, it should be relatively accessible. Both the problems (about points, lines, distances, …) and the methods (polynomials, curves, counting, …) are fairly elementary.
Notes on Extremal Combinatorics. We will be covering most of the first three sections.
The three proofs of Szemerédi-Trotter, can be found in Chapter 2 of Dvir’s survey linked to above (see Sections 2.1 and 2.5).
The proofs related point-line incidences in three dimensions can be found in Section 3 of de Zeeuw’s survey linked to above. More details can be found in the following paper:
On lines, joints, and incidences in three dimensions – Elekes, Sharir, Kaplan.
Polynomials vanishing on grids: The Elekes-Rónyai problem revisited – Raz, Sharir, Solymosi.
A semi-algebraic version of Zarankiewicz’s problem – Fox, Pach, Sheffer, Suk, Zahl.
Exercises can be found here. The file will be updated regularly.
Last Update: 09/13/2018.
Nov 26: Justin Miller
Nov 28: Gregory Cousins
Nov 30: Leo Jimenez
Dec 03: Kyle Gannon
Dec 05: Li Ling Ko
Here’s a list of paper I think would be nice to present. You’re welcome to choose something not on the list, but run it by me first.
(Li Ling Ko) Norm-graphs and bipartite Turán numbers – Kollár, Rónyai and Szabó.
A lower bound the extremal numbers for bipartite graphs K_{t, s} when s >= t! + 1.
(Justin Miller) Random algebraic construction of extremal graphs – Bukh.
A probabilistic construction of graphs with no large bipartite subgraphs.
Distinct distances on algebraic curves in the plane – Pach, De Zeeuw.
A variation of the distinct distances problem, when the point set is contained in a constant degree algebraic curve.
Polynomial partitioning for a set of varieties – Guth.
A generalization of the polynomial partitioning theorem for points to varieties of any co-dimension.
An incidence theorem in higher dimensions – Solymosi, Tao.
An application of “constant degree” partitioning polynomials, where the partitioning polynomials are taken to be of constant degree, simplifying the analysis considerably.
On sets defining few ordinary lines – Green, Tao.
Finding algebraic structure from combinatorial properties of the point set. This is a long paper, but you’d only be presenting Proposition 5.1 (along with the required background and lemmas).
(Leo Jimenez) Cutting lemma and Zarankiewicz’s problem in distal structures – Chernikov, Galvin, Starchenko.
A generalization of incidence bounds to distal structures.
Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions – Basu, Sombra.
Polynomial partitioning for points lying on a variety of co-dimension 2.
Szemerédi-Trotter-type theorems in dimension 3 -Kollár
An incidence bound in arbitrary fields.
Problem sets will be posted every few weeks.
Each student will be required to present a paper. A list of suggested papers will be posted as the semester progresses.