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ý.
Our advisors are James Abello and
Milan Bradonjic.
Proceedings from the Czech part of the REU:
DIMACSDIMATIA International REU Research Experience for Undergraduates 2012, IUUKITI series 2012569.
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álezAguilar 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 abovementioned 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 .