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.

这个项目的目的是探索组合几何和Ramsey理论的几个问题和方向以及它们之间的相互联系。一个研究方向是围绕点和曲线之间的几何关联问题以及它们与涉及距离、面积和其他度量的问题的联系。该项目还涉及Ramsey理论中的几何问题，Van der Wairden定理在算术级数上的应用和这类新的结果，以及其他适合于线排列中单调路径的更广泛类别的其他问题。特别令人感兴趣的是允许在纯粹的组合环境中重构几何问题的技术，例如古德曼和波拉克引入的允许序列技术。最后一类包括集合加法和乘法理论中出现的集合大小的估计问题。Ramsey类型问题和Erdos型极值离散几何问题一直是组合学和计算几何界关注的焦点，这是因为它们与计算问题(在范围计数、模式匹配、运动规划等方面)有关，并且发展了丰富的技术来改善极值界限(如epsilon-net理论、交叉引理、准平面图等)，这些技术被证明在计算几何的许多领域都是有用的。本项目的一个关键目标是探索和识别新的技术来处理关联和距离问题，以及Ramsey理论和数论中其他似乎需要从多个方向攻击的问题。这项研究的一个重要特点是促进了不同领域的技术的整合-几何图论、数论、拓扑学、线性规划、计算机实验、算法理论-在寻找组合几何和Ramsey理论问题的解决方案方面。这里提出的一些组合问题的进展可能会在几何算法、逼近算法等的设计和分析中得到应用，并因此随着时间的推移在现实世界中产生影响。