Problems in Combinatorial Geometry and Ramsey Theory

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

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.