Problems at the interface between Ramsey Theory and Combinatorial Geometry

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

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.