Problems in Combinatorial Geometry and Ramsey Theory

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This research project studies several fundamental problems in combinatorial geometry and Ramsey theory. Combinatorial geometry is the study of extremal configurations of points, lines, and other simple geometric objects in Euclidean space. Understanding these extremal configurations is a fundamental mathematical problem, which also has several practical applications such as in motion planning in robotics, visibility and intersection problems in computer graphics, and frequency assignment problems in cellular networks. The area has seen tremendous growth over the past 15 years, with numerous unexpected connections to other mathematical areas such as number theory, logic, and computer science. One of the main goals of this project is to further explore these connections, and the interplay of methods from combinatorics (regularity lemma, probabilistic method, and the container method), topology (cell decomposition), algebraic geometry (polynomial method), and computer science (coding theory). Graduate students will be involved in this project. There are three main areas under investigation. The first area is in incidence geometry, and one of the major goals of this project is to characterize dense point-line arrangements in the plane. The second area of research is in the study of combinatorial and topological problems involving planar arrangements of curves, including graph drawings. The third area is in Ramsey theory, which is a fundamental area of combinatorics that focuses on the appearance of a specific configuration in a sufficiently large system. The PI will continue his long-term study of estimating classical graph and hypergraph Ramsey numbers. He will also study Ramsey-type problems with a geometric flavor, which involve point sets in general position, Heilbronn’s triangle problem, visibility graphs, and unavoidable crossing patterns in graph drawings. 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.