Combinatorics Seminar

How few distinct perpendicular bisectors may be determined by a set of n points in the Euclidean plane? The vertices of a regular n-gon show that it is possible to determine exactly n bisectors, and it is not hard to show that it is impossible to determine fewer than n. In this talk, I will discuss a recent result that either a single line or circle contains all but an arbitrarily small, constant fraction of the n points, or the number of distinct bisectors is Omega(n^{68/45 + \epsilon}). This is the first substantial progress toward a conjecture of Sheffer, de Zeeuw, and myself that either a single line or circle contains all but an arbitrarily small, constant fraction of the n points, or the number of distinct perpendicular bisectors is Omega(n^2). I will also mention a connection between this problem and a conjecture of Erdos that, among n points in the plane, there is always a point x such that the number of distances between x and the remaining n-1 points is Omega(n/sqrt(log n)).