DIMACS
DIMACS REU 2012

General Information

Student: Martin Balko
Office: 446
School: Charles University in Prague
E-mail: mbalko@reu.dimacs.rutgers.edu
Project: Empty Monochromatic k-Holes in Points Sets

Project Description

We are working on some open problems in graph theory and combinatorics. One of the problems concerns with sets of points in plane in general position colored with two colors. The question is whether for a given number k there is a constant n=n(k) such that every bichromatic point set with at least n points in general position always contains a monochromatic k-hole. We know that this holds for 4-holes which do not have to be convex.

We would like to find out if this problem holds for convex 4-holes or for (not necessarily convex) k-holes where k > 4.


Additional Information