Ondra Bílka

REU 2008

Hello, welcome to my REU page. My name is Ondra Bílka and I'm a student of Computer Science at the Faculty of Maths and Physics of Charles University in Prague. I'm interested in combinatorics, discrete geometry and algebra.

Our advisors are Mario Szegedy, Dan Cranston and Padmini Mukkamala.

problem

I am working at following problem: Determine maximal ratio r such that in each configuration of n points in general configuration in plane we can connect r n*(n-1)/2 pairs of points by line segments without inducing convex quadrangle.

Previously was known r is greater than 1/2 by following strategy. bisect points to two n/2 point parts by line and draw line segment between any two points in diferent parts. Szegedy's idea was to get better bound by adding in each part all lines that doesnt cross second part. This is unfornately false for following example. Draw n equaly spaced points at circle with diameter 1. Then draw sqrt n equaly spaced points at cocentric circle with diameter n. We can see that probablity that random line in one part doesnt cross second part is roughtly 1/sqrt n.

Unfornately no methods I tried gave me any improvement.