at 14:00
Tel-Aviv University - Computer Science Colloquium
Sunday, November 28, 14:15-15:15
at 14:00
Room 309, Schreiber Building
Let $S$ be a set of $n$ points in $R^d$ in general position,
and let $0<k<n$ be an integer. A subset $S'\subset S$ is called
a
$k$-set if $|S'|=k$ and $S'$ can be separated from $S\setminus S'$
by a hyperplane. Let $f_k^{(d)}(n)$ denote the maximum number of
$k$-sets for any set $S$ of $n$ points in $d$-space. The problem
of obtaining sharp bounds for these quantities have been posed by
Erd{\H o}s, Lov\'asz and others around 1970, and is still far from
being solved, even in the plane. In the talk I will discuss the
problem, show its connection to various problems in computational and
combinatorial geometry, involving arrangements of lines, hyperplanes,
and other surfaces, and review the recent progress that has been made.
The main topic in the talk is a very recent improvement of the upper
bound on $F_k^{(3)}(n)$ to $O(nk^{3/2})$, improving the previous bound
of $O(nk^{5/3})$.
Joint work with Shakhar Smorodinsky and G\'abor Tardos.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html