Problems in Combinatorial Geometry and Ramsey Theory

组合几何和拉姆齐理论中的问题

• 批准号: 2246847
• 负责人: Andrew Suk
• 金额: $ 25.18万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2026-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246847&HistoricalAwards=false
• 关键词: Problems; Combinatorial; Geometry; Ramsey; Theory

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.

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