Problems at the interface between Ramsey Theory and Combinatorial Geometry

这个项目的目标是探索组合几何和拉姆齐理论中的几个问题和方向及其相互联系。一个研究方向是围绕点和曲线之间的几何关联问题，以及它们与涉及距离、面积和其他度量的问题的联系。该项目还涉及几何问题的拉姆齐理论，应用货车德尔Waerden定理的算术级数和新的结果，这种类型，以及其他适合在更广泛的类别单调路径的线安排。特别令人感兴趣的是技术，允许重新制定的几何问题在一个纯粹的组合设置，如技术的允许序列介绍古德曼和波拉克。最后一类包括估计集合大小的问题，这些问题出现在集合加法和乘法理论中。Ramsey型极值离散几何问题和Erdos型极值离散几何问题在组合数学和计算几何领域引起了持续的关注，这是由于它们与计算问题（范围计数，模式匹配，运动规划等）的相关性以及为改善极值边界而开发的丰富技术（如ε-网理论，交叉引理，准平面图等），该项目的一个关键目标是探索和确定新的技术，用于处理关联和距离问题，以及拉姆齐理论和数论中似乎需要从多个方向攻击的其他问题。拟议的研究的一个重要特点是推进从不同领域的技术集成-几何图论，数论，拓扑，线性规划，计算机实验，算法理论-在寻找组合几何和拉姆齐理论中的问题的解决方案。这里提出的一些组合问题的进展可能在几何算法、近似算法等的设计和分析中有应用，因此随着时间的推移在真实的世界中有影响。

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.