Discrete Geometry and Extremal Combinatorics

This project concerns several open problems at the intersection of discrete geometry and extremal combinatorics. Questions in discrete geometry traditionally involve sets of points, lines, triangles, planes, or other simple geometric objects, and many of them are tantalizingly natural and worth studying for their own sake. Some of them, such as the structure of 3-dimensional convex polytopes, go back to the antiquity, while others are also intimately connected with various different areas of modern mathematics, in particular extremal combinatorics. In recent years, these rich interactions have led to several remarkable developments between these two fields, and the goal of this project is to essentially capitalize as much as possible on this momentum. The first part of this project concerns Ramsey theory around the Erdős-Szekeres problem about the existence of large convex polytopes in finite configurations of point sets in general position, with an eye particularly towards establishing new upper bounds for various classical Ramsey numbers for graphs and hypergraphs. The second part of this proposal is about incidence geometry, an area with roots in Turán-type problems in extremal graph theory which is also fundamentally connected with other branches of mathematics, such as harmonic analysis and number theory, via the so-called sum-product phenomenon. The PI intends to further develop these connections by studying several old and new natural problems that arise on the different sides of this story. Examples of motivating (longstanding) questions include: the Zarankiewicz problem, the unit distance conjecture, and the Heilbronn triangle problem. As a byproduct, the PI also plans to develop new tools that could further the interplay between algebraic, analytic, combinatorial, and probabilistic methods in discrete mathematics. The PI plans to involve graduate students in this project. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.