DIMACS logo

Zuzka Safernová

REU 2009

Hello, welcome to my REU page. My name is Zuzka Safernová and I'm a student of the Faculty of Maths and Physics of Charles University in Prague. I'm interested in combinatorics and discrete geometry.

I'm here with Czech people. The other members of our research group are Ondra Bílka, Jozef Jirásek, Pavel Klavík, Pavel Paták, Jan Volec and Martin Tancer.

Our advisor is Aaron Jaggard.

The geometric problem

Our goal is trying to prove the following conjecture.

Definition

Let S be a set of points in the plane. Two points v and w in S are visible with respect to S if the line segment between v and w contains no other point in S.

Conjecture

For all integers k,l >= 2 there is an integer n such that every set of at least n points in the plane contains at least l collinear points or k pairwise visible points.

What is known:

The conjecture is trivial for l <= 3.

Kara et al. proved the conjecture for k <= 4 and all l.

Addario-Berry et al. proved the conjecture for k = 5 and l = 4.

Abel et al. proved the conjecture for k = 5 and all l.

The conjecture is open for k = 6 or l = 4.

References:

Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmovic, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Por, David R. Wood. Every Large Point Set contains Many Collinear Points or an Empty Pentagon, arXiv:0904.0262, 2009

Louigi Addario-Berry, Cristina Fernandes, Yoshiharu Kohayakawa, Jos Coelho de Pina, and Yoshiko Wakabayashi. On a geometric Ramsey-style problem, 2007.

Peter Brass. On point sets without k collinear points. In Discrete Geometry, vol. 253 of Monographs and Textbooks in Pure and Applied Mathematics, pp. 185–192. Dekker, New York, 2003.

Jan Kara, Attila Por, David R. Wood. On the chromatic number of the visibility graph of a set of points in the plane, Discrete and Computational Geometry 34(3):497-506, 2005.

Jiri Matousek. Blocking visibility for points in general position, submitted, 2008.

Current state:

We were studying another problems, especially Vertex Cover and Coloring.