Rutgers Discrete Mathematics Seminar

Title: On the Number of Rich Lines in Truly High Dimensional Sets

Speaker: Sivakanth Gopi, Princeton

Date: Monday, March 30, 2015 11:00 am

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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. We will also discuss some subsequent work by Zahl, Hablicsek and Scherr which made progress on our conjecture.

Joint work with Zeev Dvir (Princeton).