Title: Quantitative Sylvester-Gallai theorems
Speaker: Zeev Dvir, Princeton University
Date: Tuesday, January 31, 2012 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
Consider a set of point in R^n. A classical theorem of Sylvester-Gallai says that, if for every two points there is a third point on the line connecting them, then all points are on the same line. In this talk I will describe new quantitative analogs of this theorem in which both the condition and the consequence are weakened. For example, assuming only that a constant fraction of the pairs have a third point on the line connecting them, we can show that there is a large subset of the points (constant fraction) which lies in a subspace of constant dimension. The main ingredient in the proof is a new bound on the rank of sparse matrices whose pattern of zeros/non-zeros satisfies a weak 'design' condition. Joint work with B. Barak, A. Yehudayoff and A. Wigderson.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math