Date: Tuesday, 3 Sivan 5766 (May 30, '06)

Speaker: Gabriel Nivasch (Tel-Aviv University)

Title: "Point sets with many halving lines"

Abstract:
---------
Given a set S of n points in the plane in general position (no three
points collinear), n even, a *halving line* is a line through two points
of S that separates all the other points of S into two equal parts. It is
a long-standing open problem to determine the maximum number of halving
lines as a function of n.

The current upper bound is O(n^(4/3)), due to Dey (1998), and the current
lower bound is of the form n*e^Omega(sqrt log n), due to Toth (2001).
Erdos et al. conjecture (1973) that the true bound is o(n^(1+epsilon)) for
every epsilon > 0.

In this talk we present an improved lower-bound construction. We achieve

Omega(n e^(sqrt ln 4 * sqrt ln n) / sqrt ln n)

halving lines for an n-point set, thus improving Toth's bound by a
constant factor in the exponent. Our construction is also significantly
simpler than Toth's.

We will also sketch the other main results on the topic. The talk will
include all necessary background material, so no previous knowledge on the
topic is necessary.