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

Date: Thursday 4th December, 3:00 in Fine Hall 224.
 
Speaker: Zeev Dvir (Princeton)

Title: On the number of rich lines in truly high dimensional sets

We prove a new upper bound on the number of r-rich lines (lines with at least r
points) in a `truly' d-dimensional configuration of points v_1,...,v_n over the
complex numbers. More formally, we show that, if the number of r-rich lines is
significantly larger than n^2/r^d then there must exist a large subset of the
points  contained in a hyperplane. We conjecture that the factor r^d can be
replaced with a tight r^{d+1}. If true,  this would generalize the classic
Szemeredi-Trotter theorem  which gives a bound of n^2/r^3 on the number of
r-rich lines in a planar configuration. This conjecture was shown to hold in R^3
in a seminal work of Guth and Katz (2010) and was recently proved  over R^4
(under some additional restrictions) by Solomon and Sharir.  Although our bound
is not optimal, it is the first to hold in arbitrary dimension. For the special
case of arithmetic progressions (r collinear points that are evenly distanced)
we give a bound that is tight up to low order terms, showing that a
d-dimensional grid achieves the largest number of r-term progressions.

Joint work with Sivakanth Gopi (Princeton).

                       -----------

Next week: No seminar

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