Problems at the interface between Ramsey Theory and Combinatorial Geometry

University Of Wisconsin-Milwaukee, Milwaukee WI

Investigators

Abstract

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.