Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

For a set of $n$ points in the plane, a $k$-set is a $k$-element subset which can be separated from the rest of the points with a line. An old problem asks for the maximum number of $k$-sets an $n$-element point set can have. This problem, and its higher dimensional analogues turned out to be very important in several areas of combinatorial and computational geometry, and we are still very far from the solution.

We review previous results, some applications and generalizations, and then improve the lower bounds of ErdH os, Lov'asz et al.

More precisely, for every $n, k, nge 2k>0$, we construct a set of $n$ points in the plane with $ne^{Omegaleft({sqrt{log k}} ight)}$ $k$-sets. As a consequence, we also improve the lower bounds in higher dimensions.