# Josef Cibulka

## REU 2012

Welcome! I am the grad coordinator of the Czech part of the REU. I'm a PhD. student of computer science at Charles University in Prague, Czech Republic. I'm interested in combinatorics and combinatorial geometry. You can see more on my Prague webpage

The other members of the Czech group are Martin Balko, Ondra Bílka, Martin Böhm and Pavel Veselý.

Proceedings from the Czech part of the REU: DIMACS-DIMATIA International REU Research Experience for Undergraduates 2012, IUUK-ITI series 2012-569.

Introduction to Czech Republic (presentations from the Cultural day):

### Project description

In addition to those described on other Czechs' pages, we spent some time looking at the following problems:
• Planarization by edge contractions:
Input is a graph and the task is to make as few edge contractions as possible to obtain a planar graph. We were looking at a possibility to find a polynomial approximation algorithm. Some results are known for a similar problem with edge deletions instead of contractions.
• Empty monochromatic polygons on a random point set:
The main problem is described on Martin's page. That is, we are searching for the largest monochromatic empty (not necessarily convex) polygon. This time we would like to determine the expected size in a set of n points drawn uniformly from a unit square and with each point colored green or red with the same probability. It is easy to see that with high probability, we find such a polygon on size in the order of log(n). Can this can be improved? If we search for an empty monochromatic convex hole, the answer is in the order of log(n)/loglog(n) by a result of Balogh, González-Aguilar and Salazar.
• Questions related to the previous one - Minimum area of a polygon on a pointset:
What is the expected maximum number of vertices of a polygon of area 1/n that uses only vertices from a given set of n points drawn uniformly at random from a unit square? What is the expected area of the smallest polygon that uses all the vertices from a given set drawn uniformly at random from a unit square? What is the probability that the set of points admits a polygon of area smaller than 1/n? 1/n^2? 1/2^n? ...
Slides from my final presentation. See the above-mentioned proceedings for a corrected and improved version of the result.

I have already participated in the REU program twice, but only as a mere participant - 2005 and 2006 .