# DIMACS Discrete Mathematics Seminar

## Title:

Ramsey-type Results for Geometric Graphs

## Speaker:

- Gyula Karolyi
- Institute for Advanced Study

## Place:

- Seminar Room 431, CoRE Building,
- Busch Campus, Rutgers University.

## Time:

- 4:30 PM
- Tuesday, December 12, 1995

Abstract:
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.

dimacs-www@dimacs.rutgers.edu
Document last modified on December 11, 1995