Problems in Combinatorial Geometry and Ramsey Theory

本课题研究组合几何和拉姆齐理论中的几个基本问题。组合几何是研究欧几里德空间中点、线和其他简单几何物体的极值构型的学科。理解这些极值配置是一个基本的数学问题，它也有一些实际应用，如机器人的运动规划、计算机图形学中的可见性和交叉问题，以及蜂窝网络中的频率分配问题。在过去的15年中，该领域取得了巨大的发展，与数论、逻辑和计算机科学等其他数学领域有着许多意想不到的联系。该项目的主要目标之一是进一步探索这些联系，以及组合学（正则引理、概率方法和容器方法）、拓扑学（细胞分解）、代数几何（多项式方法）和计算机科学（编码理论）等方法之间的相互作用。研究生将参与这个项目。目前正在调查的主要领域有三个。第一个领域是入射几何，这个项目的主要目标之一是表征平面上密集的点线排列。第二个研究领域是研究组合和拓扑问题，涉及曲线的平面排列，包括图形绘图。第三个领域是拉姆齐理论，这是组合学的一个基本领域，它关注的是一个足够大的系统中特定构型的外观。PI将继续他对估计经典图和超图拉姆齐数的长期研究。他还将研究具有几何风格的ramsey型问题，包括一般位置上的点集、Heilbronn三角形问题、可见性图和图形中不可避免的交叉模式。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.