***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 6th November, 3:00 in Fine Hall 224.
 
Speaker: Ben Lund (Rutgers) 

Title: Few distinct distances and perpendicular bisectors.

Let d(n) be the smallest number of distinct distances determined by any set of n
points in the real plane. For n sufficiently large, is each set of n points that
determines d(n) distances the intersection of an equilateral triangular lattice
with a convex set? Is there at least a line that contains n^ε points, for some
ε>0?

Erdős asked these questions 30 years ago, and an argument due to Szemerédi shows
that, if P is a set of points that determines n/k distances, then the
perpendicular bisector of some pair of the points must be incident to k of the
points. I will present an upper bound on the number of quadruples (x,y,z,w)
among a set of points such that the perpendicular bisector of (x,y) is the same
as the bisector of (z,w). Combined with Szemerédi's argument, this bound implies
that set of n points that determines n/k distinct distances either includes
Omega(n^{7/5}) collinear k-tuples, or a single circle or line contains
Omega(n^{1/12}) points.

Joint work with Adam Sheffer and Frank de Zeeuw.

                       -----------

Next week: Alex Scott

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)