This research project is devoted to investigating various facets of interplay between geometry, number theory and combinatorics. The first part concerns the theory of geometric graphs and is motivated by the following question that remains open for several decades: "Does every planar drawing of a graph on n vertices and 1000n edges with straight line segments contain four pairwise crossing edges?" The PI plans to establish the existence of this and other crossing patterns in drawings of graphs with sufficiently many edges. Problems of finding good lower bounds on the minimal number of crossings over all drawings of a fixed graph, as well as the existing connections with algorithmic questions in computational geometry, will also be studied. A related investigator's goal is to apply Szemeredi's regularity lemma in combination with certain tools from real algebraic geometry and topology to prove the existence of large, complete or empty, bipartite subgraphs in the intersection graphs of segments, curves, or, in general, semi-algebraic sets. Another proposed direction of research is Euclidean Ramsey theory. Questions of the type: "Does any sufficiently large set of points in the plane, no three on a line, contain six points forming a convex hexagon with no other point inside?", or "Can one color points of the plane with six colors so that no two points, unit distance apart, receive the same color?", are questions posed many years ago by Erdos and other pioneers of the field, and despite all the efforts are still open. The author devises and plans to exploit novel perspectives on these problems, while introducing certain machinery from matroid and polytope theory, and commutative algebra.
The main theme of this proposal is to further explore the beauty of Ramsey theory and combinatorial geometry, especially natural and intuitive questions that can be easily described in lay terms, but difficult to solve. Fascinating problems of Erdos-type continue to be a fertile ground for interactions of various areas of mathematics and provide a theoretical foundation for combinatorial optimization, VLSI design, robotics, pattern recognition, tomography and computer graphics. Furthermore, an important aspect of this proposal is its educational component. Working with an undergraduate student, the investigator initiates a new discipline of Ramsey theory on integers, where one is interested in the existence of rainbow arithmetic structures. Questions considered are of the form: "Does every 3-coloring of integers from 1 to 3n, with exactly n red, n blue and n green integers, contain a rainbow 3-term arithmetic progression?" The proposed problems are rainbow analogues of classical van der Waerden-type results in Ramsey theory, and are well suited for undergraduate research projects. Finally, the PI and his mentee discover and inspect a striking dependency of the degree of regularity of certain linear equations on the axioms of set theory.
