Problems at the interface between Ramsey Theory and Combinatorial Geometry

拉姆齐理论与组合几何之间的接口问题

• 批准号: 1001667
• 负责人: Adrian Dumitrescu
• 金额: $ 30万
• 依托单位: University of Wisconsin-Milwaukee
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1001667&HistoricalAwards=false
• 关键词: Problems; interface; between; Ramsey; Theory

The objective of this project is to explore several problems and directions in Combinatorial Geometry and Ramsey Theory and their interconnections. One research direction is centered around the problem of geometric incidences between points and curves and their connections with problems involving distances, areas, and other measures. The project also deals with geometric questions in Ramsey theory, applications of Van der Waerden's theorem on arithmetic progressions and new results of this type, and others that fit in the broader category of monotone paths in line arrangements. Of particular interest are techniques that permit reformulations of geometric problems in a purely combinatorial setting, such as the technique of allowable sequences introduced by Goodman and Pollack. The last category comprises problems of estimating the size of sets that appear in the theory of set addition and multiplication. Ramsey type problems and Erdos-type extremal discrete geometry problems have attracted continued attention in the combinatorics and computational geometry communities, due to their relevance for computational problems (in range counting, pattern matching, motion planning, and others) and the rich techniques developed for improving extremal bounds (such as the epsilon-net theory, the Crossing Lemma, quasi-planar graphs, etc.), which proved to be instrumental in many areas of computational geometry.A key objective of this project is to explore and identify new techniques for dealing with incidence and distance problems, and other problems in Ramsey theory and number theory that seem to require attacks from several directions. An important feature of the proposed research is advancing the integration of techniques from different areas---geometric graph theory, number theory, topology, linear programming, computer experiments, theory of algorithms---in finding solutions for problems in combinatorial geometry and Ramsey theory. Progress on some of the combinatorial questions presented here are likely to have applications in the design and analysis of geometric algorithms, approximation algorithms, etc, and consequently have impact in the real word over time.

该项目的目的是探索组合几何学和拉姆西理论及其互连中的几个问题和方向。一个研究方向围绕点和曲线之间的几何发生率问题，以及与涉及距离，区域和其他措施的问题的联系。该项目还涉及拉姆西理论中的几何问题，范德沃登（Van der Waerden）在算术进程和这种类型的新结果中的应用，以及其他适合在线安排中更广泛的单调路径类别的应用。特别感兴趣的是允许在纯粹组合设置的几何问题的技术，例如Goodman和Pollack引入的允许序列的技术。最后一个类别包括估计集合添加和乘法理论中出现的集合大小的问题。 Ramsey类型问题和ERDOS型极端离散的几何问题问题引起了组合和计算几何社区的持续关注，因为它们与计算问题（在范围计数，模式匹配，运动计划等中的范围计数中的相关性）以及为丰富的技术而开发了丰富的技术。改善极端界限（例如epsilon-net理论，交叉引理，准平面图等），事实证明在计算几何学的许多领域都起着重要作用。该项目的关键目标是探索和确定新技术用于处理发病率和距离问题，以及拉姆齐理论和数字理论中的其他问题，似乎需要从多个方向发动攻击。拟议研究的一个重要特征是推进来自不同领域的技术的整合 - 几何图理论，数字理论，拓扑，线性编程，计算机实验，算法理论 - 在寻找组合几何和拉姆西问题的解决方案中理论。在此处提出的一些组合问题上的进展可能会在几何算法，近似算法等的设计和分析中具有应用，因此随着时间的推移会影响真实的单词。