A geometric graph is a graph drawn in the plane so that every vertex corresponds to a point, and every edge is a closed straight-line segment connecting two vertices but not passing through a third. The n(n-1)/2 segments determined by n points in the plane, no three of which are collinear, form a complete geometric graph with n vertices. In classical Ramsey--theory, we want to find large monochromatic subgraphs in a complete graph whose edges are colored with several colors. Most questions of this type can be generalized to complete geometric graphs, where the monochromatic subgraphs are required to satisfy certain geometric conditions.
We prove, for instance, the following result on matchings: If the edges of a complete geometric graph with 3n - 1 vertices are colored by two colors, there exist n pairwise disjoint edges of the same color. Moreover, these edges can be found in n^{O(loglog n)} time.
We also investigate the case, when the monochromatic subgraph we are looking for is a spanning tree, a long path or a long cycle. We show instances, where the geometric problem is considerably more difficult, than the usual graph-Ramsey problem, and also try to explore the role of convexity in these problems.
This is a joint work with J\'anos Pach and G\'eza T\'oth.